497
правок
Изменения
→Структурная теорема Эдмондса-Галлаи
Пусть u \in D(G). Тогда существует максимальное паросочетание Mu графа G, не покрывающее u. Поскольку любое максимальное паросочетание графа G покрывает a, то α(G - a) = α(G) - 1 и более того, если ax \in Mu, то Mu \setminus {ax} - максимальное паросочетание графа G - a, не покрывающее u. Таким образом, D(G - a) \supset D(G). <br>
2)покажем, что D(G − a) /subset D(G): <br>
Предположим, что существует максимальное паросочетание M' графа G - a, не покрывающее вершину v not \in D(G). Пусть w \in D(G) - смежная с a \in A(G) вершина, а Mw - максимальное паросочетание графа G, не покрывающее w. Так как v not \in D(G), максимальное паросочетание Mw покрывает вершину v. Рассмотрим граф H = G(Mw \bigcup M') - очевидно, он является объединением нескольких путей и чётных циклов. Пусть U - компонента связности графа H, содержащая v. Так как dH(v) = 1, то P = H(U) - путь с началом в вершине v. В пути P чередуются рёбра из Mw и M', причём начинается путь ребром из Mw. Так как dH(a) = 1, то вершина a либо не принадлежит пути P, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию Mw). Рассмотрим несколько случаев:a.b.c.<br>
'''a.''' Путь P кончается ребром из M' (см. рисунок)<br>
Рассмотрим паросочетание Mv = Mw \oplus E(P) (симметрическая разность
Mw и E(P). то есть, рёбра, входящие ровно в одно из двух множеств).
Очевидно, Mv - максимальное паросочетание графа G, не покрывающее v, поэтому v \in D(G), противоречие. <br>
'''b.''' Путь P кончается ребром из Mw, вершина a - конец пути P. (см.рисунок)<br>
Рассмотрим паросочетание Mv∗ = (Mw \oplus E(P)) \bigcup \{aw\}. Тогда Mv∗ - максимальное паросочетание графа G, не покрывающее v, поэтому v \in D(G), противоречие.
'''c.''' Путь P кончается ребром из Mw, a \in V(P) (см. рисунок)
Рассмотрим паросочетание M'' = M \oplus E(P). Тогда |M''| = |M'| + 1, причём Mээ \subset E(G - a). Противоречие с максимальностью паросочетания M'.
Таким образом, наше предположение невозможно и D(G - a) \subset D(G).
А значит, D(G - a) = D(G).
}}
