Изменения

Перейти к: навигация, поиск

Декомпозиция Эдмондса-Галлаи

63 байта добавлено, 17:55, 21 декабря 2013
Структурная теорема Эдмондса-Галлаи
Достаточно доказать, что <tex>D(G - a) = D(G)</tex>. <br>
'''1.''' покажем, что <tex>D(G - a) \supset D(G)</tex> : <br>
Пусть <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> dH(v) = 1 </tex>, то <tex> P = H(u) </tex> - путь с началом в вершине <tex>v</tex>. В пути <tex>P</tex> чередуются рёбра из <tex> M_w и M' </tex>, причём начинается путь ребром из <tex>M_w </tex>. Так как <tex> dH(a) = 1 </tex>, то вершина a либо не принадлежит пути <tex>P</tex>, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию <tex> M_w</tex>). Рассмотрим несколько случаев: <br>
497
правок

Навигация