Изменения

Перейти к: навигация, поиск
м
Критерий Татта
* Вершины <tex>x,y,z</tex> и <tex>t</tex> лежат в одном подграфе графа <tex>\mathbb{G'} \setminus U</tex>.
Построим граф <tex>H</tex>, такой что <tex>\mathbb{V_\mathbb{H}}=\mathbb{V_\mathbb{G'}}=\mathbb{V_\mathbb{G}}</tex> и <tex>\mathbb{E_\mathbb{H}}=M_1 \oplus M_2</tex>. Получим, что вершины <tex>x,y,z</tex> и <tex>t</tex> лежат на каком-то чередующемся цикле. В силу симметричности <tex>x</tex> и <tex>z</tex> можно считать, что вершины расположены в порядке <tex>tzxy</tex>. Тогда существует путь <tex>P_1=t..zx..y</tex> и полное паросочетание в нем, следовательно существует и путь <tex>P_2=t..zy..x</tex>, содержащий только ребра графа <tex>\mathbb{G'}</tex>. Тогда на пути <tex>x..y</tex> возьмем ребра из паросочетания <tex>M_2</tex>, а на пути <tex>t..z</tex> - ребра из паросочетания <tex>M_1</tex>. Непокрытыми остались вершины <tex>z </tex> и <tex>y</tex>, которые мы покроем ребром <tex>yz</tex>. Таким образом нам удалось построить полное паросочетание на вершинах выбранного подграфа. В остальных подграфах выберем ребра Вершины не принадлежащие рассматриваемому циклу покроем ребрами любого из паросочетаний <tex>M_1</tex> и <tex>, M_2</tex>(выберем ребра одного из них). Таким образом, получили полное паросочетание в графе <tex>\mathbb{G'}</tex>, противоречие.
В каждом из возможных случаев получили противоречие, значит, наше начальное предположение тоже неверно и <tex>G' \setminus U</tex> {{---}} объединение несвязных полных графов, лемма доказана.
137
правок

Навигация