Алгоритм выделения пустых подграфов

1. Сопоставляем корню строящегося дерева заданный граф G .

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

3. Каждый конец построенных дуг взвешиваем неокрестностью вершины графа, сопоставленного рассматриваемому корню.

4. Считаем построенного яруса корнем нового дерева.

5. Устанавливаем, взвешена ли вершина символом Ø . Если “нет”, то переходим к п. 2, если “да”, то – к п. 6.

6. Каждая ветвь построенного дерева однозначно определяет пустой подграф заданного графа G .

Закон поглощения. Если в k – ом ярусе дерева вершины v_i и v_j не смежны, поддерево с корнем v_i построено и если в поддереве с корнем v_j появляется вершина v_i , то соответствующая ветвь не строится.

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

Пример. Определить все пустые подграфы и число внутренней устойчивости графа G , изображенного на рис. 5.8.

□ Используя алгоритм выделения пустых подграфов, построим дерево:

Каждая ветвь дерева соответствует пустому подграфу графа G. При построении дерева два раза использовался закон поглощения. Заданный граф имеет восемь пустых подграфов: Е₁ = {4, 8, 3}, E₂ = {4, 8, 6}, E₃ = {4, 2, 6}, E₄ = {4, 7}, E₅ = {1, 5, 7}, E₆ = {1, 5, 8}, E₇ = {1, 6, 8}, E₈ = {5, 2}.

Число внутренней устойчивости равно:

. ■

Замечание. Аналогично можно определить и вычислить реберное число независимости графа G.

§ 4. Вершинное число внешней устойчивости графа

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

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

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

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

Модифицированной матрицей смежности графа G называется дизъюнкция матрицы смежности и единичной диагональной матрицы Е :

.

Определение вершинного числа внешней устойчивости

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

Пример. Определить вершинное число внешней устойчивости графа G (рис. 5.9 )

Рис. 5.9

□ Строим модифицированную матрицу смежности заданного графа G :

a b c d e f

a b c d e f

.

Теперь в матрице находим минимальное число строк, покрывающих все столбцы матрицы (или минимальное число столбцов, покрывающих все строки матрицы, т.к. модифицированная матрица смежности симметричная). Такое минимальное покрытие образуют, например, строки b и c. Следовательно,

Проверка вершин b и с на покрытие всех вершин графа G подтверждает правильность такого решения : вершина b покрывает себя и вершины a, c, e, f , а вершина с покрывает себя и вершины a, b, e, d, т.е. все вершины заданного графа G покрыты. ■

Если по условию задачи требуется определить все минимальные покрытия, то можно использовать алгоритм Петрика , который заключается в следующем: для каждого столбца модифицированной матрицы определяется дизъюнкция строк, покрывающих этот столбец. Далее записывается конъюнкция найденных дизъюнкций (аналогично при покрытии строк столбцами).

При выделении минимального покрытия могут быть использованы следующие законы операций дизъюнкции и конъюнкции:

1. идемпотентности

2. коммутативности

3. ассоциативности

4. дистрибутивности

5. поглощения

Здесь под знаком сложения понимается операция дизъюнкции, а под знаком умножения – операция конъюнкции.

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

□ Используя алгоритм Петрика и законы операций дизъюнкции и конъюнкции для модифицированной матрицы предыдущего примера, получим:

1 2 3 4 5 6

=

Минимальными покрытиями являются покрытия, содержащие по два элемента. Любое из покрытий является решением, т.е.

■

Замечание. Аналогично можно определить и вычислить реберное число внешней устойчивости графа G.