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

Цепи, соединяющие единственную вершину первого уровня с вершинами n -гоуровня дадут нам все возможные раскраски (последовательности цветов, соответствующих последовательностям вершин этих цепей), среди которых будет находиться и оптимальная. См. на рис. 7.6 дерево GT , для графа G, изображенного на рис. 7.5. Это деревопостроено с учетом выполнения условия (7.1).Рис. 7.5Рис. 7.6Понятно, что при достаточно большом количестве вершин n количество вершин вGT может оказаться очень большим, что создаст затруднения при выборе оптимальнойраскраски.

Для того, чтобы по возможности избежать эти затруднения можно воспользоваться следующими правилами:(а) Во-первых, воспользуемся тем, что ищутся не все оптимальные раскраски, алишь любая из них. Учитывая это, на последнем этапе ветвления, т.е. после получения це40пи длины n  1 с последовательностью номеров цветов ее вершин (i1 ,..., in 1 ) последняявершина этой цепи с номером цвета in 1 соединяется с единственной вершиной n -гоуровня с номером минимально возможного цвета in {1,2,..., max{ i1 ,..., in 1}  1}, для которого последовательность (i1 ,..., in ) допустима, т.е.

является раскраской. Понятно, что пользуясь этим правилом, мы не отсечем все оптимальные раскраски.(б) Во вторых, воспользуемся так называемыми «правилами отсечения». Каждойвершине n -го уровня дерева GT , с некоторым номером цвета in соответствует единственная цепь, соединяющая единственную вершину первого уровня с этой вершиной. Этойцепи соответствует раскраска, т.е. последовательность номеров цветов ее вершин (i1 ,..., in ).Поставим этой вершине в соответствие значение функции f (i1 ,..., in )  max{ i1 ,..., in }, которое будем указывать над каждой вершиной n -го уровня на изображении дерева GT (см.рис. 7.7).

Совершенно аналогично каждой вершине j -го уровня дерева GT , гдеj {2,..., n  1}, соответствует единственная цепь, соединяющая единственную вершинупервого уровня с этой вершиной. Этой цепи соответствует последовательность номеровцветов (i1 ,..., i j ) ее вершин. Поставим этой вершине в соответствие значение функцииmax{ i1 ,..., i j }, которое будем указывать на дереве GT над этой вершиной и называть оцен-кой для этой вершины. Заметим, что для любой раскраски (i1 ,..., i j ,..., in )  P (продолжающей раскраску (i1 ,..., i j ) множества вершин {v1 ,..., v j } ) выполняетсяf (i1 ,..., i j ,..., in )  max{ i1 ,..., in }  max{ i1 ,..., i j },(7.3)т.е. величина max{ i1 ,..., i j } является нижней оценкой для всех раскрасок, продолжающихраскраску (i1 ,..., i j ) множества вершин {v1 ,..., v j }, где j {1,2,..., n  1}.Заметим, что (по построению) самой левой цепью дерева GT , соединяющей единственную вершину первого уровня с самой левой вершиной n -го уровня является раскраска, получаемая в соответствии с реализацией алгоритма 7.1.

Организуем поэтапноепостроение дерева GT таким образом, чтобы эта цепь была построена первой. Значениецелевой функции на раскраске, соответствующей этой цепи обозначим через ~p. Эту величину, которая будет уточняться при дальнейшем построении дерева GT , будем называтьдостигнутым рекордом, т.е. минимальным достигнутым количеством цветов, для всехуже построенных раскрасок. В силу (7.3), если для некоторой очередной вершины дереваGT (которую мы проходим в процессе поэтапного построения этого дерева) оценка этойвершины больше или равна достигнутого рекорда ~p , то все продолжающие ее раскраскине улучшат достигнутый рекорд ~p , и поэтому в дереве GT не осуществляется дальнейшего продолжения цепей после этой вершины и на изображении GT такие вершины выделяются жирными кружками (см.

на рис. 7.7 вершины с №10, №12 ).Остается описать порядок прохождения вершин в дереве GT (порядок продолжения ветвления). В [3, стр. 47, 48] описаны три возможных способа (продолжения ветвления). Применим к решению нашей задачи способ 2. В этом способе для очередного ветвления (т.е. для построения, продолжающих эту вершину цепей дерева GT ) берется вершина текущего дерева решений максимального уровня j {1,2,..., n 1} и являющаяся самой41левой среди вершин этого уровня, для которых еще не были построены продолжающие ихцепи.

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

На рис. 7.7 приведен результат обхода множества вершин дерева GT , изображенного на рис. 7.6 и соответствующего множеству раскрасок для графа G, изображенного на рис. 7.5. Этот обход произведен в соответствии с правилами (а) и (б), а также с выбранным способом продолжения ветвления. На этом рисунке под каждой вершиной дерева GT указан номер этой вершины в порядке обхода вершин этого дерева. На рис.

7.7 всепройденные (и пронумерованные при этом обходе) вершины выделены жирными (№10,№12) или полужирными (№№1–9, №11) кружками, а все ребра, входящие в цепи, соединяющие единственную вершину первого уровня со всеми выделенными вершинами, изображены в виде отрезков полужирных прямых.Рис. 7.7Заметим, что при достижении вершины с №8 получаем первое значение достигнутого рекорда ~p  4. В соответствии с правилом (б) при достижении вершины с №10 (изображена жирным кружком) отсекаем все продолжающиеся из нее цепи. Далее при достижении вершины с №11 уменьшаем достигнутый рекорд до ~p  3 и в соответствии с правилом (б) при достижении вершины с №12 (изображена жирным кружком) отсекаем всепродолжающиеся из нее цепи. Оптимальная раскраска соответствует цепи, соединяющейединственную вершину первого уровня дерева GT с вершиной n -го уровня, помеченнойсимволом  .

Соответствующие этой раскраске номера цветов указаны около вершин графа G на рис. 7.5. Таким образом, хроматическим числом графа G, изображенного на рис.7.5, является p(G)  3.Замечание 7.3. В соответствии с утверждением 7.3 перед началом реализации метода ветвей и границ полезно (для уменьшения числа вершин в дереве GT ) выделить вграфе G полный подграф G0 по возможности с большим числом вершин n0 , а затем перенумеровать вершины графа G так, чтобы первыми его вершинами: v1 ,..., vn0 были вер42шины из G0 .

Тогда при построении GT с учетом (7.1) на каждом j -м уровне, гдеj {1,2,..., n0 }, имеем единственную вершину с номером цвета j.Задача о минимальном числе помещений для хранения продуктов. ПустьD  (V , X ) – орграф, V – множество продуктов, X – множество дуг вида x  (v, w)  X , гдеv, w V . Если x  (v, w)  X , то продукт v отрицательно воздействует на продукт w, т.е.продукты v, w нельзя хранить в одном помещении.

В этом случае можно поставить задачуоб определении минимального числа помещений для хранения продуктов из множестваV . Заметим, что в рассматриваемой задаче направление дуги (v, w) не имеет значения,поскольку присутствие вместо дуги (v, w) дуги ( w, v ) также означает, что продукты v, wнельзя хранить в одном помещении. Поэтому при указанной постановке задачи можно от~~орграфа D  (V , X ) перейти к неориентированному графу G  (V , X ) , где x  {v, w} Xтогда и только тогда, когда выполняется хотя бы одно из двух условий: (v, w)  X или~(w, v)  X .

Граф G  (V , X ) называется ассоциированным с орграфом D  (V , X ). В этомслучае задача об определении минимального числа помещений для хранения продуктов изV эквивалентна задаче об оптимальном раскрашивании вершин графа G : (а) определитьминимальное количество цветов p, необходимое для раскрашивания вершин неориентированного графа G так, чтобы никакие две смежные вершины не были окрашены однимцветом; (б) разбить множество вершин V на подмножества V1 ,...,V p такие, чтоV  V1  ...

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