3.4.2. Алгоритм построения минимального остова

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

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

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

3.6. Алгоритм кратчайшей раскраски графа

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

Условие оптимальности раскрашивания - использование минимального числа красок φ - хроматического числа графа.

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

Конечная грань - это внутренняя область плоскости, ограниченная ребрами в плоском изображении графа. .

Теорема 3.5.1. Для плоских графов φ<4.

Пример 4.5.1. Рассмотрим граф G изображенный на рис.4.5.1, и произведем раскраску этого графа. φ=3 (0,1,2)

φ=3 (0,1,2)

Рис.4.5.1

Алгоритм граничного перебора построения максимальных внутренне устойчивых вершин графа (построение множества всех несмежных вершин графа).

0. Текущее множество Y={X1}, i=0.

1. Находим наибольший номер j, такой, что XjY :

a). Если j  n и i = 0 переходим в п.3 (n – количество вершин графа).

b). Если j  n и i 0 переходим в п.2.

c). Если j = n, то удаляем из множества Y вершину Xn: Y=Y/{Xn}//(множ.Y без вершины Xn):

если при этом Y, то переходим в п.1,

иначе, если Y= – переходим в п.6.

0. Удаляем элемент Xj из множества Y и проверяем:

если Y=, то j=j+1, вводим в Y элемент Xj и переходим в п.3,

иначе, если Y – переходим в п.3 (ничего не выполняя).

0. j=j+1. Если j > n, то переходим в п.4,

иначе проверяем на смежность вершины Xj со всеми вершинами множества Y. Если хотя бы для одного элемента Xl множества Y (XlY) вершины (Xj, Xl) смежные, выполняем п.3, иначе добавляем элемент Xj в множество Y и переходим в п.3.

0. Если i=0, то переходим в п.5,

иначе, если i0, проверяем на поглощение множество Y: YYs (1  s  i).

Если Ys поглощает Y, то переходим в п.1, иначе переходим в п.5.

0. i=i+1, Yi=Y. Переходим в п.1 (Yi – очередное построенное подмножество максимальных внутренне устойчивых вершин графа).

1. Построение всех Ys (1  s  i), максимально внутренне устойчивых множеств закончено.

Алгоритм кратчайшей раскраски графа (словесное описание):

1. Методом граничного перебора строятся все максимальные внутренне устойчивые множества вершин графа (множество несмежных вершин).

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

3. Решается задача построения одного кратчайшего покрытия (например, методом минимального столбца максимальной строки).

4. Вершины принадлежащие каждому подмножеству вошедшему в найденное кратчайшее покрытие окрашиваются 1-й краской. Если некоторая вершина принадлежит нескольким вошедшим в покрытие подмножествам, то она в одном остается, из других исключается.

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

Несмежные вершины выбраны в таблице единицами. Далее решается задача построения одного кратчайшего покрытия (методом минимального столбца максимальной строки). Вершины, принадлежащие каждому подмножеству, вошедшему в найденное кратчайшее покрытие, окрашиваются одной краской. Если некоторая вершина принадлежит нескольким вошедшим в покрытие подмножествам, то она в одном остаётся, из остальных исключается. Для нашего примера получим два подмножества: Y₁, Y₂, Y₃. Таким образом, получим три краски 0,1,2 соответственно. И действительно (как показано на рис, 4.5.1): если х₁, покрасить краской 0, то все смежные с ней вершины х₂, х₃, х₄, х₅ нельзя покрасить 0. х₂, х₄ - смежные, для них необходимо две разные краски (1 и 2), х₃, х₄ - аналогично. Таким образом, изображенная на примере раскраска - минимальна.