Изменения
Нет описания правки
{{Определение
|id = odd
|definition =<tex>\mathrm{odd}({G})</tex> {{---}} число нечетных компонент связности в графе <tex>{G}</tex>, где '''нечетная компонента''' (англ. ''odd component'') {{---}} это [[Отношение связности, компоненты связности#def2|компонента связности]], содержащая нечетное число вершин.
}}
{{Определение
|id = Tutt_set
|definition ='''Множество Татта''' графа <tex>{G}</tex> {{---}} множество <tex>S \subset {V_{G}}</tex>, для которого выполнено условие: <tex>\mathrm{odd}({G} \setminus S) > \left\vert S \right\vert</tex>
}}
#: [[Файл:Граф_для_теоремы_Татта.png|right|200px|thumb|К доказательству 2-ого пункта леммы.]]
# Вершины <tex>x,y,z</tex> и <tex>t</tex> лежат в одном подграфе графа <tex>{G'} \setminus U</tex>.
#: Построим граф <tex>H</tex>, такой что <tex>{V_{H}}={V}</tex> и <tex>{E_{H}}=M_1 \oplus M_2</tex><ref>[http://ru.wikipedia.org/wiki/%D1%E8%EC%EC%E5%F2%F0%E8%F7%E5%F1%EA%E0%FF_%F0%E0%E7%ED%EE%F1%F2%FC Симметрическая разность] </ref>. Получим, что вершины <tex>x,y,z</tex> и <tex>t</tex> лежат на каком-то чередующемся цикле из ребер <tex>M_1</tex> и <tex>M_2</tex>. Рассмотрим подробнее, почему это будет именно так. Ребро <tex>xz</tex> принадлежит паросочетанию <tex>M_1</tex>, значит вершина <tex>y</tex> и какая-то произвольная вершина <tex>v</tex> будут покрыты ребром паросочетания <tex>M_1</tex>, при этом эти ребра не принадлежат паросочетанию <tex>M_2</tex>, но ребра <tex>yt</tex> и <tex>vu</tex>, где <tex>u</tex> {{---}} произвольная вершина, принадлежат <tex>M_2</tex> и не принадлежат <tex>M_1</tex> и так далее. Таким образом и получается чередующийся цикл в графе <tex>H</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>{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, M_2</tex> (выберем ребра одного из них). Таким образом, получили полное паросочетание в графе <tex>{G'}</tex>, противоречие.
В каждом из возможных случаев получили противоречие, значит, наше начальное предположение тоже неверно и <tex>{G'} \setminus U</tex> {{---}} объединение несвязных полных графов, лемма доказана.
}}
==См. также==
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
* [[Декомпозиция Эдмондса-Галлаи]]
==Примечания==
<references/>
== Источники информации ==
