§ 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.