Методические указания к выполнению расчетных работ по теории графов и сетей (1013088), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

на рис. 6.5 изображение орграфа D, разбитого науровни в соответствии с рис. 6.2, около каждой вершины которого указано значениефункции Гранди на этой вершине). Единственным ядром этого орграфа является множество N  {v V | g (v)  0}  {v4 , v6 }.Рис. 6.535Тема 7. Хроматическое число графа. Задача об оптимальном раскрашивании вершин графа.

Задача о минимальном числе помещений для хранения продуктовПусть G  (V , X ) – неориентированный граф, где V  {v1 ,..., vn }. Рассмотрим следующую задачу: (а) определить минимальное количество цветов p  p(G), необходимоедля раскрашивания вершин графа G так, чтобы никакие две смежные вершины не былиокрашены одним цветом; (б) разбить множество вершин V на подмножества V1 ,...,V p такие, что V  V1  ... V p , Vi  V j   при i  j, и чтобы множества V1 ,...,V p являлисьвнутренне устойчивыми (т.е. чтобы никакие две вершины из любого множества Vi небыли смежными, а следовательно, могли быть окрашенными в один цвет).

Такая задачаназывается задачей об оптимальном раскрашивании вершин неориентированного графаG, а число p  p(G) называется его хроматическим числом.Будем предполагать, что граф G является связным. В противном случае для достижения оптимального раскрашивания отдельно раскрашиваем множества вершин каждойкомпоненты связности графа G .

Тогда хроматическим числом графа G является максимальное из хроматических чисел его компонент связности.Опишем два алгоритма раскрашивания вершин графа G. Первый является приближенным («эвристическим»), дающим в некоторых случаях оптимальное раскрашиваниевершин графа G. Второй – гораздо более сложный, дающий во всех случаях оптимальноераскрашивание вершин графа G.Алгоритм 7.1 («эвристический»)Окрашиваем вершину v1 цветом 1. Окрашиваем вершину v2 цветом 1, если она неявляется смежной с вершиной v1 , или цветом 2, если она является смежной с вершинойv1.

Каждую вершину vk (где 1  k  n ) окрашиваем цветом с минимальным номером сре-ди номеров {1,2,..., k} \ N k , где N k – множество номеров цветов вершин v1 ,..., vk 1 , смежныхс вершиной vk .Рис. 7.1Пример 7.1. Применим алгоритм 7.1 к графу G, изображенному на рис. 7.1. Действуя в соответствии с алгоритмом 7.1, окрашиваем вершину v1 цветом 1, и, поскольку вершина v2 является смежной с v1 , окрашиваем ее цветом 2. Вершина v3 является смежной сv2 , но не с v1 , поэтому N 3  {2}, {1, 2, 3} \ {2}  {1, 3}, минимальным номером в множестве36{1, 3} является 1, а следовательно, вершина v3 окрашивается цветом 1. Далее вершину v4окрашиваем цветом с номером min{{1, 2, 3, 4} \ N 4 }  min{{1, 2, 3, 4} \ {1}}  2, вершину v5 –цветом с номером min{{1, 2, 3, 4, 5} \ N 5 }  min{{1, 2, 3, 4, 5} \ {1, 2}}  3, вершину v6 – цветом с номером min{{1, 2, 3, 4, 5, 6} \ N 6 }  min{{1, 2, 3, 4, 5, 6} \ {1, 2, 3}}  4, и т.д.

Указываем около каждой вершины на рис. 7.1 номер цвета, в который эта вершина окрашивается.По окончании работы алгоритма имеем: V  V1  ...  Vr , где r  4 , Vi – множество вершин,окрашенных цветом с номером i , где i {1, 2, 3, 4} ; V1  {v1 , v3 , v9 , v11}, V2  {v2 , v4 , v10 , v12},V3  {v5 , v7 }, V4  {v6 , v8 }; Vi  V j   при i  j; r – количество цветов, которое необходимодля такого раскрашивания. При этом никакие две различные вершины из Vi , гдеi {1, 2, 3, 4}, не являются смежными.Для того чтобы убедиться в оптимальности полученного раскрашивания вершинсвязного графа G (полученного с использованием алгоритма 7.1 или любого другого «эвристического» алгоритма) нередко помогают следующие простые утверждения.Утверждение 7.1.

Если связный граф G с n(G)  2 вершинами не содержит цикловили любой его простой цикл имеет четную длину, то этот граф является бихроматическим, т.е. p(G)  2 (см. на рис. 7.2 пример графа с оптимальным раскрашиванием вершин,у которого отсутствуют простые циклы нечетной длины).Рис. 7.2Утверждение 7.2. Если связный граф G с n(G)  3 вершинами имеет хотя быодин цикл нечетной длины, то p(G)  3.На рис. 7.3 приведено оптимальное раскрашивание вершин графа, содержащегоцикл нечетной длины.Рис. 7.3Замечание 7.1. Используя утверждение 2.2, нетрудно показать, что для того, чтобыу графа G с n(G)  2k (или n(G)  2k  1 вершинами) отсутствовали простые циклы37нечетной длины, необходимо и достаточно, чтобы в матрицеK o  A3  ...

 A2k 1( K o  A3  ...  A2k 1 ), где A  A(G) – матрица смежности графа G, отсутствовали ненуле-вые диагональные элементы.Нам понадобится следующее определение. Граф G называется полным, если вместе с любыми его вершинами v, w, где v  w, он содержит также ребро {v, w}.Утверждение 7.3. Если у связного графа G имеется полный подграф с k вершинами, где k  N, то p(G)  k (см. на рис. 7.4 полные графы для k  2, 3, 4, 5 и соответствующие оптимальные раскрашивания их вершин).Рис. 7.4В соответствии с приведенными утверждениями заметим, что граф G из примера7.1 содержит полный подграф с 4 вершинами (например, порожденный вершинами v1 , v2 ,v5 , v6 ), а следовательно, p(G)  4 (см.

утверждение 7.3). Но тогда раскрашивание вер-шин, найденное с помощью алгоритма 7.1 и приведенное на рис. 7.1, является оптимальным, т.е. p(G)  4.Метод «ветвей и границ». Как будет видно из последующих примеров, алгоритм7.1 далеко не всегда дает оптимальное раскрашивание вершин графа. Для того, чтобы раскрашивание вершин связного графа G  (V , X ), где V  {v1 ,..., vn }, было гарантированнооптимальным можно применить так называемый метод «ветвей и границ». В этом методерешается задача минимизации некоторой целевой функции f (x) на конечном множестведопустимых решений P. Допустимыми решениями (или допустимыми последовательностями) являются последовательности (i1 ,..., in ) (кратко – раскраски), где i j {1,2,..., n}, такие, что вершина v j окрашивается цветом с номером i j , j  1,2,..., n, и при этом никакиедве смежные вершины не окрашиваются одним цветом, т.е.

{v j1 , v j2 } X  i j1  i j2 . Совершенно аналогично будем понимать допустимость любой части этой последовательности (i1 ,..., i j ), и называть ее раскраской множества вершин {v1 ,..., v j }, где j {1,2,..., n  1}.Ищется последовательность, на которой достигается минимум целевой функцииf (i1 ,..., in )  max{ i1 ,..., in } на множестве допустимых решений P. Эта последовательность,очевидно, и укажет нам оптимальное раскрашивание вершин графа G.Будем искать оптимальное раскрашивание вершин графа G на дереве возможныхрешений (раскрасок) GT .

Это дерево состоит из n уровней: 1-ый уровень соответствуетвершине v1 и каждый j -й уровень – вершине v j , где j {1,2,..., n}. Совокупность вершинкаждого j -го уровня соответствует допустимым номерам цветов для окрашивания j -ойвершины. При изображении дерева решений эти номера будут указываться внутри вер-38шин каждого j -го уровня (см. на рис. 7.6 изображение дерева возможных решений GTдля графа, изображенного на рис.

7.5).Замечание 7.2. Не теряя общности рассуждений, можно считать, что для любойраскраски (i1 ,..., in )  P выполняетсяi1  1, j {2,..., n} i j  max{ i1 ,..., i j 1}  1,(7.1)так как, если имеется некоторая раскраска, то всегда можно перенумеровать цвета так,чтобы выполнялось это условие. Из (7.1), в частности, следует, что(7.2)i j  j, j  1,2,..., n.Пример 7.2. Если раскраска множества вершин некоторого графа G соответствуетвторой строке табл. 7.1, то после перенумерации цветов она переходит в раскраску, соответствующую третьей строке этой таблицы, а эта раскраска удовлетворяет (7.1).v1v2v4v3v5v6v7v8v9v1051321324413454532515Табл. 7.1В соответствии с замечанием 7.2 (см.

условие (7.2)) на первом уровне дерева GT ,соответствующего вершине v1 , присутствует единственная вершина с номером цвета 1, ана каждом j -ом уровне (соответствующем вершине v j ), где j {2,..., n}, – вершины с номерами цветов из множества {1,2,..., j}. Для каждого j {2,..., n} никакие две вершиныj -го уровня не являются смежными (иначе GT не будет деревом, поскольку в нем будутприсутствовать циклы).Единственная вершина первого уровня с номером цвета 1 соединяется ребрами свершинами второго уровня, соответствующими возможным номерам цветов вершины v2 .При этом, в силу (7.1), если вершины v1 , v2 являются смежными, то единственной вершиной второго уровня является вершина с номером цвета 2, в противном случае вершинамивторого уровня являются вершины с номерами цветов 1, 2, расположенные на его изображении в порядке возрастания этих номеров (см.

рис. 7.6).Вершины второго уровня соединяются ребрами с вершинами третьего уровня, соответствующими возможным номерам цветов вершины v3 . Если на втором уровне оказалась единственная вершина с номером цвета 2, то в силу (7.1) эта вершина соединяется свершинами третьего уровня с номерами цветов i3 {1, 2, 3}, для которых последовательность (1, 2, i3 ) является допустимой (расположенными на его изображении в порядке возрастания номеров).

В случае, если на втором уровне находятся две вершины с номерамицветов 1, 2, то (в соответствии с условием (7.1)) вершина с номером цвета 1 соединяется свершинами третьего уровня с номерами цветов i3 {1, 2}, для которых последовательность(1, 1, i3 ) является допустимой (расположенными на его изображении в порядке возрастанияномеров), а вершина с номером цвета 2 соединяется с вершинами третьего уровня с номерами цветов i3 {1, 2, 3}, для которых последовательность (1, 2, i3 ) является допустимой(расположенными на его изображении в порядке возрастания номеров).На каждом j -м уровне, где j {3,..., n 1}, любая вершина этого уровня соединяется ребрами с некоторыми вершинами ( j  1) -го уровня. При этом в силу того, что GT – де39рево, для любой вершины j -го уровня с некоторым цветом i j существует единственнаяцепь (и при этом простая; см.

свойство (4) деревьев в теме 4), соединяющая единственнуювершину первого уровня с номером цвета i1  1 с этой вершиной j -го уровня, которой соответствует последовательность (i1 ,..., i j ) номеров цветов, соответствующих вершинамэтой цепи. В силу (7.1) указанная вершина j -го уровня с номером цвета i j соединяетсяребрами с вершинами ( j  1) -го уровня с номерами цветов i j 1 {1,2,..., max{ i1 ,..., i j }  1}(расположенными на его изображении в порядке возрастания номеров), для которых последовательности (i1 ,..., i j 1 ) допустимы.Описанное дерево GT , дает нам схему «ветвления» для решения поставленной задачи.

Характеристики

Список файлов книги