ЛЕКЦИЯ 12. Максимальные и наибольшие паросочетания. Алгоритм выбора наибольшего сочетания в двудольном графе с матрицей двудольного графа

Варианты теоремы Менгера

Непересекающиеся цепи и разделяющие множества

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

Лекция 11. Непересекающиеся цепи и разделяющие множества.

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

Пусть G(V, Е) — связный граф, и и v — две его несмежные вершины. Две цепи (и, v) называются вершинно-непересекающимися, если у них нет общих вершин, отличных от и и v.

Две цепиназываются рёберно-непересекающимися, если у них нет общих рёбер.

Замечание 1. Если две цепи вершинно не пересекаются, то они и рёберно не пересекаются.

Обозначим через Р(и, v) множество вершинно-непересекающихся цепей .

Множество R вершин (и/или рёбер) графа G разделяет две вершины и и v, если и и v принадлежат разным компонентам связности графа G-R.

Разделяющее множество рёбер называется разрезом. Разделяющее множество вершин для вершин и и v обозначим R(u, v).

Для заданных вершин и и v множества Р(и, v) и S(u, v) можно выбирать различным образом.

Из определений следует, что любое множество P(u,v) вершинно-непересека- ющихся цепей обладает тем свойством, что

,

а любое разделяющее множество вершин R(u, v) обладает тем свойством, что

& & .

Замечание 2. Если и и v принадлежат разным компонентам связности графа G, то \Р(и, v)| = 0 и \R(и, v)| = 0.

Пример 11.1. В графе, диаграмма которого представлена на рис. 32, можно выбрать множества вершинно-непересекающихся путей Р₁ = {(и, a, d, v), (u, b, e, v)}и Р₂ ={(u, b, d, v), (u, c, e, v)}. Заметим, что путь (u, c, b, d, v) образует множество Р₃ вершинно-непересекающихся путей, состоящее из одного элемента. Множества вершин R₁ ={a, b, c} и R₂ ={d, e} являются разделяющими для вершинu и v.

Рис. 32. Вершинно-непересекающиеся пути и разделяющие множества вершин

Теорема Менгера в «вершинной форме»

Теорема (Менгера, 1927 г.). Пусть uиv — несмежные вершины в графе G. Наименьшее число вершин в множестве, разделяющем и и v, равно наибольшему числу вершинно- непересекающихся простых -цепей:

max |Р(и, v)| = min\R(u, v)|.

Замечание 3. Легко видеть, что . Действительно, любая -цепь проходит через R. Если бы, то в R была бы вершина, принадлежащая более чем одной цепи из Р, что противоречит выбору Р. Таким образом, для и . Следовательно, . Утверждение теоремы состоит в том, что в любом графе существуют такие Р и R, что достигается равенство |Р| = |R|.

Доказательство. Пусть G — связный граф, ии v — несмежные вершины. Сов­местная индукция по р и q. База: наименьший граф, удовлетворяющий условиям теоремы, состоит из трех вершин u,w,v и двух рёбер (u,w) и(w,v). В нём P(u,v) = {} и R(u,v) = {w}. Таким образом, |Р(u,v)| = |R(u,v)|= 1. Пусть утверждение теоремы верно для всех графов с числом вершин меньше р и/или числом рёбер меньше q. Рассмотрим граф G с р вершинами и q ребрами. Пусть u,vV, причём u,v — не смежны и R — некоторое наименьшее множество вершин, разделяющее и и v. Обозначим п: = Рассмотрим три случая.

[ 1 ] Пусть в R есть вершины, несмежные сu и несмежные с v. Тогда граф G-R состоит из двух нетривиальных графов G₁ и G₂. Образуем два новых графа G_u и G_v, стягивая нетривиальные графы G₁ и G₂ к вершинам и и v соответственно: G_u : = G/G₁, G_v : = G/G₂ (рис. 33).

R по-прежнему является наименьшим разделяющим множеством для u и v как в G_u, так и в G_v. Так как G₁ и G₂ нетривиальны, то G_u и G_v имеют меньше вершин и/или рёбер, чем G. Следовательно, по индукционному предположению в G_u и в G_v имеется п вершинно-непересекающихся простых цепей. Комбинируя отрезки этих цепей от и до R и от R до v, получаем п вершинно-непересекающихся простых цепей в G.

[ 2 ] Пусть все вершины R смежны с и или с v (для определённости пусть с и) и среди вершин S есть вершина w, смежная одновременно с и и с v (рис. 34).

Рассмотрим граф G' : = G - w. В нем R - w — разделяющее множество для и и v, причём наименьшее. По индукционному предположению в G' имеется |R-w| = n - 1 вершинно-непересекающихся простых цепей. Добавим к ним цепь . Она простая и вершинно не пересекается с остальными. Таким образом, имеем п вершинно-непересекающихся простых цепей в G.t

Рис. 33. К доказательству теоремы Менгера, случай 1

Рис. 34. К доказательству теоремы Менгера, случай 2

[ 3 ] Пусть теперь все вершины R смежны с и или с v (для определённости пусть с u) и среди вершин R нет вершин, смежных одновременно с вершиной uис вершиной v. Рассмотрим кратчайшую -цепь, (рис. 35).

Рис. 35. К доказательству теоремы Менгера, случай 3

Рассмотрим граф G': = G/{w₁, w₂}, полученный из G склейкой вершин w₁и w₂в вершину w₁. Имеем, в противном случае цепь была бы ещё более короткой. Следовательно, в графе G' множество R по-прежнему является наименьшим, разделяющим и и v, и граф G' имеет по крайней мере на одно ребро меньше. По индукционному предположению в G' существуют п вершинно- непересекающихся простых цепей. Но цепи, которые не пересекаются в G', не пересекаются и в G. Таким образом, получаем п вершинно-непересекающихся простых цепей в G. Что и требовалось доказать.

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

Теорема. Для любых двух несмежных вершин и и v графа G наибольшее число рёберно-непересекающихся -цепей равно наименьшему числу рёбер в (и, v) -разрезе.

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

Другими словами, в любом графе G любые две несмежные вершины соединены не менее чем(G) вершинно-непересекающимися простыми цепями.

Так же можно отметить и связь между теоремами Менгера и Форда и Фалкерсона.