Пример 2.14

На рис. 2.26 приведен граф Питерсена, который гомеоморфный графу K₅ (граф K₅ может быть получен из графа Питерсена 5-кратным применением операции стягивания ребра). Следовательно, согласно теореме 2.14 он не является планарным.

2.6. Раскраска графов

             Хроматическое число графа

             Раскраска вершин

             Верхняя и нижняя оценка хроматического числа

             Раскрашивание планарных графов

 

Хроматическое число графа

В приложениях графов к решению практических задач часто возникает необходимость разбиения множества вершин (ребер) на классы с помощью задания на этом множестве некоторого отношения эквивалентности.

Правильной раскраской вершин графа G = (V, E) в    цветов называется разбиение {V₁, V₂, …, V_} множества V такое, что для любого i = 1, 2, …,    вершины, принадлежащие подмножеству V_i, попарно несмежные и окрашены в i-й цвет.

Раскраска называется неправильной, если в одно множество разбиения попадают смежные вершины.

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

Замечание. Всякий подграф правильно раскрашенного графа правильно раскрашен.

Граф k-раскрашиваем, если его можно правильно раскрасить не более, чем в k цветов.

Пусть  g_i(G) – количество правильных раскрасок вершин графа G  в i  цветов.

Хроматическим числом  (G) графа G называется наименьшее из чисел   из всех возможных правильных его раскрасок, т.е. 

(G) = min {i | g_i(G)  0}

Хроматическое число графа относится к классу трудно вычислимых инвариантов заданного графа.

Раскраска вершин

Граф G с хроматическим числом   (G) = 2 называется бихроматическим.

Теорема 2.15. Граф G – двудольный тогда и только тогда, когда он бихроматический граф.

Доказательство

Пусть G = (V₁, V₂, E) – двудольный граф. Всякую вершину v  V₁ окрасим в цвет , всякую вершину u   V₂ окрасим в цвет . В результате, все вершины окажутся окрашены в два цвета, и никакие смежные вершины не будут окрашены в один цвет, так как граф двудольный, то есть раскраска правильная.

Пусть теперь G – бихроматический граф. Тогда множество его вершин можно разбить на два не пересекающихся класса:

V₁ – окрашенные в цвет ;

V₂ – окрашенные в цвет .

Так как вершины каждого класса окрашены в один и тот же цвет, то среди них отсутствуют смежные вершины, то есть смежные вершины могут принадлежать только разным подмножествам V₁, V₂. Следовательно,

G = (V₁, V₂, E), V₁  V₂ = V и  V₁  V₂ =  – двудольный граф.

Замечание. Следующие утверждения равносильны:

1.      Граф G является бихроматическим.

2.      Граф G является двудольным.

3.      Граф G не содержит циклов нечетной длины.

Равносильность первых двух высказываний доказана в теореме 2.15.

Теорема 2.16 (Кенига). Хроматическое число (G) = 2  тогда и только тогда, когда граф G не содержит циклов нечетной длины.

Доказательство

Пусть (G) = 2. Предположим, что граф G содержит цикл нечетной длины, тогда число вершин в этом цикле будет также нечетно, кроме того, вершины цикла должны быть окрашены поочередно в два цвета, что невозможно сделать, следовательно, граф, содержащий этот цикл, нельзя правильно раскрасить двумя цветами.

Пусть граф G = (V, E)  не содержит циклов нечетной длины. Можно считать его связным, так как хроматическое число не зависит от числа компонент графа. Вершины u, v  V будем называть четно соединимыми, если  расстояние d(u, v) – четное. Покажем, что бинарное отношение четной соединимости на множестве V является эквивалентностью:

        рефлексивность выполняется, так как d(v, v) = 0 – четное число;

        симметричность выполняется, так как d(v, u) = d(u, v);

        транзитивность: если d(u, v) и d(v, w) – четные числа, то d(u, w) тоже четное число. Пусть L(u, v), L(v, w) и L(u, w) – кратчайшие простые цепи, соединяющие соответствующие вершины. Тогда по предположению длина замкнутого маршрута  L(u, v) _ L(v, w) _ L(w, u),  равная  d(u, v) + d(v, w) + d(w, u), является четной (так как из замкнутого маршрута нечетной длины может быть выделен простой цикл нечетной длины, что противоречит предположению). Отсюда d(u , w) = d(w, u) – четное число.

Отношение четной соединимости разбивает множество V на классы эквивалентности таким образом, что две вершины четно соединимы тогда и только тогда, когда они попадают в один класс.

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

Покажем, что количество классов не больше двух. Пусть классов эквивалентности больше двух и пусть r, s, t – представители трех из них. Так как d(r, s) + d(s, t) + d(t, r) – четное число, то хотя бы одно из входящих в него расстояний должно быть четным и, следовательно, соответствующие ему вершины вопреки предположению принадлежат одному классу. Следовательно, классов эквивалентности не больше двух: V = V₁  V₂.

Раскраска всех вершин класса V₁ в цвет 1, а всех вершин класса V₂  в цвет 2 является правильной для графа  G (двудольного графа), следовательно, (G) = 2