8. Связность и паросочетания

В гл. 1 мы определили, что граф является связным, если между двумя произвольными вершинами существует путь. Предположим, что граф G связный. Тогда нас может интересовать, «как хорошо» он связан. Другими словами, нам бы хотелось знать минимальное число вершин или ребер, удаление которых превращало бы граф G в несвязный. Это приводит нас к понятиям «вершинная связность» и реберная связность графа». В настоящей главе мы предлагаем некоторые результаты, касающиеся вершинной и реберной связностей графа. Обсуждаем также классический результат теории графов — теорему Менгера, которая соотносит связности с числом вершинно-непересекающихся и реберно-непересекающихся путей.

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

Связность и паросочетания — это широко изученные темы теории графов. Этим областям принадлежит много глубоких результатов теории графов.

8.1. Связность, или вершинная связность

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

Например, связность графа на рис. 8.1 равна 2, поскольку удаление вершин и из него приводит к несвязному графу, а удаление произвольной вершины не достигает этого. Очевидно, что связность несвязного графа равна 0.

Рассмотрим граф на вершинах. Ясно, что если граф G полный. Если же он не полный, то имеет хотя бы две несмежные вершины Удаление из графа G оставшихся вершин

приведет к графу, в котором вершины не соединены путем. Таким образом, если граф G не полный, то

Разделяющее множество графа G — это множество вершин, удаление которых из графа G приводит к несвязному или тривиальному графу.

Рис. 8.1.

Граф называется k-связным, если Таким образом, -связный граф не содержит разделяющих множеств 5 мощности

Если граф связный, его связность больше или равна 1. Следовательно, связные графы 1-связны.

Если связный граф не содержит точек сочленения, то его связность больше 1. Поэтому связные графы без точек сочленения -связны.

В следующей теореме мы представляем простую верхнюю границу связности графа.

Теорема для простого связного графа G, где — минимальная степень вершины в графе

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

Если граф G имеет ребер и вершин то из теоремы 1.1 следует, что Поэтому и

где целая частьх (наибольшее целое, меньшее или равноех).

Объединяя выражение (8.1) с результатом, установленным теоремой 8.1, получаем следующее утверждение:

Теорема 8.2. Для простого связного графа G, имеющего ребер и вершин, .

Пусть — наименьшее число ребер, которые должен иметь -связный граф на вершинах. Конечно, мы полагаем . Из теоремы 8.2 следует, что

где — ближайшее целое к (наименьшее целое, большее или равное ).

Харари [8.1] доказал, что равенство в выражении (8.2) достигается с помощью специальной процедуры построения -связного графа , который содержит точно ребер. Процедура заключается в следующем:

Случай 1. k четно.

Пусть . Тогда строится на вершинах и две вершины смежны, если - где сложение ведется по . Граф представлен на рис. 8.2, а.

Рис. 8.2.

Случай 2. k нечетно, четно.

Пусть Граф получается из графа введением ребер, соединяющих вершины и v; для . Граф показан на рис. 8.2, б.

Случай 3. k нечетно, нечетно.

Пусть Граф получается из графа введением ребер, соединяющих вершины для . Граф представлен на рис. 8.2, в.

Легко проверить, что граф , построенный указанным образом, содержит точно ребер. Докажем сейчас, что граф k-связный.

Теорема 8.3. Граф k-связный.

Доказательство.

Случай

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

Случай четно.

Допустим, что вершины нельзя связать путем после удаления вершин Если один из двух интервалов [0, а], не содержит последовательных индексов из этого множества, то путь из вершины в вершину можно построить так, как показано в случае 1. Поэтому предположим, что вершины нельзя соединить путем после удаления вершин где где

Пусть

Тогда Существует путь из вершины в вершину и из вершины в вершину Следовательно, существует путь из вершины в вершину поскольку вершины смежны в

Случай нечетно.

Доказательство проводится аналогично случаю 2.

В следующей теореме мы представляем достаточные условия что граф -связен. Этот результат получен Бонди [8.2].

Теорема 8.4. Пусть G — простой граф размерности п. Пусть вершины графа G упорядочены так, что Тогда граф G -связен, если для

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

Рассмотрим граф который должен быть несвязным. Пусть Н — компонента графа минимального порядка . Тогда степень каждой вершины в графе Н не больше Следовательно, в графе G степень каждой вершины графа Н не превышает . Таким образом,

Поэтому по условиям теоремы

Так как граф имеет вершин, компонента графа минимального порядка, то или

Следовательно,

где — множество вершин графа Н. Так как каждая вершина смежна не больше чем с вершинами

Из выражений (8.5) и (8.6) следует, что все вершины степени больше находятся в S. Следовательно, существует не более s вершин степени, превышающей Поэтому

Используя выражения (8.4) и (8.7), получим Следовательно, или что противоречит допущению.

Например, степени вершин графа на рис. 8.3 удовлетворяют условиям теоремы 8.4 для Следовательно, он -связный.

Рис. 8.3. 3-связный граф, удовлетворяющий условиям теоремы 8.4 для случая