Компоненты связности графа
Лабораторная работа №4. ТЕОРИЯ ГРАФОВ.
РАСКРАСКА НЕОРИЕНТИРОВАННЫХ ГРАФОВ
Цель работы: изучить особенности неориентированных графов и основные определения; научиться находить хроматическое число и хроматический класс для графа.
Неориентированные графы
Основные понятия
Понятие неориентированного графа считают более общим по отношению к понятию ориентированного графа .
Ребром графа называется такая пара элементов
и
, для которой
или
(4.1)
т.е. пара вершин, связанных дугами в обоих направлениях либо одной дугой в каком-либо направлении.
Ребро обозначается так:
или
. (4.2)
Обозначим множество ребер графа через .
Множество вершин вместе с множеством ребер
определяют неориентированный граф, который обозначается через
. (4.3)
Каждому ориентированному графу можно однозначно поставить в соответствие неориентированный граф
. Обратное, очевидно, неверно.
Если в ориентированных графах (рис. 4.1, 4.2) дуги заменить
![]() |
Рис. 4.1 Рис. 4.2
ребрами, то получится неориентированный граф (рис. 4.3).
В некоторых случаях неориентированный граф можно воспринимать как симметрический граф без петель. Например, граф (рис. 4.3) и граф
(рис. 4.4) не различаются.
![]() |
Рис. 4.3 Рис. 4.4
Однако понятие неориентированности не всегда совпадает с понятием двусторонней ориентированности.
Например, в транспортной сети симметрия некоторых дуг может сочетаться с антисимметрией их пропускных способностей.
Неориентированному графу соответствует
различных графов
, где
- число ребер,
- число вершин. Например, граф, изображенный на рис. 4.5, имеет 14 дуг и 8 ребер.
Цепь – такая последовательность ребер , в которой каждое ребро
соприкасается одним из концов с ребром
, а другим – с
(если они существуют). Далее мы намеренно используем ориентированные графы при иллюстрации компонентов неориентированных графов с целью уяснения их родства и различия. При этом следует мысленно заменить дуги соответствующими ребрами.
Например, для графа, изображенного на рис. 4.1, цепи обозначаются так:
и
.
Длиной цепи называется число ребер, которые она содержит.
Простая и элементарная цепи определяются аналогично пути, только вместо дуг рассматриваются ребра.
Цикл – это конечная цепь, которая начинается и заканчивается в одной и той же вершине. Например, для графа, изображенного на рис. 4.5, цепи яв-ляются циклами.
Эквивалентными считаются циклы, проходящие через одни и те же вершины в одинаковом порядке. Например, для графа, показанного на рис. 4.5,
.
Понятия простого цикла и элементарного цикла определяются аналогично соответствующим понятиям для контуров, только вместо дуг рассматриваются ребра.
Связный граф .
Граф называется связным, если для всех
и
всегда существует цепь из вершины
в вершину
.
Сильно связный граф всегда связный.
Например, граф (см. рис. 4.3) связный, но не сильно связный; а граф
(см. рис. 4.5) – не связный и ему соответствующий граф
также не связный.
Компоненты связности графа.
Совокупность вершин графа ( ), которые можно соединить цепью, обозначим через
.
Компонентой связности называется подграф графа
, порожденный
.
Например, граф и ему соответствующий неориенти-рованный граф
(см. рис. 2.62) имеют две компоненты связности:
.
Рис. 4.5
Пусть - компоненты связности, порожденные подмно-жествами вершин
.
Тогда имеют место следующие соотношения:
(4.4)
, а также
.
Далее под словом «граф» подразумеваем неориентированный граф, ассоциируя по-прежнему дуги как ребра.
Степенью вершины называется число ребер, для которых одним из концов служит
(другой конец отличен от
). Степень вершины
обозначается через
.
Например, для графа, изображенного на рис. 4.5,
.