Изменения

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

Теорема Татта о существовании полного паросочетания

Нет изменений в размере, 21:59, 17 декабря 2013
м
Нет описания правки
В графе <tex>\mathbb{G'}+xz</tex> существует полное паросочетание <tex>M_1</tex>, так как граф <tex>\mathbb{G'}</tex> максимальный по построению. Аналогично, в графе <tex>\mathbb{G'}+yt</tex> существует полное паросочетание <tex>M_2</tex>. Так как в <tex>\mathbb{G'}</tex> нет полного паросочетания, то <tex>xz \in M_1</tex> и <tex>yt \in M_2</tex>.
[[Файл:Граф_для_теоремы_Татта.png|right|300px|thumb|К доказательству 2-ого пункта леммы.]]
Возможны два случая:
* Вершины <tex>x,z</tex> и <tex>y,t</tex> лежат в разных полных подграфах графа <tex>\mathbb{G'} \setminus U</tex>, обозначим их <tex>H_1</tex> и <tex>H_2</tex>, соответственно.
[[Файл:Граф_для_теоремы_Татта.png|right|200px|thumb|К доказательству 2-ого пункта леммы.]]
Покроем вершины подграфа <tex>H_1</tex> паросочетанием <tex>M_2</tex>, при этом заметим, что ребро <tex>xz</tex> не входит в это паросочетание. Аналогично покроем паросочетанием <tex>M_1</tex> вершины подрафа <tex>H_2</tex> и ребро <tex>yt</tex> не войдет в это паросочетание. Если остались непокрытые вершины, то покроем их ребрами из любого паросочетания <tex>M_1</tex> или <tex>M_2</tex>. Таким образом, мы получим полное паросочетание в графе <tex>\mathbb{G'}</tex>, что противоречит его построению.
137
правок

Навигация