497
правок
Изменения
→Структурная теорема Эдмондса-Галлаи
Пусть <tex>u \in D(G)</tex>. Тогда существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] <tex>M_u</tex> графа <tex>G</tex>, не покрывающее <tex>u</tex>. Поскольку любое максимальное паросочетание графа <tex>G</tex> покрывает a, то <tex> \alpha (G - a) = \alpha (G) - 1 </tex> и более того, если, для некоторой вершины <tex>x \in D(G)</tex>, <tex>ax \in M_u</tex>, то <tex>M_u \setminus {ax} </tex> - максимальное паросочетание графа <tex> G - a </tex>, не покрывающее <tex> u </tex>. Таким образом, <tex>D(G - a) \supset D(G) </tex>. <br>
'''2.''' покажем, что <tex> D(G - a) \subset D(G)</tex>: <br>
Предположим, что существует максимальное паросочетание <tex>M'</tex> графа <tex> G - a</tex>, не покрывающее вершину <tex>v not \in D(G)</tex>. Пусть <tex> w \in D(G) </tex> - смежная с <tex> a \in A(G)</tex> вершина, а <tex> M_w </tex>- максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> w </tex>. Так как <tex> v not \in D(G) </tex>, максимальное паросочетание <tex> M_w </tex> покрывает вершину <tex>v</tex>. Рассмотрим граф <tex> H = G(M_w \bigcup M') </tex> - очевидно, он является объединением нескольких путей и чётных циклов. Пусть <tex> U </tex> - компонента связности графа <tex> H </tex>, содержащая <tex>v</tex>. Так как <tex> dHd_H(v) = 1 </tex>(степень вершины), то <tex> P = H(uU) </tex> - путь с началом в вершине <tex>v</tex>. В пути <tex>P</tex> чередуются рёбра из <tex> M_w и M' </tex>, причём начинается путь ребром из <tex>M_w </tex>. Так как <tex> dHd_H(a) = 1 </tex>, то вершина a либо не принадлежит пути <tex>P</tex>, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию <tex> M_w</tex>). Рассмотрим несколько случаев: <br>
[[Файл: Gallai-lema-a.png|150px|thumb|right|случай '''а''']]
