Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Связность ориентированных графов

Определение.Ориентированный граф G связен, если неориентированный граф, получающийся из G путем удаления ориентации ребер, является связным.

Определение.Ориентированный граф сильно связен, если для каждой пары вершин i и j существует по крайней мере один путь из i в j и по крайней мере один путь из j в i.

Определение.Максимальный сильно связный подграф орграфа называется сильно связной компонентой.

 

На рисунках 20 – 222 изображены несвязный, связный, но не сильно и сильносвязный графы соответственно.

Циклы

Эйлеров цикл

Определение. Эйлеров цикл — цикл, который проходит ровно один раз по каждому ребру (дуге) графа.

Определение.Если граф имеет цикл, содержащий все ребра (дуги) графа по одному разу, то граф называется эйлеровым.

Не все графы имеют эйлеровы циклы, но если эйлеров цикл существует, то это означает, что, следуя вдоль этого цикла, можно нарисовать граф на бумаге, не отрывая от нее карандаша.

 

 

Граф, изображенный на рисунке 23 является эйлеровым. Задача о Кенегсбергских мостах, рассмотренная выше предполагает нахождение эйлерова цикла в мультиграфе.

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

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

1. Докажем прямую теорему.

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

2. Докажем обратную теорему (способ доказательства – конструктивный, то есть дает алгоритм построения эйлерова цикла).

Пусть все вершины графа имеют четную степень. Будем строить эйлеров цикл, начиная с некоторой вершины v0, при этом пройденные ребра будем удалять. Так как все вершины имеют четную степень, то, попав в какую-либо вершину, обязательно найдем ребро, по которому можно из неё выйти. Таким образом, обязательно вернемся в вершину v0, получив при этом некоторый цикл Р. Если при этом все ребра графа участвуют в цикле, то теорема доказана.

В противном случае, так как граф связен, обязательно найдется ребро не входящее в цикл, но инцидентное какой-либо вершине цикла. Обозначим эту вершину v1. Будем строить цикл начиная с вершины v1. Из аналогичных соображений мы обязательно вернемся в вершину v1, получив цикл Р1. Если при этом все ребра графа присутствуют в циклах Р и Р1, то цикл v1Рv1Р1v1 содержит все ребра графа по одному разу, то есть является эйлеровым, следовательно, теорема доказана. В противном случае продолжаем аналогичные рассуждения. Так как ребер в графе конечное количество построение цикла обязательно закончится.

Теорема. Связный орграф является эйлеровым тогда и только тогда, когда полустепень исхода каждой вершины равна полустепени ее захода.

Доказательствоаналогично случаю неориентированного графа.

Гамильтонов цикл

Определение.Граф называется гамильтоновым, если в нем имеется цикл, содержащий каждую вершину этого графа.

Уильям Роуэн Гамильтон выпустил головоломку, суть которой состояла в построении пути, который через каждую вершину проходит по одному разу. Задача похожа на задачу о нахождении эйлеровой линии, однако до сих пор не найдены необходимые и достаточные условия существования в графе гамильтоновых линий.

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

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

Например, на рисунках 18 и 22 – изображены гамильтоновы графы, а на рисунках 21 и 23 графы, не являющиеся гамильтоновыми.

РўСѓСЂРЅРёСЂС‹

Определение.Граф называется полугамильтоновым, если существует маршрут, содержащий каждую его вершину ровно один раз.

Определение.Турнир (полный ориентированный граф) – орграф, в котором любые его две вершины соединены ровно одной дугой.

Этот класс графов получил свое название в связи со спортивными турнирами без ничьих, проводимых по круговой системе. Результаты встреч можно описать орграфом, вершины которого соответствуют участникам соревнований, а дуга (v ,w) есть в графе, если участник, соответствующий вершине v, выиграл у участника, соответствующего вершине w.

На рисунке 24 изображен не сильносвязный турнир, а на рисунке 25 – сильносвязный.

Теорема. Любой турнир полугамильтонов.

Доказательство (метод математической индукции по количеству вершин). Если турнир имеет меньше четырех вершин, то утверждение, очевидно, верно. Проведем индукцию по числу вершин. Предположим, что любой турнир с n вершинами полугамильтонов. Пусть Т — турнир с n+1 вершинами, и пусть турнир Т’ с n вершинами получен из Т удалением некоторой вершины о вместе со всеми инцидентными ей дугами. Тогда но предположению индукции Т’ обладает полугамильтоновым маршрутом

Рассмотрим три случая.

(1) Если {v, v1) — дуга в T, то искомой простой орцепью является

(2) Если (v, v1) не является дугой в Т (это означает, что дугой является (v1, v)) и если существует такое i, что (v, vi) -дуга в T, то, выбирая первое i с таким свойством (см. рис. 26), получим, что искомым маршрутом является

Р РёСЃ. 26

(3) Если в Т не существует дуги вида (v,vi), то искомым маршрутом является

Теорема. Любой сильно связный турнир гамильтонов.

Доказательство (метод математической индукции по длине цикла). Докажем белее сильный результат ,состоящий в том, что сильно связный турнир Т с n вершинами содержит циклы длины 3, 4, … n.

Докажем, что существует цикл длины три. Пусть Т – сильно связный турнир. Тогда для любой вершины v из Т все множество дуг ей инцидентных можно разделить на два не пересекающихся подмножества W – множество дуг для которых вершина v является концом и Z – множество дуг для которых вершина v является началом. Так как Т сильно связен, то оба этих множества не пусты, следовательно найдутся вершины w принадлежащая W и z принадлежащая Z, тогда имеем цикл v, w , z, v длины три.

Предположим, что существуют циклы длины меньшей или равной k – v1, v2, …,vk. Докажем, что существует цикл длины к. Возможны два случая:

1. Существует вершина v, у которой есть инцидентные дуги, направленные к циклу и направленные из цикла. Тогда находим первую дугу, направленную к циклу, пусть это будет дуга (v, vi). Тогда искомый цикл имеет вид: v1, v2, …vi-1, v, vi,…,vk.

2. Для любой вершины графа все дуги направлены либо к циклу, либо из цикла. Тогда все множество вершин, не входящих в цикл можно разделить на два непересекающихся подмножества W – множество вершин у которых все дуги направлены к циклу и Z – множество вершин у которых все дуги направлены из цикла. Так как Т сильно связен, то оба этих множества не пусты, следовательно найдутся вершины w’ принадлежащая W и z’ принадлежащая Z, тогда имеем цикл v1, w',z',v3, …,vk. длины k+1 (см. рис. 27).

Р РёСЃ. 27

Деревья

Определение. Лесом называют граф без циклов.

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

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

Р РёСЃ. 28

Удобно считать, что граф, состоящий из одной изолированной вершины, тоже является деревом.

Определение. Вершина дерева, степень которой равна единице, называется висячей вершиной или листом.

Свойства деревьев

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

2. Удаление всякое ребра в дереве приводит к увеличению числа компонент связности.

3. Дерево с p вершинами всегда имеет (p-1) ребер.

  1. Если G - лес, р - вершин и к компонент связности, то G имеет р-к ребер.
  2. В каждом дереве существует по крайней мере две висячие вершины.

Доказательство свойств деревьев предлагается читателю в качестве упражнений.

Определение. Для произвольного СЃРІСЏР·РЅРѕРіРѕ неориентированного графа G(V,E) каждое дерево Р Сћ(V1,T1), Р С–Р Т‘Р Вµ V1=V Р С‘ Р•1ÍE, называют стягивающим деревом (каркасом, остовом). Ребра такого дерева называют ветвями, Р В° остальные ребра графа - хордами.

На рисунке 29 приведен пример графа и его каркасов.

Р РёСЃ. 29

 

На рисунке 30 представлены граф и его каркасы, построенные методами поиска в глубину и в ширину. В круглых скобках указана очередность просмотра вершин графа при соответствующем поиске.

Р РёСЃ. 30

Планарные графы

Во многих случаях не имеет значения, как изобразить граф, т.к. изоморфные графы несут одну и ту же информацию. Но встречаются ситуации, когда важно выяснить, возможно ли нарисовать граф на плоскости так, чтобы его изображение удовлетворяло определенным требованиям. Например, в радиоэлектронике при изготовлении микросхем печатным способом электрические цепи наносятся на плоскую поверхность изоляционного материала. Так как проводники не изолированы, то они не должны пересекаться. Аналогичная задача возникает при прокладке железнодорожных и других путей, где не желательны переезды.

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

Определение. Граф, изоморфный плоскому, называется планарным.

Граф К4 (рис. 31) – планарен, ему соответствуют плоские графы, изображенные на рисунках 32 и 33.

 

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

Ниже на рисунке 34 изображен граф с четырьмя гранями.

Р РёСЃ. 34

Заметим, что грань 4 не ограничена, такую грань называют внешней, все остальные грани называют внутренними.

Теорема (Формула Эйлера).Пусть G - связный планарный граф. Тогда справедливо следующее p-q+r=2, где p - количество вершин, q - количество ребер, r - количество граней.

Доказательство (методом математической индукции по количеству ребер). При q=0 теорема верна. Очевидно, что если q=0, то p=1 и r=1, тогда p-q+r=2.

Пусть теорема верна для всех графов с q ребрами: p-q+r=2. Добавим еще одно ребро. Если добавляемое ребро соединяет существующие вершины, то q1=q+1, p1=p, r1=r+1 и p1-q1+r1=p-(q+1)+r+1= p-q+r=2. Если добавляемое ребро соединяет существующую вершину с новой, то q1=q+1, p1=p+1, r1=r и p1-q1+r1=p+1-(q+1)+r= p-q+r=2.

Теорема.Если G - связный планарный граф РЎРѓ РЎР‚ вершинами Р С‘ q ребрами Р С‘ p>3, то q£3p-6.

Доказательство.Так как каждая грань ограничена Р С—Р С• крайней мере тремя ребрами, каждое ребро ограничивает Р Р…Р Вµ более РґРІСѓС… граней, то 3r£2q. Из формылы Эйлера следует ,что 2=p-q+r, тогда 2£p-q+2/3q, следовательно 3p-3q+2q³6, тогда q£3p-6

Теорема.Граф К5 не является планарным.

Доказательство.Предположим противное, граф планарен. РўРѕРіРґР° p=5, q=4*5/2=10, Р С—Р С• формуле Эйлера r=7. РўРѕРіРґР° Р Р…Р Вµ выполняется условие предыдущей теоремы q£3p-6, Р В° значит, наше предположение Р Р…Р Вµ верно граф Р Р…Р Вµ является планарным.

Теорема.Граф К3, 3 не является планарным.

Доказательство.Предположим противное, граф является планарным. РўРѕРіРґР° p=6, q=9, Р С—Р С• формуле Эйлера r=5. Р’ данном графе нет треугольников, следовательно, если РѕРЅ планарен, то Р Р† его плоской укладке каждая грань ограничена Р С—Р С• крайней мере 4 ребрами. Таким образом, 4r£2q, 2r£q. Р СњР С• полученное условие для нашего графа Р Р…Р Вµ выполняется, Р В° значит, наше предположение Р Р…Р Вµ верно граф Р Р…Р Вµ является планарным.

Теорема.В планарном графе существует вершина степени не больше пяти.

Доказательство.Предположим противное, степень любой вершины графа Р Р…Р Вµ менее шести. РўРѕРіРґР° СЃСѓРјРјР° степеней всех вершин Р Р…Р Вµ менее 6*РЎР‚, следовательно Р С—Р С• лемме Р С• рукопожатиях 2q³6p, отсюда p£q/3. Так как q£3p-6, получим q£q-6. Таким образом получили противоречие, значит, наше предположение Р Р…Р Вµ верно, Р Р† планарном графе обязательно должна быть вершина степень которой меньше шести.

Определение. Элементарным стягиванием называется следующая процедура: берем ребро е (вместе с инцидентными ему вершинами u, v) и “стягиваем ” его, то есть удаляем е и отождествляем вершины u и v; полученная при этом вершина инцидентна тем ребрам (отличным от е), которым первоначально были инцидентны вершины u и v.

Ниже на рисунке 35 представлены два графа: до и после процедуры элементарного стягивания ребра е.

СЂРёСЃ. 35

Определение. Граф G называется стягиваемым к графу H, если Н можно получить из G с помощью некоторой последовательности элементарных стягиваний.

Теорема Куратовского.Граф является планарным тогда и только тогда, когда в нем нет подграфов, стягиваемых к графам К5 или К3,3.

Раскрашивание графов

Определение. Произвольная функция f:V®{1,2,...,k}, где k принадлежит множеству натуральных чисел, называется вершинной k-раскраской графа G(V,E).

Определение.Раскраска называется правильной, если f(u)¹f(v), для любых смежных вершин u Р С‘ v.

Определение.Граф, для которого существует правильная k-раскраска, называется k-раскрашиваемым.

Определение.Минимальное число k, при котором граф G является k-раскрашиваемым, называется хроматическим числом графа и обозначается c(G).

 

СЂРёСЃ. 36

Для графа на рисунке 36 c(G)=3. Меньшим количеством цветов граф правильно раскрасить нельзя из-за наличия подграфов К3. Рядом с вершинами графа - указаны номера цветов.

Раскраска планарных графов

Проблема раскраски планарных графов является одной из самых знаменитых проблем теории графов. Первоначально вопрос формулируется следующим образом: достаточно ли четырех красок для такой раскраски произвольной географической карты, при которой соседние страны окрашены в различные цвета? В 1879 г. британский математик А. Кэли выдвинул гипотезу четырех красок: «Всякий планарный граф вершинно 4-раскрашиваем.» Гипотеза четырех красок привлекала внимание многих исследователей. Уже в 1880 г. появилось первое доказательство А.Кемпе. Ошибка в этом доказательстве была обнаружена Р. Хитвудом в 1890 г. Одновременно он показал, что если в формулировке гипотезы слова “четыре” заменить на “пять”, то полученная теорема легко доказывается.

Теорема.о пяти красках.Всякий планарный граф 5-раскрашиваем.

Доказательство (метод математической индукции по количеству вершин). Для планарных графов, у которых меньше шести вершин теорема очевидна.

Предположим, что G планарный граф с n вершинами, и что все планарные графы с n-1 вершинами 5-раскрашиваемы. Можно считать, что G плоский граф, и что он содержит вершину v, степень которой не больше пяти. Удаление вершины v и всех инцидентных ей ребер приводит нас к графу с n-1 вершиной, который, по предположению индукции 5-раскрашиваем, раскрасим его. Тогда в исходном графе G останется окрасить только одну вершину v.

Если степень вершины v меньше пяти, то ее можно окрасить в любой цвет, не участвующий в окраске смежных с ней вершин.

Пусть степень вершины v равна пяти. Если среди смежных вершин есть две вершины одинакового цвета, то ее можно окрасить в цвет, не использованный для окраски этих вершин.

Итак, остался последний случай: всем вершинам, смежным с v присвоены различные цвета. Обозначим вершины, смежные с v через v1,v2,...,v5. Пусть они окрашены в цвета c1,c2,...,c5. Определим H(i,j) как подграф графа G, вершинами которого являются все вершины цвета ci или cj, а ребрами - все ребра, соединяющие вершину цвета ci с вершиной цвета cj. Рассмотрим два случая.

1). v1 и v3 не принадлежат одной компоненте связности графа H(1,3). В этом случае можно поменять цвета всех вершин той компоненты H(1,3), которая содержит v1 (цвет с1 на цвет с3, а цвет с3 на цвет с1). В результате v1 приобретет цвет c3, что позволит окрасить v в цвет c1.

2). v1 и v3 принадлежат одной компоненте связности графа H(1,3). В этом случае существует цикл C вида v->v1->..->v3->v, часть которого, заключенная между v1 и v3 целиком лежит в H(1,3). Так как v2 находится внутри цикла C, а v4 - вне его, то не существует простой цепи из v2 в v4, целиком лежащей в H(2,4). Поэтому v2 и v4 принадлежат разным компонентам связности графа H(2,4). В этом случае можно поменять цвета всех вершин той компоненты H(2,4), которая содержит v2 (цвет с2 на цвет с4, а цвет с4 на цвет с2). В результате v2 приобретет цвет c4, что позволит окрасить v в цвет c2.

Таким образом, все вершины исходного графа можно окрасить в 5 цветов, что и требовалось доказать.

Список литературы

  1. Асанов М. О., Баранский В. А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. – Ижевск, 2001.
  2. Ахо А., Хокпкрофт Дж., Ульман Дж.Структуры данных и алгоритмы. – М.: Издательский дом «Вильямс», 2001.
  3. Бадин Н.М., Волченков С.Г., Дашниц Н.Л., Корнилов П.А. Ярославские олимпиады по информатике. – Ярославль, 1995.
  4. Виленкин Н.Я. Комбинаторика. – М.: Наука, 1969.
  5. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990.
  6. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. – М.: Лаборатория базовых знаний, 2002.
  7. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978.
  8. Майника Э. Алгоритмы оптимизации на сетях и графах. – М.:Мир,1981.
  9. Мельников О.И. Занимательные задачи по теории графов. – Минск.: Тетрасистемс, 2001.
  10. Новиков Ф.А. Дискретная математика для программистов. – СПб.:Питер, 2001.
  11. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. – М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2002.
  12. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.
  13. Харари Ф. Теория графов. – М.: Мир,1973.
  14. Шапорев С.Д. Дискретная математика. –СПб:БХВ-Петербург, 2007
  15. Яблонский С.В. Введение в дискретную математику. – М.: Высш. шк., 2002.

 

12

Последнее изменение этой страницы: 2016-08-28

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...