Изменения

'''Смежными листами''' (англ. ''coincident endpoints'') в неориентрированном графе называется такая пара вершин <tex>ux, vy</tex>, что <tex>\operatorname{deg}u x = 1, \operatorname{deg}v y = 1</tex>, а также имеющая общюю соседнюю причём обе вершины имеют общую смежную вершину (или, другими словами, расстояние между этими вершинами <tex>\rho(ux, vy) = 2</tex>).

Если <tex>G</tex> — связный граф, состоящий из <tex>n \geq 3</tex> вершин и не содержащий ''смежных листов'', то найдутся такие две '''смежные''' вершины <tex>ux, vy</tex>, что граф <tex>G \backslash \{ux, vy\}</tex> также будет связен.

:Пусть <tex>a, y</tex> — вершины графа <tex>G</tex>, находящиеся на расстоянии <tex>\rho(a, y) = d</tex>, а <tex>D = a \dots xy</tex> — путь между этими вершинами длины <tex>d</tex> (вершины <tex>a</tex> и <tex>x</tex> могут совпадать). :# В начале берем какой-нибудь поток Предположим, что <tex>G^* = G \backslash \{x, y\}</tex> не связен. Обозначим за начальный <tex>A</tex> компоненту связности <tex>G^*</tex> такую, что <tex>a \in A</tex>. Так как <tex>D</tex> является диаметром графа <tex>G</tex>, то все вершины графа <tex>G^* \backslash A</tex> смежны с <tex>x</tex> в графе <tex>G</tex> (напримериначе мы бы нашли пару вершин, нулевойрасстояние между которыми было бы больше, чем <tex>d</tex>).После этого возможны несколько случаев::# В остаточной сети этого потока находим какой-нибудь Граф <tex>G^* \backslash A</tex> содержит компоненту <tex>B</tex> размера <tex>m \geq 2</tex>. Тогда для <tex>\forall b, c \in B</tex>, которые в <tex>B</tex> являются смежными, в <tex>G \backslash \{b, c\}</tex> будет существовать путь из источника к стоку и увеличиваем поток на пропускную способность этого путикаждой вершины до <tex>x</tex>, а значит, <tex>G \backslash \{b, c\}</tex> связен.:# Повторяем пункт Граф <tex>2G^* \backslash A</tex> содержит вершину <tex>e</tex> до тех пор, пока находится хоть какой-то путь смежную с <tex>y</tex> в остаточной сетиграфе <tex>G</tex>. Тогда по аналогичным причинам граф <tex>G \backslash \{e, y\}</tex> связен. :То# Граф <tex>G^* \backslash A</tex> не содержит компонент размера <tex>m \geq 2</tex> (случай 1), что получится а значит он содержит только изолированные вершины. Тогда все вершины <tex>G^* \backslash A</tex> связаны только с <tex>x</tex> в концеисходном графе <tex>G</tex> (они могли быть связаны максимум с еще одной вершиной <tex>y</tex>, будет максимальным потокома это было рассмотрено в случае 2). В случае целочисленной сети достаточно в качестве начального приближения взять нулевой потокНо, и так как граф не трудно видетьсодержит смежных листов, что на каждой итерации (в том числе то <tex>G^* \backslash A</tex> состоит из единственной вершины <tex>f</tex>. Если <tex>\operatorname{deg}y = 1</tex>, то <tex>f</tex> и последней) этот поток будет оставаться целочисленным<tex>y</tex> являлись бы смежными листами. Таким образом, <tex>y</tex> должен быть связан с вершиной из <tex>A</tex>. Следовательно, <tex>G \backslash \{f, что и докажет требуемоеx\}</tex> связен.

Для начала докажем Докажем оригинальную версию теоремы, доказанную независимо Самнером (''Sumner'', 1974) и Лас Вергнасом (''Las Vergnas'', 1975). Напомним, что индуцированный подграф <tex>-</tex> это граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.

Пусть <tex>G</tex> — связный граф четного порядка <tex>2n \geq 3</tex>, и существует <tex>k</tex> <tex>-</tex> такое число , что любой индуцированный связный подграф <tex>G</tex> четного порядка <tex>2k</tex> содержит совершенное паросочетание (<tex>1 < k \leq n</tex> ). Тогда <tex>G</tex> также содержит совершенное паросочетание.|proof=:Докажем теорему по индукции.:Теорема довольно просто проверяется для случаев <tex>n = 2, 3</tex>. Предположим, что теорема выполняется для <tex>n - 1</tex> (<tex>n \geq 4</tex>). Пусть <tex>G</tex> — связный граф порядка <tex>2n</tex> и предположим, что <tex>k</tex> <tex>-</tex> это такоечисло, что любой индуцированный связный подграф <tex>G</tex> четного порядка <tex>2k</tex> содержит совершенное паросочетание.:Случай <tex>k = n</tex> очевиден, поэтому можно считать, что <tex>k \leq n - 1</tex>. :Если граф содержит смежные листы <tex>a</tex> и <tex>b</tex>, то рассмотрим любой связный подграф графа <tex>G</tex> четного порядка <tex>2k</tex>, содержащий эти вершины. Тогда хотя бы одна из вершин <tex>a, b</tex> будет не покрыта паросочетанием.:Таким образом, граф <tex>G</tex> не содержит смежных листов. Тогда из леммы следует, что существуют смежные вершины <tex>x</tex> и <tex>y</tex>, что граф <tex>G \backslash \{x, y\}</tex> связен. :По нашему индукционному предположению, граф <tex>G \backslash \{x, y\}</tex> содержит совершенное паросочетание, а значит, добавив ребро <tex>xy</tex>, мы получим совершенное паросочетание для <tex>G</tex>.}} Также можно доказать более слабое, но полезное утверждение про графы без лап (индуцированных подграфов <tex>K_{1,3}</tex>).{{Утверждение|about=следствие из теоремы|statement=Пусть <tex>G</tex> — связный граф чётного порядка <tex>2n</tex>, не содержащий лап. Тогда <tex>G</tex> также содержит совершенное паросочетание.

# Из [[Определение матроида|определения матроида]] (первой аксиомы) :Единственный связный граф порядка <tex>\varnothing \in I4</tex>, где который не содержит совершенного паросочетания — это <tex>I</tex> K_{{---1,3}} семейство независимых множеств матроида <tex>M</tex>. Откуда <tex>\varnothing \notin \mathfrak{C}</tex>. # От противного. Из определения цикла: если <tex>C_1 \subset C_2</tex>Таким образом, то <tex>C_1 \in I</tex>. Значит <tex>C_1 \notin \mathfrak{C}</tex>. Противоречие. Аналогично эта теорема является частным случаем теоремы Самнера — Лас Вергнаса при <tex>C_2 \nsubseteq C_1</tex>. # От противного. Пусть <tex>D k = (C_1 \cup C_2) \setminus p2</tex> независимо.#: Обозначим <tex>A = C_1 \cap C_2</tex>. Покажем, что <tex>|A| < |D|</tex>. Из предыдущего пункта очевидным образом следует, что <tex>|C_1 \setminus C_2| > 0за исключением тривиального случая </tex> и <tex>|C_2 \setminus C_1| > 0</tex>.#: <tex>|D| n = |C_1 \setminus C_2| + |C_2 \setminus C_1| + |A| - 1 \geqslant |A| + 1 + 1 - 1 = |A| + 1 > |A|.</tex>#: Отсюда путем многократного применения третьей аксиомы матроидов получим <tex>\exists B: A \subset B</tex> и <tex>|B| = |D|</tex>, причем <tex>B</tex> {{---}} независимо. #[[Файл: Поскольку <tex>C_1</tex> {{---}} цикл, <tex>C_1 \nsubseteq B</tex>all_connected_graphs_4_vertices. Значит, найдется хотя бы один элемент в <tex>C_1 \setminus A</tex>, не лежащий в <tex>B</tex>. Следовательно в <tex>B</tex> лежит не более чем <tex>png|C_1 \setminus Athumb| - 1</tex> элементов из этого множества. Аналогично в <tex>B</tex> лежит не более чем <tex>550px|C_2 \setminus Acenter| - 1</tex> элементов Все связные неориентированные графы, состоящие из множества <tex>C_2 \setminus A</tex> . #: Получаем: <tex>|B| \leqslant |A| + |C_1 \setminus A| - 1 + |C_2 \setminus A| - 1 = |C_1 \cup C_2| - 2 = |D| - 1</tex> . А поскольку <tex>|B| = |D|</tex> получаем противоречие. 4 вершин, с точностью до изоморфизма]]