Лабораторная работа №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,
.
