§ 37. Подмножество сочленения

Пусть задан связный граф непустое подмножество А называется подмножеством сочленения, если подграф, порожденный множеством не связан. В случае, когда подмножество А сводится к единственной вершине, ее называют точкой сочленения.

Например, подмножество является подмножеством сочленения неориентированного графа, порожденного множеством

Минимальное подмножество сочленения. Рассмотрим два подмножества множества порождающего граф

Рис. 158.

Предлагается найти наименьшее подмножество сочленения А, которое разделяет подмножества из

Иначе говоря, рассматривая симметрический граф без петель, соответствующий отыскивают такое множество А (если оно существует), что

Например, если и , то является минимальным подмножеством сочленения (рис. 158).

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

Полная подматрица. Основная подматрица. Покрытие. Полной подматрицей булевой матрицы называется ее подматрица, все элементы которой равны 1.

Основной подматрицей называется полная подматрица, не содержащаяся ни в какой другой полной подматрице.

Например, на рис. 159 представлены все основные подматрицы матрицы

Покрытием булевой матрицы называют множество полных подматриц, покрывающее все единичные элементы этой матрицы Например, покрытие матрицы (рис. 159).

Рис. 159

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

Пусть I — множество строк, множество столбцов матрицы Каждая полная подматрица определяется парой подмножеств, где Введем две операции, Если полная подматрица определяется определяется то

Используя указанные ниже правила, можно получить все основные подматрицы.

Правило I Удаляем любую подматрицу содержащуюся в подматрице из покрытия С

Правило II Добавляем к С подматрицы, получаемые применением вышеуказанных операций ко всем парам матриц II, оставшимся в покрытии (если при этом получается матрица, уже содержащаяся в С, то она не добавляется).

Пример (рис. 159). Найдем основные подматрицы матрицы выбирая покрытие.

Шаг 2 (правило II). Найдем объединения и пересечения:

которые дают новую подматрицу

Рассматривая

получаем

а

приводят к

Наконец,

Пересечения для всех и вторую операцию из (37.2) применять излишне.

Шаг 3 (правило I). Выпишем новое покрытие:

удалена, так как содержится в

Шаг 4 (правило II). Проводим подробно все выкладки;

Получаем новую подматрицу

Далее,

(см. скан)

(см. скан)

содержащуюся в . Шаг 5 (правило I). Выписываем новое покрытие:

удалена, так как содержится в .

Рис. 100.

Шаг 6 (правило II). Действуя по правилу II, мы приходим к тому же покрытию. Следовательно, мы нашли все основные матрицы (см. рис. 159),

Отыскание минимальных подмножеств сочленений. На примере графа на рис. 160 проиллюстрируем процесс отыскания минимальных подмножеств сочленения. Выписываем булеву матрицу симметрического графа без петель, соответствующего графу на рис. 160, и дополнительную к ней матрицу

где - квадратная матрица, все элементы которой единицы:

(см. скан)

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

не минимальное (в этом случае к можно присоединить по крайней мере одну вершину так что (37.1, г) еще выполняется) и, следовательно,

Рис. 161

Рис. 162.

Таким образом, задача сводится к отысканию основных подматриц в определяемых подмножествами

Пример. Если (рис. 160), то определяется с помощью

а с помощью

Отсюда следует, что

— минимальные подмножества сочленения (см. рис. 161 и 162).

УПРАЖНЕНИЕ

(см. скан)