ivanstudent

Путь к Файлу: /Дискретная математика. Часть 2 / 189 / 5.DOC

Ознакомиться или скачать весь учебный материал данного пользователя
Скачиваний:   1
Пользователь:   ivanstudent
Добавлен:   24.12.2014
Размер:   562.0 КБ
СКАЧАТЬ

R(E+R)lо=R(E+R)lo+1

 и эта матрица транзитивная и можно

S=R(E+R)lо.

Следствиями из доказанной теоремы полагаются следующие утверждения - в классе всех неориентированных униграфов каждый граф обладает единственным транзитивным замыканием.

4.2. Бикомпоненты графа

Говорят, что в орграфе L=(X,U,P) вершина Y достижима из вершины Х если существует путь из Х в Y. Высказывание «Y достижима из X в L» будет обозначать Д(X,Y).

Вершины Х и Y в L взаимодостаточны, если истинно Д(X,Y)& Д(Y,X). Отношение взаимодостижимости рефлексивно, симметрично и транзитивно, поэтому множество Х разбивается на попарно непересекающиеся подмножества взаимодостижимых вершин подграфа. Порождаемые этим подмножеством называются компонентами бисвязности  (бикомпонентами). И их количество обозначается через 5. При5=1 граф называется бисвязным.

 

 
5

Пример 4.2.1. Граф на рисунке 4.2.1. имеет три компоненты бисвязности – они порождаются множествами вершин {a,b,c}, {d,l},{f}. Если направление  дуги изменить на противоположное, то граф станет бисвязным.

Пусть граф задан матрицей смежности R над B{0,1}. Элемент матрицы Sij(l) матрицы (E+R)2 равен 1 тогда и только тогда, когда из i-ой вершины графа в в j - вершину существует путь длины не более l. Существует также l, что (E+R)lo=(E+R)lo+ , причём  Sij(lо) равен 1 в том и только в том случае, если j - ая вершина достижима из i-ой. Тогда каждая бикомпонента состоит из тех вершин, которым в матрице (E+R)lo отвечают одинаковые строки.

 

 

 

 

Пример 4.2.2. Для графа на рис. 4.2.1 имеем

 

             5

 

                                   5

Теорема Камьона-Фаулькса. Полный обыкновенный орграф обладает гамильтоновым циклом тогда и только тогда, когда он бисвязен.

Теорема Редеи. Всякий плотный орграф имеет хотя бы один гамильтонов путь.

4.2.1. Базы вершин. Ядра

Множество 5называется базой вершин орграфа L=(X,U,P), если

5

т.е. множество L  вершин достижимых из вершины Z. Иными словами, всякая из вершин достижима хотя бы из одной вершины Z множества X , но различные вершины множества Z недостижимы друг из друга.

Бикомпоненту Li=(Xi,Ui,P) орграфа L=(X,U,P) назовём базовой, если в неё не заходит извне ни одна дуга.

Базовые бикомпоненты можно найти по «установившейся» матрице  (E+R)lo: её столбец отвечает вершине из базовой компоненты тогда и только тогда, когда он не поглощает (при сложении) никакой другой столбец с меньшим числом единиц; иначе - если строка не поглощается никакой строкой с большим числом единиц.

Лемма. Всякий орграф имеет по крайней мере одну базовую компоненту.

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

Следствие 1. Все базы вершин одного и того же орграфа обладают одинаковым числом вершин.

Следствие 2. Для единственности базы вершин орграфа необходимо и достаточно, чтобы каждая его базовая бикомпонента была одновершинной.

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

Обозначим 5 отображение, относящее каждому не пустому подмножеству 5некоторое подмножество5 5, т.е.5 

Множество 5 называется положительным ядром орграфа L, если 5; аналогично множество 5 есть отрицательное ядро, если 5.

Иначе определения для N+ и N - имеют вид:

5

и

5

Пример 4.2.3. Граф L1 на рисунке 4.2.2.обладает как положительным, так и отрицательным ядром, граф L2 - двумя ядрами, каждое из которых одновременно и положительное, и отрицательное, граф L3 - положительным ядром, а граф L4 не имеет ядер.

5
 

 

 

 

 


                L1                            L2                                L3                                L4

Рис. 4.2.2

Изменение ориентации всех дуг орграфа на противоположную превращает все положительные ядра в отрицательные и наоборот.

Пример 4.2.4. Пусть Х множество решений, каждое из которых может быть принято в некоторой ситуации. Выбор одного из этих решений поручен группе экспертов, каждый из которых имеет своё мнение о взаимной предпочтительной в отношении каждой пары решений. Считаем, что решение Х эффективно, но предпочитается решению Y, если часть экспертов, считая Х лучше Y, имеет возможность добиться того, чтобы угодная им точка зрения одержала верх. Однако, если другая часть экспертов (может быть и частично совпадающая с первой) считает, что Y лучше Z и может добиться принятия решения Y(т.е. Y эффективно предпочитается Z), то может быть, что  Х эффективно не предпочитается Z: отношение эффективного предпочтения не транзитивно.

Введём в рассмотрение граф Бержа с множеством вершин Х, считая за Гх множество решений эффективно предпочитаемых решению Х.

Пусть N- - отрицательное ядро графа (если оно существует); Он Нейман и Моргенштерн предполагают ограничиться рассмотрением решений, соответствующих вершинам из N-. В обоснование этого предложения заметим, что никакое решение из N- не может эффективно предпочитаться какому-либо решению из N-, а это обеспечивает известную сплочённость; с другой стороны любое решение 5 - эффективно предпочитается некоторое решение из N-, в силу чего Х сразу отвергается.

 

4.2.2. Алгоритм Рудяну нахождения ядер графа

Алгоритм основан на следующей теореме.

Теорема. Подмножество 5 вершин орграфа  L=(X,U,P) является его положительным ядром тогда и только тогда, когда выполняются следующие три условия:

1.5

2.5

3. множество N\E+ есть положительное ядро подграфа L’=(X’,U,P), где  5

Для отрицательных ядер справедлива двойственная теорема.

Здесь 5 - множество всех тупиков графа L. 5- множество всех анти- тупиков L.

Доказательство. Пусть N-произвольное подмножество YX, удовлетворяющее условиям 1 и 2, а  N’=N\E+

5Ясно, что (рис. 4.2.3)

5

Если N удовлетворяет, кроме 1 и 2, также условию 3, т.е. 5, то 5, а это означает, что N является положительным ядром графа L.

Наоборот, если N положительное ядро L, т.е. 5, то условие 1 и 2, очевидно выполнены, поэтому 5 иначе N  положительное ядро L. При 5 теорема вырождается в тавтологию.

Пример 4.2.5. Найти ядро графа, изображённого на рисунке 4.2.4

5

Рис. 4.2.4

 

Начнём с положительных ядер. Прежде всего

5

В подграфе L’, полученном из L пополнением вершин 4 и 11, имеем

5.

Удаляя из L’ вершины  1,5,2, и 6, получим L’’, у которого

5.

5

Наконец, удаление из L’’ вершин 3 и 8 даёт граф L’’ без антитупиков (рис. 4.2.5).

Рис. 4.2.5

Визуально находим в L’’ два положительных ядра: {9} и {7,12}. Согласно теореме в L’’ положительными ядрами являются {3,9}и {3,7,12}, в L {1,3,5,9} и {1,3,5,7,12}, а в исходном графе L N1+={1,3,5,9,11} и N2+={1,3,5,7,11,12}

Для отрицательных ядер аналогично имеем

5.

В подграфе L’, после удаления вершин 8,3,7,10:

5

и т.д. Окончательно получим N-={2,4,8,12}.

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

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

 

Говорят, что дано гомоморфное отображение (гомоморфизм) 5 графа L=(X,U,P) в граф L’=(X’,U’,P’), если каждой вершине 5 и каждому ребру 5графа L однозначно отнесены их образы 5 и 5 в L’ с сохранением инцидентности, т.е.

5

Из определения гомоморфизма ясно, что он не обязательно сохраняет тип рёбер, так, если две различные вершины 5 имеют один образ 5переходят в петли. Вообще при гомоморфизме дуга может перейти в дугу, звено или петлю, а петля - только в петлю. Поэтому, есть частный случай гомоморфизма: отображение 5тождественно как на Х, так и на U, а образом графа L=(X,U,P) служит соответствующий неограф 5.

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

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

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

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

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

Другое представление раскраски вершин заключается в том, что вершине X  графа L=(X,U,P) относится целое неотрицательное число q(x) с соблюдением условия.

5

при этом q(x) = 0 означает, что вершина х не окрашена, а при q(x)=i>0 число i можно рассматривать как номер той вершины графа F, в которую отображена  х.

Наконец, раскраска вершин равносильна выделению L некоторой системы попарно непересекающихся  пустых подграфов.

Если раскраска графа L является отображением на F, то имеем раскраску n(F) цветами. Раскраска называется полной, если окрашены все те вершины, при которых нет петель. Наименьшее количество цветов, достаточное для полной раскраски вершин графа называется хроматическим числом и обозначается 5.

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

Очевидно, что если L1,L2,...,Lx  - компоненты графа L, то

5.

Известны следующие оценки хроматического числа графа:

1. 5- тривиальная оценка через число вершин;

2. 5- где 5плотность графа;

3. Оценка Брукса:5, где 5степень графа:

5.

Полную раскраску вершин графа L=(X,U) в 5цветов будем называть минимальной.

 Рассмотрим ряд примеров.

Пример 5.1.1. Пусть Х множество стран и 5, если страны x и y граничат между собой. Требуется раскрасить карту так, чтобы никакие две соседние страны не были окрашены в один цвет.

Пример 5.1.2. Проводится монтаж аппаратуры, например, телефонной станции. Чтобы не перепутать проводники, необходимо провести их окраску таким образом, чтобы два проводника, идущие к одной плате, имели разный цвет.

 

5.1.1. Нахождение минимальной раскраски путём использования

                   соцветных вершин

Рассматривается алгоритм для нахождения минимальной раскраски графа.55 Две вершины x и y графа  L=(X,U) называют соцветными, если существует такая минимальная раскраска q(x) его вершин, при которой q(y)=q(z). Отношение соцветности симметрично и рефлексивно, но не транзитивно (так, например, вершины a и f графа на рис. 5.1.1. соцветны, вершины f и d тоже соцветны, а a и d - не соцветны.

Смежные вершины всегда несоцветны, но обратное утверждение неверно (см., например, вершины a и d).

Показано, что неполный связный граф L=(X,U)  всегда обладает хотя бы парой соцветных различных вершин. Отождествление двух таких вершин превращает L в связный граф L’ c прежним хроматическим числом. Если  L’  неполный, то в нём опять имеется пара различных соцветных вершин и т.д. Продолжая процесс отождествления, в конечном итоге получим полный граф F5, а одна из минимальных раскрасок вершин исходного графа находится следующим образом: окрасим вершины F5 в цвета 1,2,3..., 5 и придадим вершине 5 графа L цвет той вершины графа F5, в которую она перешла после всех отождествлений.

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

Одним из локальных критериев соцветности является следующий:

Если x и y две несмежные вершины, и 5, то x и y соцветны.

5

Пример 5.1.3.

5.1.2. Алгоритм  Витавера нахождения минимальной раскраски

         вершин

Алгоритм основан на нахождении некоторой специальной ориентации рёбер. Пусть L=(X,U)  - данный обыкновенный граф. Через 5 обозначим наибольшее из таких целых чисел К, что при любой ориентации всех рёбер графа  полученный орграф 5 содержит по крайней мере один ормаршрут длины К.

Теорема Витавера.

5.

Доказательство. Пусть 5 и пусть q(x)  - одна из минимальных раскрасок графа L.

Полагая

5,

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

Следовательно, 5, т.е.

5 *)

Пусть теперь, наоборот, данный граф L=(X,U) превращён некоторой ориентацией рёбер в орграф 5 не содержащий ни одного маршрута длины более 5. Определим последовательность x1,x2,: множество вершин, полагая

5.

При этом считаем Uxj = 0, т.е.

5.

Из определения множеств xj непосредственно следует, что

                                      5 ,     5                                      (5.1)

в каждом xj никакие две вершины не смежны.                                                 (5.2)

Кроме того,

                                 5при 5                            (5.3)

в самом деле, равенство xj = 0 означает, что

5

или

5.

Иначе говоря

5,

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

Далее

                        5.                     (5.4)

Действительно, пусть 5, a x - произвольная вершина из xi; по определению xi имеем 5 а значит и подавно 5, а так как 5, то 5, следовательно, 5, откуда и вытекает (5.4).

Наконец, из (5.4) и из предположения об отсутствии в 5 ормаршрутов длины >5 заключаем, что

                                                   5.                                         (5.5)

На основании (5.3), (5.5) и не пустоты X имеем

5,

где 5 и 5 при 5 значит, ввиду (5.1) и (5.2) система множеств 5 есть полная раскраска вершин графа L в 5 цветов. Отсюда и из *) вытекает справедливость теоремы.

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

Пусть 5 матрицы смежности графа под 5, а 5 - система переменных в 5, соответствующих рёбрам L , получаемых из L всевозможными ориентациями рёбер.

В матрице 5

5,

5,

5

5.

Как известно, элемент 5 матрицы 5 равен 1 или 0, смотря по тому, существует или не существует ормаршрут длины 5 из вершины xi в вершину xj в орграфе 5, полученном из L ориентацией рёбер, которая отвечает системе значений  5.

Поэтому

5,

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

5,

после чего образовать матрицу  5 и определить по ней множества 5 следующим образом: к x1 относим все те вершины x5. Которым в 5 отвечают строки из одних нулей; затем вычёркиваем из матрицы строки и столбцы, соответствующие вершинам xпо исходной; и так далее  до тех пор, пока не будет исчерпана вся матрица.

Существенным недостатком этого способа является весьма быстрый рост сложности  булева выражения

                                           5     

при увеличении 5.

               

Пример 5.1.4.

Рассмотрим граф, показанный на рис. 5.1.3

5
 

 

 

 

 

 

 

 

 


Имеем

   5                                               5

5.

Это означает, что ввиду непустоты данного графа, ормаршруты длины 1 существуют при любой ориентации рёбер.

5

5

55                        5

следовательно, 5. Одной из систем значений, при которой последняя сумма равна нулю, будет 5

Соответствующий орграф изображён на рис. 5.1.4, а его матрица смежности

5.

Из 5 сразу находим x1={1,4}, вычёркивая первую и четвёртую строки, а также первый и четвёртый столбцы, получаем матрицу

5,

из которой x2 = {2}, вычёркивая первую строку и первый столбец, получаем, что x= {3}. Таким образом, x(L) = 3, а одной из минимальных раскрасок вершин является такая, при которой первая и четвёртая вершины окрашены в красный цвет, вторая - в зелёный и третья - в синий.

 

5.2. Определение хроматического числа

              плоского графа

 

Пусть каждой вершине 5 обыкновенного графа L=(X,U)  отнесена некоторая точка плоскости, каждому ребру 5 прямолинейный отрезок с концами в тех случаях, которые отвечают вершинам, соединённым с L ребром U. Возникает вопрос о возможности изображения их в плоскости, чтобы никакие два ребра не пересекались в точке, являющейся концом хотя бы одного из тех рёбер.

5Пример 5.2.1. Задача о трёх городах и трёх источниках снабжения. Имеется три города A,B,C и три источника снабжения: водонапорная башня D, газовый завод E, электростанция F (рис. 5.2.1).

 

Можно ли начертить (на плане) три города, три источника и все линии передач таким образом, чтобы никакие две линии не пересекались между собой в не концевых точках? Непосредственные попытки показывают, что всегда можно нарисовать 8 линий, а девятая обязательно пересечёт хотя бы одну из этих восьми.

Для любого графа, однако, можно всегда попытаться выбрать такое расположение  его вершин в плоскости, при котором количество лишних пересечений было бы наименьшим; так граф F на рис. 5.2.2 допускает изображение с одной лишней точкой пересечения – рис. 5.2.3.

5В трёхмерном пространстве обыкновенный граф всегда допускает такое расположение, при котором два ребра не пересекаются в точке, отличной от  концевых.

Граф называется плоским, если он может быть расположен на плоскости без лишних точек пересечения.

5.2.1. Проблема четырёх красок

Что можно сказать о хроматическом числе графа, если известно, что он плоский?  Очевидно, оно может быть равным 1,2,3. Для графа на      рис. 5.2.4 хроматическое число равно четырём.

5
 

 

 

 

 

 

 


До сих пор не удавалось построить ни одного плоского графа L с 5, что даёт основание выдвинуть гипотезу четырёх красок: хроматическое число плоского графа никогда не превосходит 4. Первоначально эта гипотеза в терминах раскраски карт опубликована А. Кэли в 1878 году, хотя постановка этой проблемы осуществлена ещё А. Мёбиусом в 1840 году.

До настоящего времени гипотеза не доказана и не опровергнута.

Теорема.

 Если L = (X,U,P) - плоский граф, то 5.

В заключение заметим, что для решения задач раскраски возможным является использование аппарата дискретного программирования

Пусть необходимо проверить возможность раскраски вершин графа посредством P цветов. Каждому варианту раскраски ставится в соответствие система булевых переменных yiq i, U, q 1,P, где yiq равна единице, если вершина xi имеет цвет q и равна нулю в противоположном случае.

Положим также rij = 1, если xi - граничная точка ребра Uj; rij = 0 в противном случае.

Тогда задача сводится к определению значений для булевых переменных yiq , что

5, 5**)  **)

5, 5; 5

Пусть необходимо получить окраску вершин минимальным количеством цветов. С этой целью каждому цвету 5 отнесём «вес» - натуральное число aq, таким образом, что выполняется неравенство:

      a1+a2+...+aq-1+(n-q+1)aq<(n-q)a1+a2+...+aq-1+aq+aq+1, 5

      т.е aq+1>(n-q)aq-(n-q-1)a1.

Это неравенство гарантирует, что «самая лёгкая» окраска вершин графа с помощью q+1 цветов всё-таки «тяжелее», чем «самая тяжёлая» окраска q цветами.

Неравенство **)  наверняка выполняется, если

aq+1=(n-q)aq-(n-q-1)a1+1,

полагая a1=1, мы получим

aq+1=(n-q)[aq-1]+2,

откуда находим последовательно (независимо от графа L):

a2=2, a3=n, an=n2-4n+5, ...

Тогда задача раскраска вершин графа сводится к определению самой лёгкой раскраски: найти минимум

5

при ограничениях **).

По найденным yiq  хроматическое число вычисляется как

5.

 

Примечание.

К пособию прилагаются обучающие программы в электронном виде в папке D_M_2 для изучения базовых алгоритмов теории графов:

1. алгоритм Дейкстры нахождения кратчайших маршрутов на взвешенном графе;

2. алгоритм нахождения всем максимально полных и максимально пустых подграфов;

3. алгоритм построения кратчайших цепей на невзвешенном графе;

4. алгоритм нахождения гамильтонового цикла в графе.

КОНТРОЛЬНАЯ РАБОТА №1

Задание 1

Для графа G=(X,U) на рис.1  выполнить    

1.  Построить:

-  матрицу смежности;

- матрицу инциденций.

2.  Определить степени S[i] для вершин X[I]  данного графа, где i меняется от 1 до k.

3.  Подсчитать количество маршрутов длиной L = 3 между вершинами графа, построить их между вершинами х[i] и х[j] , помеченными "*".

*  Для выполнения п.3 составить программу на алгоритмическом языке  Паскаль, либо использовать систему MathCAD или MathLAB.

Задание 2

По матрицам А и С на рис.2 и рис. 3 построить графы G1 и G2.

Задание 3             

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

2. Результат представить в виде дерева решений.

Задание 4

Для графа, представленного  на рис.1  выполнить:

1. Построить подграфы: 3-х вершинные, 4-х вершинные, 1-вершинные.

2. Построить суграфы.

Задание 5

Для графа, представленного на рисунке 1 выполнить:

 1. Построить матрицу метрики.

 2. Вычислить радиус и диаметр.

 3. Определить периферийные точки.

 

 ВНИМАНИЕ    * Задания выполнять в текстовом редакторе WORD.

 

Наверх страницы

Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

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

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика