Автор: Юра Попов, 05 Декабря 2010 в 16:46, курсовая работа
Пусть Sn — множество целых чисел от 1 до п, которые мы будем называть цветами; n-раскраской графа G назовем такое отображение множества V(G) в Sn, при котором вершины, являющиеся концами одного ребра, окрашиваются в разные цвета (т.е. таким вершинам сопоставляются разные элементы из Sn). Через N(G;n) обозначим число n-раскрасок графа G. Очевидно, что N(G;n) является графовой функцией. Ясно также, что если G имеет петли, то N(G;n)=0.
Введение: 2
Глава I. Вершинная раскраска графа 4
1.1 Основные понятия вершинной раскраски графа. 4
1.2 Переборный алгоритм для раскраски 13
Глава II. Реберная раскраска графа 15
2.1 Раскрытие понятия правильной реберной раскраски графа. 15
2.2 Методы реберной раскраски графа 16
Литература 22
Рассмотрим кольцо R4, состоящее из четырех элементов, которые мы обозначим через 0, 1, ω, ω2. Операция умножения в этом кольце подчиняется закону ω3 = 1, а операция сложения— следующим правилам: z + z = 0 для каждого z R4 и 1+ω + ω2 = 0.
Поскольку каждый элемент из R4 является противоположным самому себе, то циклы и кограницы графа G над кольцом R4 можно рассматривать как цепи в E(G) без указания конкретного ориентанта графа G . Реберные раскраски графа G можно трактовать как всюду ненулевые циклы над R4 если в качестве цветов использовать ненулевые элементы кольца R4.
Рассмотрим следующие теоремы:
Теорема 1. Кубический граф G допускает реберную раскраску тогда и только тогда, когда F(G; 4) > 0.
Теорема 2. Пусть В — бонд графа G, t — реберная раскраска этого графа, пα, nβ и пγ — количество ребер бонда В, которые при раскраске t получают цвет α, β и γ соответственно. Тогда числа па,, пβ и nγ имеют одинаковую четность.
Доказательство. Бонд В является носителем кограницы графа G над R4, все коэффициенты которой равны 1. Эта кограница ортогональна циклу t. Следовательно,
пα α + nββ + пγγ = 0.
Учитывая, далее, правила сложения в кольце R4, получаем утверждение теоремы.
Примером графа, не допускающего реберной раскраски, является, всякий кубический граф, содержащий перешеек.
Пусть, далее, кубический граф G связен и его бонд В имеет торцевые графы Н и К. Предположим сначала, что |В|=2. Преобразуем Н в кубический граф Н1 присоединением нового ребра А1, соединяющего вершины графа Н, являющиеся концами ребер из В. Будем называть Н{ остаточным графом бонда В, содержащим Н; А1 назовем пополняющим ребром. Существует, конечно, и второй остаточный граф бонда В, содержащий К.
Пусть теперь |B| = 3. Построим из G новый кубический граф Н1 заменяя К одной новой вершиной k, инцидентной всем трем ребрам бонда В. Аналогичной заменой графа Н образуем граф К1. Будем называть Н1 и К1 остаточными графами бонда В, содержащими Н и К соответственно.