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

1) найти среди  неокрашенных вершину v наивысшей степени;

2) проверить,  является ли v смежной с какой-нибудь вершиной, уже окрашенной в k-цвет;

3) если нет,  то окрасить v в цвет k;

4) если да, то  исключить v из числа вершин, окрашивающих в цвет k, и вернуться к шагу (1). Этот эвристический метод опирается на рассмотрение вектора d, i-й компонентой которого является степень 1-й вершины. Уильяме модифицирует этот процесс, заменяя для этого вектор d на d_m, где вектор dm определяется последовательно: d₁=d, d_m+1 = Ad_m; здесь через А обозначается матрица смежностей графа G. Вектора d_m при m->∞ сходятся к главному собственному вектору матрицы А. Уильяме замечает, что эта сходимость наступает, вообще говоря, после итераций, где п — число вершин в графе. Уильям применил свой модифицированный метод к раскраске одного графа, содержащего 700 вершин, использовав для этого 28 красок. Заметим, что здесь речь идет не о планарном графе. Позднее было обнаружено, что этот граф содержит полный подграф на 26 вершинах и уже для раскраски такого подграфа нужно 26 цветов. Так что оценка Уильямса, прямо-таки, скажем, не слишком завышена. Как мы уже отмечали, Рингель и Янгс подтвердили гипотезу Хивуда. По мнению Янгса, их совместная работа может быть использована для получения прямых доказательств того, что различные гипотезы, в частности гипотеза 3, эквивалентны гипотезе четырех красок. Есть надежда, что эти методы (графы тока, вихревые графы, закон Кирхгофа) в конечном счете дадут нам новую информацию в этой области, хотя до сих пор они этого еще не сделали.

 

Заключение

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

1. составление расписаний: расписание для образовательных  учреждений; расписание в спорте; планирование встреч, собраний, интервью; расписание транспорта, в том числе - авиатранспорта; расписания для коммунальных служб и т.д.;
2. расчёт сетей ОКС-7 (некое обобщение телефонных сетей); а именно,

раскраска мультиграфа  с некоторыми ограничениями нужна  при маршрутизации пакетов с  учётом равномерной нагрузки;

         3) конструирование устройств, где провода соединённые в одном узле, должны для удобства различения иметь разные цвета;

        4)  распределение исполняемого кода по кешу.

Граф несовместимости  здесь такой: вершины – некие “блоки” кода (можно, например, брать процедуры), рёбра существуют тогда, когда из одного “блока” вызывается другой. Как видно, мы концентрируемся на так называемых конфликтах первого поколения (first-generation cache conflicts) – между “блоком” и её вызывающим/вызываемым. Но стоит отметить, что задача раскраски решается не алгоритмами общего назначения, а специальным эвристическим, который, к тому же, даёт решение, которое удовлетворяет неким дополнительным условиям.

Достоинство этого  метода – в том, что учитываются и размеры кеша, строки кеша, “блоков” кода, и ассоциативность кеша. Метод удачно  комбинируются с другими оптимизациями – но не оптимизатором компилятора, а оптимизатором компоновщика.

Список использованной литературы

1)  Белов В.В. Теория графов [Текст]: учеб. пособие для вузов /- В.В. Белов.- М.: Высш. школа, 1976. – 392 с.

2) Березина Л.Ю.  Графы и их применение [Текст]:пособие для учителей /Л.Ю. Березина– М.: Просвещение, 1979. – 143 с

3)  Гаврилов Г.П. Задачи и упражнения по дискретной математике [Текст]: учеб. пособие./ -Г.П. Гаврилов, А.А. Сапоженко– 3-е изд., перераб. – М.:ФИЗМАТЛИТ, 2006 - 416 c.

4) Делоне. Б.Н. Проблемы современной математики [Текст]: cборник. пер. с англ./- Б.Н. Делоне.- М.: Знание, 1975.-64 c.

5) Уилсон. Р. Введение в теорию графов [Текст]: пер. с англ./- Р. Уилсон.-М.: Мир, 1977.-207 c.

 

 
Приложение

ОПРЕДЕЛЕНИЕ 1: Граф, у которого множество рёбер пусто, называется вполне не связным (или пустым) графом. Будем обозначать вполне несвязный граф с n вершинами через N_n ; N₄ показан на (рис.1). Заметим, что у вполне несвязного графа все вершины изолированы. Вполне несвязные графы не представляют особого интереса.

           рис. 1        

ОПРЕДЕЛЕНИЕ 2: Простой граф, в котором любые  две вершины смежны, называется полным графом. Полный граф с N вершинами обычно обозначается через K_n. Графы K₄ и K₅ изображены на (рис. 2 и 3).

                       

                   рис. 2                      рис. 3

ОПРЕДЕЛЕНИЕ 3: Граф, у которого все вершины имеют одну и ту же степень,  называется регулярным графом. Если степень каждой вершины равна r, то граф называется регулярным степени r. Регулярные графы степени 3, называемые также кубическими (или трёхвалентными) графами (см., например, рис. 2 и 4), представляют особый интерес в связи с задачей раскраски. Другим известным примером кубического графа является так называемый граф Петерсона, показанный на (рис. 5). Отметим что каждый вполне несвязный граф является регулярным степени 0, а каждый полный граф К_n – регулярным степени n – 1.

ОПРЕДЕЛЕНИЕ 4: Среди регулярных графов особенно интересны так называемые платоновы графы – графы, образованные вершинами и рёбрами многогранников – платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра. Граф К₄ соответствует тетраэдру (рис.2); графы, соответствующие кубу и октаэдру, показаны на рис.4 и 6.

                               

                  рис. 4                                          рис. 5

ОПРЕДЕЛЕНИЕ 5: Если множество вершин графа можно разбить на два непересекающихся подмножества V₁ и V₂ так, что каждое ребро в G какую-нибудь вершину из V₁ с какой-либо вершиной из V₂ (рис.7);

 

                                 

рис. 6                          рис.7

тогда G называется двудольным графом. Такие графы иногда обозначают G(V₁, V₂), если хотят выделить два указанных подмножества. Двудольный граф можно определить и по-другому – в терминах раскраски его вершин двумя цветами, скажем красным и синим. При этом граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое ребро имело

                       

                         рис.8                                          рис. 9

 

Один конец  красный, а другой – синий. Следует  подчеркнуть, что в двудольном графе  совсем не обязательно каждая вершина  из V₁ соединена с каждой вершиной из V₂; если же это так и если при этом граф G простой, то он называется полым двудольным графом и обычно обозначается К_{m,n ,}где m и n – число вершин соответственно в V₁ и V₂. Например, на (рис. 8). изображён граф К_4,3, а на (рис. 2.5) – два варианта графа К_3,3. Заметим, что граф К_m,n имеет ровно m + n вершин  и mn рёбер. Полый двудольный граф вида К_1,n называется звёздным графом; на (рис. 9) изображён звёздный граф К_1,5.

Объединение и соединение двух графов. Существует несколько способов соединения двух графов для образования нового, большего графа; проиллюстрируем два из них. Пусть даны два графа G₁ = (V(G₁), E(G₁)) и G₂ = (V(G₂), E(G₂)), причём множества V(G₁) и V(G₂) не пересекаются; тогда объединением G₁ ᴜ G₂ графов G₁ и G₂ называется граф с множеством вершин  V(G₁) ᴜ V(G₂) и семейством рёбер E(G₁) ᴜ E(G₂) (рис.10).  Можно также образовать соединение графов G₁ и G₂ ( обозначаемое G₁+ G₂), взяв их объединение и соединив рёбрами каждую вершину графа G₁   с каждой вершиной графа G₂ . Пример графа   К₁+ К₂ дан на (рис. 11). Заметим, что граф К_m,n можно было бы определить как соединение графов N_m и N_n.

            рис.10

Связные графы. Все графы, рассмотренные нами до сих пор, состояли из “одного куска”. Исключениями были вполне не связные графы N_n (n >=2) и объединения графов, состоящее из “ не соединённых друг с другом частей”. Формализуем это различие,

 

                             

Рис.11 рис. 12

 

Называя граф связным, если его нельзя представить в виде объединения двух графов, и несвязным в противном случае. Очевидно, что всякий несвязный граф G можно представить в виде объединения конечного числа связных графов – каждый из таких связных графов называется компонентой (связности ) графа G. На рис. 12. изображён граф с тремя компонентами).  Доказательство некоторых утверждений для произвольных графов часто бывает удобно сначала провести для связных графов, а затем применить их к каждой компоненте в отдельности.

ОПРЕДЕЛЕНИЕ 6: Связный регулярный граф степени 2 называется циклическим графом (или циклом); циклический граф с n вершинами обозначается через C_n. Соединение графов N₁ и C_n-1 (n>=3) называется колесом с n вершинами и обозначается W_n. На (рис. 13) изображены C₆ и W₆.

                         

                                        рис. 3.13

 

ОПРЕДЕЛЕНИЕ 7: Пусть G – простой граф с множеством вершин V(G). Дополнением G графа G называется простой граф с множеством вершин V(G), в котором две вершины смежны тогда и только тогда, когда они не смежны в G. Отсюда следует, что если граф G содержит n вершин, то граф G c чертой можно построить, удалив из графа К_n все рёбра, принадлежащие G (сдесь G считается подграфом К_n). Заметим, что дополнение полного графа является вполне несвязным графом и наоборот; дополнение регулярного графа регулярно.