По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
От [ ] [ ] Gg [1..5] [4,5] Ss (1) (1,4) Примечания Выбираем первую вершину Вершины 2, 3 исключаются из списка кандидатов, остаются вершины с номерами 4,5 Первое уточнение «черного ящика А». If [] Then Gg с учетом ранее использованных вершин> Else Его суть в том, что если выбирать из ранее использованных вершин нечего, то множество кандидатов совпадает со значени- ем Qp, и далее по логике мы «тупо» выбираем первую вершину из Qp. Переходим к следующему вызову процедуры Find. 3 2 [ ] [5] [ ] [4] [ ] [5] (1,4) (1,5) Вывод первого максимального независимого множества и выход в предыдущую копию Find Исключаем вершину 4 из Qp и включаем ее Продолжает работу цикл While процедуры Find с парамет- ром k, равным 2. Выбираем следующую вершину — это верши- на 5. И вызываем процедуры Find с другими значениями пара- метров. 3 2 [ ] [ ] [ ] [4,5] [ ] [ ] (1,5) Вывод второго максимального независимого множества Цикл While закончен, выход в предыдущую копию процедуры Find 172 Алгоритмы на графах Уточнение «черного ящика Б». Первое: необходимо исклю- чить вершину i из Qp и включить ее в Второе: следует от- корректировать множество Gg. Выбор на этом шаге вершин, не смежных с i, приведет к генерации повторяющихся максималь- ных независимых множеств, поэтому следует выбирать верши- ны из пересечения множеств Qp и A[i]. Итак, «черный ящик Б». =Qp- [i ] [i ] ; ; Следующий шаг — выход в предыдущую версию при этом значение 1 1 2 3 4 3 2 1 2 [2..5] [3,5] [5] [ ] [ ] [5] [3..5] [5] [1] [1] [ ] [ ] [ ] [5] [3] [1.2] [2] [1-5] [2..3] [3,5] [5] [ ] [ ] [ ] [2,3] (2) (2,3) (2,3,5) (3) Однако после работы «черного ящика Б» имеем следующие значения переменных Вывод третьего максимального независимого множества Согласно логике «черного ящика Б» множество кандидатов Gg становится пустым Итак, мы первый раз попадаем в процедуру Find, и множество при этом не пусто Должна работать логика «черного ящика А» при непустом значении Замечание 1. Если существует вершина при- надлежащая такая, что пересечение A[j] и Qp пусто, то да- льнейшее построение максимального независимого множества бессмысленно — вершины из A[j] не попадут в него (в нашем примере как раз этот случай). Замечание 2. Если нет вершин из удовлетворяющих первому замечанию, то какую вер- шину из Qp следует выбирать? Ответ: вершину для некоторого значения причем мощность пересечения множеств минимальна. Данный выбор позволяет со- кратить перебор. Итак, окончательная логика «черного ящика А». Begin For To N Do 4. Алгоритмы на графах 173 j In Then If Number Then Begin End; Gg:=Qp*A[i] End Закончим трассировку примера. 2 1 [5] [1,2,3] [ ] [ ] Выход в основную программу Независимые максимальные множества графа найдены. 4.7.3. Доминирующие множества Для графа доминирующее множество вершин есть множество вершин такое, что для каждой вершины j, не входящей в S, существует ребро, идущее из некоторой верши- ны множества в вершину Доминирующее множество назы- вается минимальным, если нет другого доминирующего множе- ства, содержащегося в нем. Пример. Доминирующие множества (1, 2, 3), (4, 5, 6, 7, 8, 9), (1,2, 3, 8, 9), (1, 2, 3, 7) и т. д. Множества 2, 3), (4, 5, 6, 7, 8, 9) являются минималь- ными. Если Q — семейство всех ми- нимальных доминирующих мно- жеств графа, то число называется числом доминирования графа, а множество S*, на котором этот минимум достигается, называется наименьшим доминирующим множеством. Для нашего примера Задача. Пусть город можно изобразить как квадрат, разде- ленный на районов. Считается, что опорный пункт мили- ции, расположенный в каком-либо районе, может контролиро- вать не только этот район, но и граничащие с ним районы. Требуется найти наименьшее количество пунктов милиции и места их размещения, такие, чтобы контролировался весь го- род. Представим каждый район вершиной графа и ребрами сое- диним только те вершины, которые соответствуют соседним районам. Нам необходимо найти число доминирования графа и 174 4. Алгоритмы на графах хотя бы одно наимень- шее доминирующее мно- жество. Для данной зада- чи и наименьших множеств есть (3, 5, 12, 14). Эти вершины выделены на рисунке. 4.7.4. Задача о наименьшем покрытии Рассмотрим граф. На рисунке показана его матрица смежно- сти А и транспонированная матрица смежности с единичными диагональными элементами А*. Задача определения доминиру- ющего множества графа G эквивалентна задаче нахождения та- кого наименьшего множества столбцов в матрице А*, что каж- дая строка матрицы содержит единицу хотя бы в одном из выбранных столбцов. Задачу о поиске наименьшего множества столбцов, «покрывающего» все строки матрицы, называют за- дачей о наименьшем покрытии. В общем случае матрица не обязательно является квадратной, кроме того, вершинам графа (столбцам) может быть приписан вес, в этом случае необходимо найти покрытие с наименьшей общей стоимостью. Если введе- но дополнительное ограничение, суть которого в том, чтобы любая пара столбцов не имела общих единиц в одних и тех же строках, то задачу называют задачей о наименьшем разбиении. Предварительные замечания. 1. Если некоторая строка мат- рицы А* имеет единицу в единственном столбце, т. е. больше нет столбцов, содержащих единицу в этой строке, то данный столбец следует включать в любое решение. 2. Рассмотрим множество столбцов матрицы А*, имеющих единицы в конкретной строке. Для нашего примера: 6, 4. Алгоритмы на графах 175 7, 2, 5, 3, 5), 4), 3, 4, 5), 6), 7), Видим, что Из этого сле- дует, что 5-ю строку можно не рассматривать, поскольку любое множество столбцов, покрывающее 4-ю строку, должно покры- вать и 5-ю. Четвертая строка доминирует над пятой. 4.7.5. Метод решения задачи о наименьшем разбиении Попытаемся осознать метод решения задачи, рассматривая, как обычно, пример. У нас есть ориентированный граф, его матрица смежности и транспонированная матрица смежности с единичными диагональными элементами. Исследуем структуру матрицы А*. Нас интересует, какие столбцы содержат единицу в первой строке, какие столбцы содержат единицу во второй строке и не содержат в первой и так далее. С этой целью можно было бы переставлять столбцы в матрице А*, но оставим ее «в покое». Будем использовать дополнительную матрицу ее тип: Type = Array l..MaxN+l] Of Integer; Var Bl:Pr; где MaxN — максимальная размерность задачи. Почему плюс единица (технический прием — «барьер»), будет ясно из последующего изложения (процедура Press). При инициализации матрица должна иметь вид: в первой строке — 3 . . N 0], а все остальные элементы равны нулю. Наше исходное предположение заключается в том, что все столбцы матрицы имеют единицы в первой строке. Прове- рим его. Будем просматривать элементы очередной строки (i) матрицы Если то со значением Bl[i,j], как номе- ром столбца матрицы А*, проверим соответствующий элемент А*. При его неравенстве нулю элемент остается на своем мес- те, иначе он переписывается в следующую строку матрицы а элементы текущей строки сдвигаются вправо, сжимаются (Press). Итак, для N-1 строки матрицы Для нашего приме- ра матрица после этого преобразования будет иметь вид: 176 4. Алгоритмы на графах В задаче заданы стоимости вершин графа или стоимости столбцов матрицы А*, и необходимо найти разбиение наимень- шей стоимости. Пусть стоимости описываются в массиве Price Of Integer) и для примера на рисунке имеют значения [15 13 43 8 9 10]. Осталась чисто техническая де- таль — отсортировать элементы каждой строки матрицы по возрастанию стоимости соответствующих столбцов матрицы А*. Результирующая матрица имеет вид: а логика формирования приведена ниже по тексту (Blocs). Procedure блоков, В1 - глобальная *} Procedure Sort; Begin End; Procedure элементы строки с номером i, начиная с позиции (столбца) на одну позицию вправо.*} Var Begin k:=j; While Do Begin { *Поэтому размерность матрицы с плюс В последнем столбце строки всегда записан 0. *} Bl[i,k]:=Bl[i,k+l]; (k) ; End; End; Var Begin Алгоритмы на графах 177 (B1) ; For i:=l N Do что в первом блоке все столбцы. *} For i:=l Do Begin While Do Begin If Then не в этом блоке. (cnt) ; в следующую строку. *} Press (i,j); Dec(j) End; Inc(j); End; End; Sort; End; Изменим чуть-чуть Какой вид бу- дет иметь матрица После этой предварительной работы мы имеем вполне «при- личную» организацию данных для решения задачи путем пере- бора вариантов. Матрица Bl разбита на блоки, и необходимо выбрать по одному элементу (если соответствующие строки ещё не покрыты) из каждого блока. Процесс выбора следует про- должать до тех пор, пока не будут включены в «покрытие» все строки или окажется, что некоторую строку нельзя включить. Продолжим рассмотрение метода. Если при поиске незави- симых множеств мы шли «сверху вниз», последовательно уточ- няя логику, то сейчас попробуем идти «снизу вверх», склады- окончательное решение из сделанных «кирпичиков». Как обычно, следует начать со структур данных. Во-первых, мы ищем лучшее решение, т. е. то множество столбцов, которое удовлетворяет условиям задачи (не пересечение и «покрытие» всего множества строк), и суммарная стоимость этого множест- ва минимальна. Значит, необходима структура данных для хранения этого множества и значения наилучшей стоимости и, соответственно, структуры данных для хранения текущего (очередного) решения и его стоимости. Во-вторых, в решении строка может быть или не быть. Следовательно, нам требуется как-то фиксировать эту информацию. Итак, данные. Алгоритмы на графах Type Of Boolean; Var решение. *} решение. *} - признак того, что строка i "покрыта" текущим решением. *} Логика включения (исключения) столбца с номером k в ре- шение (из решения) имеет вид: Procedure Include {*Включить столбец в *} Var j Begin цена решения. *} с номером к в решение. For N Do If Then "покрытые" столбцом к.*} Ends- Procedure столбец из *} Var Begin For To N Do If (A*[j,k]=l) And R[j] Then R[j] End; Проверка, сформировано ли решение, заключается в том, чтобы просмотреть массив и определить, все ли его элементы равны истине. Function Var Begin j:=l; While And R[j] Do Inc(j); End; Кроме перечисленных действий, нам необходимо уметь опре- делять — «можно ли столбец с номером k включать в решение». Для этого следует просмотреть столбец с номером k матрицы и проверить, нет ли совпадений единичных элементов со значе- нием True соответствующих элементов массива R. Алгоритмы на графах 179 Function Cross -.Boolean; столбца с частичным решением, сформированным Var Begin While And Not(R[j] And (A*[j,k]=l)) Do Inc(j) ; End; Заключительная логика поиска (Find) имеет в качестве па- раметров номер блока (строки матрицы Bl) — переменная Ыос и номер позиции в строке. Первый вызов — Procedure Find (Ыос, jnd: Integer) ; Begin If Result Then Begin If P Pbetter:=P; Sbetter:=S; End; End Else If [bloc, jnd] =0 Then Exit Else If ) Then Begin Include ); Find(bloc+l,l); ); End Else If R[bloc] Then Else End; Будет ли правильно работать процедура Find при изменен- ной матрице А* (изменение приведено выше по тексту)? Испра- вьте неточность. Нам осталось дать общую логику, но после выполненной ра- боты она не вызывает затруднений. Program .; Type . . . Var . . . Procedure и инициализация данных. Begin End; 180 4. Алгоритмы на графах Procedure *} Begin End; {*Процедуры и функции, рассмотренные ранее по тексту. *} Begin логика. Blocs; Find (1,1) ; Print; End. 4.8. Раскраски 4.8.1. Правильные раскраски Пусть — неориентированный граф. Произвольная функция где принадлежит множеству натура- льных чисел, называется вершинной fc-раскраской графа G. Раскраска называется правильной, если для любых смежных вершин и и v. Граф, для которого существует прави- льная называется fe-раскрашиваемым. Минималь- ное число при котором граф G является называется хроматическим числом графа и обозначается Пример. Меньшим количеством цветов граф пра- вильно раскрасить нельзя из-за наличия треугольников. Рядом с «кружками» — вер- шинами графа — указаны но- мера цветов. Метод получения правиль- ной раскраски достаточно прост — закрашиваем очеред- ную вершину в минимально возможный цвет. Введем следую- щие структуры данных. Const количество вершин *} Type Of V; Of V; Var MyAr ray; {*Gr - каждой вершине графа определяется номер цвета. *} 4. Алгоритмы на графах 181 Для примера, приведенного выше, массив Gr имеет вид: Gr[l]=Gr[3]=Gr[5]=l; Gr[6]=3. Фрагмент основной логики. описания графа>; For i:=l N Do Gr[i] : = [Color (i ,0) ] ; <вывод Поиск цвета раскраски для одной вершины можно реализо- вать с помощью следующей функции: Function - номер окрашиваемой вершины, t - номер цвета, с которого следует искать раскраску данной вершины, А - матрица смежности, Gr - результирующий массив. *} Var Begin ]; For j:=l To Do If Then ; множество цветов, в которые окрашены смежные вершины с меньшими *} j:=t; Repeat минимального номера цвета, в который можно окрасить данную *} Inc(j) ; Until In Ws) End; Пример. Получаем правильную рас- краску: Gr[l]=l, Gr[3]=3, Gr[5]=4. Однако минимальной раскрас- кой является: Gr[l]=l, и и хроматическое число графа равно трем. 4.8.2. Поиск минимальной раскраски вершин графа Метод основан на простой идее [16], и в некоторых случаях он дает точный результат. Пусть получена правильная раскрас- ка графа, q — количество цветов в этой раскраске. Если суще- ствует раскраска, использующая только q— 1 цветов, то все вер- шины, окрашенные в цвет q, должны быть окрашены в цвет g, 182 4. Алгоритмы на графах меньший q. Согласно логике формирования правильной рас- краски вершина была окрашена в цвет q, потому что не могла быть окрашена в цвет с меньшим номером. Следовательно, не- обходимо попробовать изменить цвет у вершин, смежных с рас- сматриваемой. Но как это сделать? Найдем вершину с минима- льным номером, окрашенную в цвет q, и просмотрим вершины, смежные с найденной. Попытаемся окрашивать смежные вер- шины не в минимально возможный цвет. Для этого находим очередную смежную вершину и стараемся окрасить ее в другой цвет. Если это получается, то перекрашиваем вершины с боль- шими номерами по методу правильной раскраски. При неуда- че, когда изменить цвет не удалось или правильная раскраска не уменьшила количества цветов, переходим к следующей вер- шине. И так, пока не будут просмотрены все смежные верши- ны. Опишем логику, используя функцию Color предыдущего па- раграфа. Var i : V; Procedure MaxMin (Var c,t:V) ; Begin End; Procedure Begin End; Begin <ввод данных, инициализация For N Do правильная *} Repeat <найти вершину с минимальным номером , имеющую максимальный цвет раскраски - >; цвет раскраски в соответствии с описанной идеей - процедура Until [MinNum] ;{ *До тех пор, пока метод улучшает раскраску. *} <вывод минимальной (или почти минимальной!) раскраски>; End. Алгоритмы на графах 183 Если работа процедуры достаточно очевидна, то Change требует дальнейшего уточнения. Procedure Change V) ; r,q:V; Function смежную с 1 вершину с наибольшим номером и не принадлежащую множеству *} Var Begin While And (i In Rs) And Do Begin If Then Dec(i) ; End End; Begin Ws: = [] ; q:=MaxCon (t,Ws) ; While q<>0 Do Begin If r с номерами, большими t, по методу правильной Else Ws:=Ws+[q]; End; End; Осталось заметить, что при изменении цвета у вершин с но- мерами, большими значения t, по методу правильной раскрас- ки следует запоминать в рабочих переменных значения Gr и МахС, так как при неудаче (раскраску не улучшим) их необхо- димо восстанавливать, и на этом закончить уточнение логики. При любом упорядочении вершин допустимые цвета для вершины с номером i удовлетворяют условию Это очевидно, так как вершине i предшествует i— 1 вершина, и, следователь- но, никакой цвет не использовался. Итак, для вершины 1 допустимый цвет 1, для 2 — цвет 1 и 2 и так далее. С точки зрения скорости вычислений вершины следует помечать (при- сваивать номера) так, чтобы первые q вершин образовывали наибольшую клику графа G. Это приведет к тому, что каждая из этих вершин имеет один допустимый цвет и процесс возвра- 184 4. Алгоритмы на графах та в алгоритме можно будет заканчивать при достижении вер- шины из этого множества. В алгоритме рассматриваются только вершины, смежные с вершиной, окрашенной в максимальный цвет. Однако следует работать и с вершинами, являющимися смежными для смеж- ных. На рисунке приведены примеры графов и их раскраски. Первая цифра в круглых скобках обозначает значение цвета при правильной раскраске, вторая — при минимальной. Для графов на первом и третьем рисунках алго- ритм дает правильный результат. Для графа на втором рисунке при изме- нении цвета вершины с номером 6 необходимо просматривать вершины, смежные к смежным с шестой вершиной. Рас- смотренный алгоритм требует очередной моди- фикации. Самый интересный случай на последнем рисунке. Мы не можем получить минимальную раскраску с помощью рас- смотренного алгоритма (даже если будем рассматривать все вер- 4. Алгоритмы на графах 185 шины, смежные к смежным), хотя она, конечно, существует и совпадает с предыдущей. Итак, результат работы алгоритма за- висит от нумерации вершин графа, а таких способов — способов нумерации N!. 4.8.3. Использование задачи о наименьшем покрытии при раскраске вершин графа При любой правильной раскраске графа G множество вершин, окрашиваемых в один и тот же цвет, является независимым мно- жеством. Поэтому раскраску можно понимать как разбиение вер- шин графа на независимые множества. Если рассматривать толь- ко максимальные независимые множества, то раскраска — это не что иное, как покрытие вершин графа G множествами этого типа. В том случае, когда вершина принадлежит не одному максималь- ному независимому множеству, допустимы различные раскраски с одним и тем же количеством цветов. Эту вершину можно окра- шивать в цвета тех множеств, которым она принадлежит. Исходным положением метода является получение всех максимальных независимых множеств и хранение их в неко- торой матрице где W — количество максимальных независимых множеств. Элемент матрицы M[i,j] равен едини- це, если вершина с номером i принадлежит множеству с номе- ром у, и нулю в противном случае. Если затем каждому столбцу поставить в соответствие единичную стоимость, то задача рас- краски не что иное, как поиск минимального количества столб- цов в матрице М, покрывающих все ее строки. Каждый стол- бец соответствует определенному цвету. Пример. Имеем пять максимальных независимых множеств и два варианта решения задачи о покрытии (строки А В). В обоих случаях вершина 4 может быть Окрашена как во второй, так и в третий цвета. |