06. Формулировка теоремы Менгера (вершинный и реберный варианты), теорема Холла о системах различных представителей и теорема Кёнига о независимых клетках в матрице

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

Зываются в разных связных компонентах). Если исходный граф связен, то для каждой пары несмежных вершин возникает следующая характеристика: Минимальное число ()-Раз-деляющих вершин; будем в длижайшем тексте обозначать это число символом K. Например, в приведенном ниже графе это число равно двум, хотя ()-разделяющих наборов здесь не-сколько:

Будем, далее, всякую цепь, соединяющую вершины называть ()-Цепью; если у двух ()-цепей имеется общая вершина, отличная от , то будем называть такие две ()-цепи Вершинно-пересекающимися. Очевидно, в каждом графе для данных двух вер-

Шин существует следующая характеристика - Максимальное число вершинно-неперсека-ющихся (попарно) ()-Цепей. Будем в этом тексте обозначать только что введенную харак-теристику через L. Нетрудно понять, что Всегда . Сформулируем теперь Теорему Мен-

Гера: Всегда . Или то же самое словами:

Минимальное число ()-Разделяющих вершин равно максимальному числу вершинно непересекающихся (попарно) ()-Цепей.

Сформулированная только что теорема называется Вершинным вариантом теоремы Менгера. Существует аналогичный реберный вариант этой теоремы. Сформулируем его.

В прежних обозначениях набор ребер называется ()-Разделяющим, если после удаления этих ребер из графа верштины окажутся несвязанными (т. е. в разных связных компонентах). Ясно, что граф обладает следующей характеристикой: Минимальное число ребер, составляющих ()-Разделяющий набор. Обозначим эту характеристику через K.

Назовем, далее, набор ()-цепей Реберно непересекающимся (а цепи этого набора - реберно непересекающимися), Если любые две цепи набора не имеют общих ребер. Очевидно, для каждого графа и фиксированных в нем вершин существует такая характеристика: Максимальбное число реберно непересекающихся ()-Цепей. Обозначим эту характеристику через L. Как и в предыдущем случае, очевидно, что . Реберный вариант теоремы Менгера: всегда (или словами: Минимальное число ()-Разделяющих ребер равно максимальному числу реберно непересекающихся ()-цепей.

Мы продемонстрируем на двух примерах плодотворность теоремы Менгера (в обоих е вариантах - вершинном и реберном).

Пример 1. Теорема Холла о системах различных представите-лей. Пусть - некоторые множества и имеются элементы ; элементы называются Системой различных представителей, если все они попарно различны.

Если рассмотреть множества , то станет ясно, что система различных представителей существует не всегда. Теорема Холла устверждает: Система мно-жеств Обладает системой различных представителей тогда и только тогда, когда в объединении любых K Множеств из числа данных Имеется K различных элементов,

Для доказательства этого факта строится следующий граф:

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

Пример 2. Теорема Кёнига о покрывающих линиях. Пусть имеется некоторая матрица , в которой все элементы равны либо нулю, либо единице. Будем словом Линия Обозначать либо строку, либо столбец в данной матрице. Две единицы в матрице будем на-

Зывать Независимыми, если они не находятся на одной линии. Произвольный набор единиц будем называть Набором независимых единиц, если любые две единицы в наборе независимы. Наконец, набор линий в данной матрице будем называть Покрывающим, если каждая единица матрицы принадлежит хоть одной линии набора.

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

Для доказательства и этой теоремы строится такой же граф, как и для теоремы Холла (он изображен на последнем рисунке) с той лишь разницей, что стновятся именами строк данной матри-цы, - становятся именами столбцов и ребро включается

Тогда и только тогда, когда на пересечении I-Ой строки и J-ого столбца стоит в матрице единица. Факт, сформулированный в теореме Кёнига, именно в этой матрице превращается в вершинный вариант теоремы Менгера в отношении вершин .

< Предыдущая		Следующая >