8.4. Теорема Менгера

В этом разделе мы представляем классический результат теории графов — теорему Менгера [8.11]. Она поможет соотнести связность графа с числом вершинно-непересекающихся путей между двумя различными вершинами графа.

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

Доказательство этой теоремы дается в разд. 15.7.

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

Доказательство. Очевидно, что теорема верна при Следовательно, необходимо рассмотреть вариант

Необходимость. Если s и не смежны, то необходимость следует из теоремы 8.9.

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

Теперь покажем, что в графе существует -путь, не содержащий вершин из А. Ясно, что это верно, если s и и смежны. Если s и не смежны, тогда в графе G имеется k вершинно-непересекающихся -путей и, следовательно, в графе G имеется вершинно-непересекающихся -путей. Поскольку хотя бы один из этих путей не содержит всех вершин А.

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

Достаточность. Поскольку между двумя различными вершинами графа G имеется k вершинно-непересекающихся путей, G — связный граф. Более того, не более чем один из этих путей может иметь длину 1, так как в графе G нет параллельных ребер. Объединение оставшихся путей должно содержать по крайней мере различных вершин, отличных от s и . Поэтому .

Допустим, что в графе G имеется такое разделяющее множество А, что Рассмотрим тогда подграф G графа G на множестве вершин Он имеет по меньшей мере две компоненты. Если мы выберем две вершины s и из различных компонент подграфа G, то в графе G имеется, самое большее, вершинно-непересекающихся -путей. Это противоречит тому, что любые две вершины графа G связаны k вершинно-непересекающимися путями.

Следовательно, достаточность доказана.

Этот результат получен Уитни [8.12]. Поскольку он является попросту вариацией теоремы 8.9, будем говорить также о нем как о теореме Менгера.

Рассмотрим два частных класса -связных графов: двусвязные и трехсвязные графы. Существует несколько эквивалентных характеризаций двусвязных графов. Некоторые из них уже приведены в упражнениях к гл. 1.

Татт охарактеризовал трехсвязные графы, исходя из частного класса графов, называемых колесами.

Рассмотрим цикл С длины п. Если мы добавим новую вершину и соединим ее со всеми вершинами цикла С, то получим колесо Например, колесо представлено на рис. 8.6.

Рис. 8.6. Колесо

Характеризация Татта [8.13] трехсвязных графов формулируется в следующей теореме:

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

1. Введением нового ребра.

2. Заменой вершины v степени не меньше 4 двумя такими смежными вершинами v и v" степеней не менее 3, что каждая вершина, смежная первоначально с вершиной v, становится смежной точно с одной из вершин v и

Закончим этот раздел характеризацией -реберно-связных графов. Эта характеризация аналогична теореме 8.9, называемой теоремой Менгера, хотя открыта независимо Фордом и Фалкерсоном [8.14], а также Элиасом, Файнстейном и Шенноном [8.15].

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

Доказательство этой теоремы приводится в разд. 15.7