497
правок
Изменения
→Структурная теорема Эдмондса-Галлаи
|proof=
много-много и с картинками. :(
Достаточно доказать, что D(G-a) = D(G). <br>
1) покажем, что D(G − a) /supset D(G): <br>
Пусть 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.
}}
