Таблица 6.9

Ответ к задаче 6.7

G1

G2

G1

G2

n

20

6

20+6=26

m

170

3

170+3=173

k

1

4

1+4=5

γ

151

1

151+1=152

h

10

3

max(10,3)=10

d

2

Бесконечность

Бесконечность

Цикломатическое число равно 152, хроматическое число равно 10, диаметр равен бесконечности.

6.7.3. Двудольное представление графов

Биграф, двудольный граф или чeтный граф – это математиче-

ский термин теории графов, который обозначает множество вершин и связей между ними, таких, что если множество вершин разбить на два непересекающихся подмножества V1 и V2, то связи будут только между вершинами из разных подмножеств.

Неориентированный граф G = (V,U) называется двудольным, если множество его вершин можно разбить на две части V1 V2 V , |V1 | > 0, |V2 | > 0, так, что выполняются условия:

ни одна вершина в V1 не соединена с вершинами в V1;

ни одна вершина в V2 не соединена с вершинами в V2. Двудольный граф называется полным двудольным графом, ес-

ли для каждой пары вершин v1 V1, v2 V2 существует ребро (v1,v2 ) U . Для |U | = i, |V | = j такой граф называется Ki,j

Теорема 6.12. Граф является двудольным тогда и только тогда, когда он 2-раскрашиваемый (то есть его хроматическое число равняется двум).

На самом деле, если раскрасить вершины графа в два цвета, то легко расположить все вершины одного цвета в одной доле, все

190

вершины другого цвета – в другой доле и провести имеющиеся ребра. Соответственно, вершины каждой из долей будут попарно несмежными и, таким образом, граф – двудольным. На самом деле от способа изображения свойства графа, конечно же, не меняются, все 2-раскрашиваемые графы сами по себе изначально являются двудольными, только они могут иметь недвудольное представление, по которому факт двудольности не сразу кажется очевидным.

Задача 6.13. Определить, является ли граф (рис. 6.39, а) двудольным, и если да, построить его двудольное представление.

1

2

3

4

1

2

3

4

8 7 6 5 8 7 6 5

а			б
1	7	3	5

2

4

6

8

в

Рис. 6.39

Решение. В графе (рис. 6.39, а) все циклы имеют четную длину, следовательно, граф 2-раскрашиваемый (его хроматическое число равно 2). Это означает, что граф двудольный. Для построения двудольного представления раскрасим граф в два цвета (разные штриховки на рис. 6.39, б). Теперь разместим все заштрихованные одним способом вершины в первой доле (вершины 1, 7, 3, 5 – например, имеющие красный цвет), а остальные вершины (2, 4, 6, 8 – например, имеющие синий цвет) – во второй доле. Теперь остаeтся только провести ребра так, чтобы они соединяли смежные в исход-

191

ном графе вершины. Например, из вершины 1 нужно провести ребра в вершины 2, 4, 6, 8. Далее достаточно рассмотреть 7, 3 и 5, т.е. вершины одной доли, в результате все ребра будут построены. Двудольное представление графа построено на рис. 6.39, в.

6.7.4. Хроматический класс

В теории графов ставится часто вопрос о реберной раскраске графов. Какое минимальное число цветов нужно, чтобы раскрасить ребра графа так, что любые 2 смежных ребра (т.е. 2 ребра, имеющих общую вершину) были бы окрашены в разный цвет? Это минимальное число цветов называется хроматическим классом.

Дадим строгое определение. Граф G называется реберно k- раскрашиваемым, если его ребра можно раскрасить k красками таким образом, что никакие два смежных ребра не окажутся одного цвета. Если граф G реберно k-раскрашиваемый, но не является реберно (k–1)-раскрашиваемым, то k называется хроматическим классом графа G. При этом используется запись H(G)=k. На рис. 6.40 изображен граф G, для которого H(G)=4.

1	3
	4
2	2

1

4

3

Рис. 6.40

Ясно, что если наибольшая из степеней вершин графа G равна Stmax, то H(G) ≥ Stmax. Для хроматического класса графа справедлива следующая теорема, известная как теорема Визинга.

Теорема 6.13 (Визинга). Если в графе максимальная степень вершин равна Stm, то хроматический класс равен либо Stm, либо

Stm + 1.

192

Очевидно, что простейший алгоритм нахождения хроматического класса (и соответствующей раскраски ребер) состоит в следующем. По данному графу строим так называемый двойственный граф: ребра графа соответствуют вершинам нового (двойственного) графа, причем, если 2 ребра имеют общую вершину, то соответствующие вершины являются смежными и в двойственном графе, т.е. при построении соединяются ребром. После этого раскрашиваем наилучшим образом вершины двойственного графа и, переходя к «старому» графу, получаем (одну из возможных) наилучших реберных раскрасок графов. Можно собственно и не строить двойственный граф, а просто применить алгоритм поиска хроматического числа, заменив вершины ребрами. Например, при использовании алгоритма на методе поиска наименьшего покрытия ввести изначально при поиске пустых подграфов в виде пометки начальной вершины список ребер графа. На выходе первой части алгоритма получатся списки максимальных по включению множеств, содержащих попарно несмежные ребра. Вторая часть алгоритма будет выполняться аналогично.

В заключение отметим, что реберная раскраска часто применяется при конструировании различных устройств, где провода, соединяющиеся в одном узле, должны для удобства иметь разные цвета.

Заметим, что до сих пор нет «хороших» критериев для графов, позволяющих определить, когда же именно хроматический класс равен Stm, а когда Stm + 1.

Однако в некоторых частных случаях соответствующие результаты находятся легко. Например, хроматический класс простого цикла на n вершинах равен 2 или 3 в зависимости от того, четно n или нечетно. Хроматические классы полных двудольных и просто полных графов вычисляются в соответствии со следующими теоремами.

Теорема 6.14. Для полных двудольных графов

χe (Kn1 ,n2 ) = ρ = max(n1 , n2 ) .

Теорема 6.15. Для полных графов χe (Kn ) = n , если n нечетно (n≠1), и χe (Kn ) = n – 1, если n четно.

193