Доказательство. Необходимость. ( ) Пусть задан неориентированный граф G=(V, U) , не имеющий петель, для которого c(G) = 2
Необходимость. () Пусть задан неориентированный граф G =(V, U), не имеющий петель, для которого c (G) = 2. Предположим, что в G имеются элементарные циклы нечетной длины.
Пусть С = v 0,..., v 2 k +1, где v 2 k +1 = v 0, - элементарный цикл в G, имеющий нечетную длину.
Возьмем 2 -раскраску графа G. Тогда все вершины цикла С, имеющие четные номера, раскрашены в один цвет, а вершины этого же цикла с нечетными номерами раскрашены в другой цвет.
Вершины v 0 и v 2 k +1 цикла С совпадают и имеют четный и нечетный номера. Следовательно, одна и та же вершина графа должна быть раскрашена в разные цвета. Полученное противоречие означает, что предположение о существовании элементарных циклов нечетной длины в 2 -хроматическом графе G является неверным.
Поэтому G не может содержать элементарных циклов нечетной длины.
Достаточность. ()
Проведем доказательство в предположении связности графа G. Если G имеет несколько компонент связности, то проводимое доказательство справедливо для каждой компоненты связности этого графа, а значит, и для всего графа G.
Пусть связный граф G не имеет элементарных циклов нечетной длины.
Возьмем два цвета, которые обозначим как b и w.
Раскрасим все вершины G с помощью следующей процедуры.
1. Произвольную вершину v графа G раскрасим в цвет b.
2. Еще нераскрашенные вершины, соседние с вершинами, которые окрашены в цвет b, раскрасим в цвет w.
3. Все нераскрашенные вершины, которые являются соседними с вершинами, окрашенными в цвет w, раскрасим в цвет b.
4. Действия 2 и 3 повторяются, пока в G остаются не раскрашенные вершины.
Через конечное число шагов все вершины графа G будут раскрашены с использованием двух цветов.
Покажем, что выполненное раскрашивание вершин G является 2 -раскраской этого графа.
Предположим противное. В графе G некоторые соседние вершины v 1 и v 2 раскрашены одинаково.
Из определения процесса раскрашивания вершин графа G следует существование таких простых путей W 1 и W 2, ведущих из v в вершины v 1 и v 2, длины которых имеют одинаковую четность. Данная ситуация изображена на рис. 5.32.
v
W 1 v 3 W 2
v 1 v 2
Рис. 5.32
На этом рисунке пунктирные линии представляют пути в G. Здесь v 3-последняя общая вершина путей W 1 и W 2. Тогда последовательность вершин v 3,..., v 2, v 1,..., v 3 образует цикл нечетной длины. Это противоречит предположению об отсутствии таких циклов в графе G.
Поэтому приведенное раскрашивание G является его 2 -раскраской.
Дата добавления: 2015-09-27 | Просмотры: 403 | Нарушение авторских прав
|