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

Министерство  образования и науки Российской Федерации

ФГБОУ ВПО «Ишимский государственный  педагогический институт

им. П.П.Ершова»

 

Кафедра математики, информатики и методики их преподавания

 

 

РАСКРАСКА ГРАФОВ

Курсовая работа

 

 

 

 

Исполнитель:

Игнатьева Валентина Сергеевна

студентка 3 курса дневного отделения

физико-математического  факультета

 

 

Научный руководитель: ассистент

Теплова Валентина  Давыдовна

 

 

 

 

 

 

Ишим 2012

 

Оглавление

 

 

 

 
 

 

Введение

Актуальность. Попытки решить сформулированную в середине 19 века задачу четырех красок привели к появлению некоторых исследований графов, имеющих теоретическое и прикладное значение. Многие результаты середины 19 века, относящиеся к теории графов, были получены при решении практических проблем.  В 20 веке задачи, связанные с графами, начали возникать не только в физике, электротехнике, химии, биологии, экономике, социологии и т.д., но и внутри математики, в таких ее разделах, как алгебра, топология, теория вероятностей, теория чисел и др. Методы этих разделов стали успешно использоваться для решения задач теории графов. 

Наряду с термином граф в начале 20 века употреблялись в качестве синонимов и другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт. 

В проблематике теории графов можно выделить направления, носящие более комбинаторный  или более геометрический характер. К комбинаторным относятся, например, задачи о построении графов с заданными свойствами, задачи о подсчете и перечислении графов с фиксированными свойствами. Геометрический (топологический) характер носят, например, задачи, связанные с обходами графа, и задачи, возникающие при укладке графа на различных поверхностях.  Наряду с проблемами, носящими общий математический характер, в теории графов имеются специфические задачи. Например, изучаются различные свойства связности графа, исследуется строение графа по свойствам связности. При анализе надежности сетей связи, электронных схем, коммуникационных сетей возникает задача о нахождении количеств непересекающихся цепей, соединяющих различные вершины графа. Курсовая работа состоит из трех параграфов. В первом параграфе рассматриваются базовые понятия теории графов, во втором – понятие хроматического числа и хроматического многочлена и в третьем – гипотеза четырёх красок.

Цель курсовой работы – изучить основные понятия теории раскрашивания плоских графов и проанализировать известные результаты о гипотезе четырех красок.  Достижению данной цели курсовой работы были поставлены и решены следующие задачи:

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

Объект – плоский граф.

Предмет – условия раскраски графов и его практическое применение.

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

 

 

 

 

 

 

 

 

 

 

 

§1. Введение в теорию графов

 

Рассмотрим  сначала рисунок 1.1. и 1.2. на которых изображены соответственно участок электрической цепи и часть карты дорог. Ясно, что оба эти рисунка могут быть представлены одной и той же диаграммой из точек и линий, изображённой на рисунке 1.3.

Точки P,Q,R,S,T называются вершинами, линии называются рёбрами, а вся диаграмма называется графом. (Заметим, что точка пересечения линий PS и QT не относятся к вершинам графа, так как она не является ни общей точкой двух проводов, ни перекрёстком дорог).

Степенью вершины называется число рёбер, концом которых является эта вершина; на рисунке 1.2. это соответствует числу дорог, сходящихся у перекрёстка;  так, степень вершины Q равна 4.

Очевидно, что граф, изображённый на рисунке 1.3, может описывать и другие ситуации. Например, если обозначить через P,Q,R,S,T футбольные команды, то наличие ребра между двумя вершинами можно трактовать как состоявшуюся встречу соответствующих двух команд (так согласно рис. 1.3, команда P уже сыграла с S, но ещё не сыграла с R); в этом случае степенью вершины будет число матчей, сыгранных соответствующей командой.

Рассмотренные выше ситуации можно описать и другим графом, изображённым на рис 1.4. Здесь мы устранили

 

 

          

                 рис. 1.1                              рис. 1.2

 

         

         рис. 1.3                                рис. 1.4

 

 “пересечение” линий PS и QT, проведя линию PS вне прямоугольника PQST. Заметим, что полученный при этом граф по-прежнему даёт нам представление о том, как соединены провода в электрической цепи, есть ли прямая дорога от одного перекрёстка к другому и какие футбольные команды встречались друг с другом; потеряна только информация, касающаяся “метрических” свойств (длина дороги, прямолинейность провода и т.д.) их соединения и что для наших целей метрические свойства несущественны. Исходя из этого, любые два графа, которые представляют одну и ту же ситуацию (как, например, графы, изображённые на рисунке 1.3 и 1.4.) будут считаться по существу одинаковыми. Более точно, мы будем говорить, что два графа изоморфны, если существует взаимно однозначное соответствие между их вершинами, обладающее тем свойством, что две вершины соединены ребром в одном графе тогда и только тогда, когда соответствующие им вершины соединены ребром в другом. На рисунке 1.5. изображён ещё один граф, изоморфный двум предыдущим. Заметим, что в графе представления о пространстве и расстояниях совершенно искажены, хотя, как и раньше, можно сразу сказать, какие точки соединены проводом или дорогой.

Стоит отметить, что граф, о котором шла речь до сих пор, “простой” в том  смысле, что в нём любую пару вершин соединяет не более чем одно ребро. Предположим теперь, что дороги от Q  до S и S до T (рис. 1.5.) слишком загружены и для их разгрузки проложены параллельные дороги, соединяющие те же точки; тогда соответствующая диаграмма будет выглядеть, как на рисунке 1.6. (Рёбра, соединяющие Q c S или S c T, называются кратными.) Если к тому же мы хотим построить гараж в пункте P, то на диаграмме это можно отметить ребром, идущим из P в P; такое ребро обычно называют петлёй (рис. 1.7).

А что получится, если по каждой из дорог, возможно, только одностороннее движение? Задавшись таким вопросом, мы придём к рассмотрению ориентированных графов (или, сокращённо, орграфов) Пример орграфа дан на рисунке 1.8; направления движения указаны стрелками (в этом конкретном случае в пункте Т творилось бы нечто несусветное, но это не помешает нам исследовать и такие ситуации). Заметим что если не все дороги односторонние, то можно получить соответствующий орграф, сопоставляя дороге с двусторонним движением два противоположно ориентированных ребра.

Много внимания уделяется в теории графов изучению различного рода цепей; под  цепью понимается последовательность идущих друг за другом рёбер. Так, например, на рисунке 1.5 один из способов попасть из P в R описывается цепью P→Q→R  длины 2; анологично,  P→S→Q→T→S→R  есть  цепь длины 5. По очевидным соображениям цепь вида Q→S→T→Q  нызывается циклом.

           

                     рис. 1.5   рис. 1.6

В общем случае не всегда можно найти цепь, связывающую  две данные вершины ᴠ и ᴠᴠ рассматриваемого графа P R T Q S (см. рис.1.9);

 

         

              рис. 1.7 рис. 1.8

такая цепь будет  существовать, только если  граф состоит  как бы из одного куска. Для большей  ясности рассмотрим пример графа, вершины  которого соответствуют станциям лондонского и нью-йорского метрополитенов, а рёбра-линиям, соединяющим станции между собой. Совершенно очевидно, что по рёбрам этого граф невозможно попасть со станции Черинг Кросс в Лондоне на Гранд Централ Стейшн в Нью-Йорке.

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

Граф,в котором любые  две вершины соединины  цепью, называется связным графом.

              

рис. 1.9

Дадим сначала  определение простого графа G_w.

Пара (V(G), E(G)) называется простым графом, если V(G)- непустое конечное множество элементов, называемых вершинами (или узлами, или точками), а E(G)- конечное множество неупорядоченных пар различных элементов из V(G), называемых рёбрами (или линиями). Иногда V(G) называют множеством вершин, а E(G)-множеством рёбер графа G.

Например, на рисунке 1.10 изображён простой граф G, у которого множеством вершин V(G) является множество {u,v,w,z}, а множество рёбер E(G) состоит из пар {u,v}, {v,w}, {u ,w} и {w,z}. Говорят, что ребро {v, w} соединяет вершины v и w. Отметим, что, так как E(G) является множеством, а не совокупностью элементов, где некоторые элементы могут встречаться несколько раз; например, {a,b,c} – множество, тогда как {a,a,a,b,c,c} – семейство, то в простом графе данную пару вершин может соединять не более чем одно ребро.

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

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

               

               рис. 1.10         рис. 1.11

 

Получающийся  при этом объект в котором могут  быть петли и кратные рёбра, называется общим графом, или просто графом (рис. 1.11). Подчеркнём тот факт, что каждый простой граф является графом, но не каждый граф является простым графом.

Более точно, графом G называется пара (V(G), E(G)), где V(G) – непустое конечное множество элементов, называемых вершинами, а E(G) – конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых рёбрами. Заметим, что употребление слова “семейство”  говорит о том, что допускаются кратные рёбра. Будем называть V(G) множеством вершин, а E(G) – семейством рёбер графа G; на рисунке 1.11, V(G) – это множество {u,v,w,z}, а E(G)- это семейство, состоящее из рёбер {u,v},{v,v},{v,v},{v,w},{v,w},{v,w},{u,w},{u,w} и {w,z}. О каждом ребре вида с собой.

Предметом изучения в теории графов являются также ориентированные  графы (называемые орграфами или сетями; однако мы будем употреблять слово “сеть”  в несколько ином смысле). Орграфом D называется пара (V(D), A(D)), где V(D) – непустое конечное множество элементов, называемых вершинами, а A(D) – конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами). Дуга, у которой вершина v  является первым элементом, а вершина w – вторым, называется дугой из v в w и обозначается (v,w). Заметим, что дуги (v,w) и (w,v) различны. На рисунке 1.12 изображён орграф, дугами которого являются (u ,v), ( v ,v), (v ,w), (v ,w), (w ,v), (w ,u) и (w,z); порядок вершин на дуге указан стрелкой.

                          рис. 1.12

Некоторые специалисты  по теории графов называют графом то, что  мы называли простым графом. Во многих случаях,  и особенно в приложениях, под графом понимается орграф. Ещё  хуже, иногда графом называют объект, который получается, если снять условие конечности множества вершин или семейства рёбер. (Если оба они бесконечны, мы называем соответствующий объект бесконечным графом). Следует подчеркнуть, что любое из перечисленных определений графа вполне допустимо, если только пользоваться им последовательно.

Прежде чем привести примеры  некоторых важных типов графов, удобно дать несколько простых определений.

Две вершины v и w графа G называются смежными, если  существует соединяющее их ребро (т. е. ребро вида {v,w}); при этом вершины v и w называются инцидентными этим вершинам). Аналогично, два различных ребра графа G называются смежными, если они имеют, по крайней мере одну общую вершину. Степенью (или валентностью) вершины v графа G называется число рёбер, инцидентных v; степень вершины v обозначается через p(v). При вычислении степени вершины v договоримся учитывать петлю в v два раза, а не один (если только явно не сказано иное). Вершина степени 0 называется изолированной вершиной, вершина степени 1 называется висячей (или концевой) вершиной. Так, граф, изображённый на рисунке 1.11, имеет одну висячую вершину, одну вершину степени 3, одну – степени 6 и одну – степени 8. Легко видеть, что если сложить степени всех вершин графа, то получится чётное число – равное удвоенному числу рёбер, так как каждое ребро участвует в этой сумме ровно два раза. Этот результат, известный ещё двести лет назад Эйлеру, часто называется леммой о рукопожатиях. Из неё следует, что если несколько человек обменялись рукопожатиями, то общее число пожатых рук обязательно чётно, ибо в каждом рукопожатии участвуют две руки (при этом каждая рука считается столько раз, сколько она участвовала в рукопожатиях). Из леммы о рукопожатиях сразу следует, что в любом графе число вершин нечётной степени должно быть чётным.

Два графа G₁ и G₂ называются изоморфными, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число рёбер, соединяющих любые две вершины в G₁ , равно числу рёбер, соединяющих соответствующие вершины в  G₂. Так, два графа, изображённые на рисунке 1.14, изоморфны при соответствии u ↔ l, v  ↔ m, w  ↔ n, x  ↔ p, y   ↔ q, z  ↔ r. Заметим, что эти графы имеют по шесть вершин – другие точки пересечения рёбер вершинами не являются. u₁ u₂ u₃ u₄

              

          рис. 2.4

 

                      

                                            рис. 2.5

 

           Подграфом графа G называется граф, все вершины которого принадлежат V(G), а все рёбра принадлежат E(G).  Так, граф на (рис. 1.10) является подграфом графа, изображённого на рисунке 1.13, но не является подграфом ни одного из графов, приведённых на рисунке 1.14 (так как последние не содержат “треугольников”).

Наконец, матрицей смежности графа G с множеством вершин {v₁,…,v_n} (соответствующей данной нумерации вершин) называется матрица  A=(a_ij) размера n*n, в которой элемент a_ij равен числу рёбер в G, соединяющих v_i и v_j. Например, на рисунке 1.15 дана матрица смежности графа, изображённого на рисунке 1.13. Можно получить несколько различных матриц смежности данного графа, меняя обозначения его вершин; это приведёт к изменению порядка строк и столбцов матрицы А. Но в результате всегда получится симметричная матрица из неотрицательных чисел,