Изменения

|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>

Пусть <tex> U = \{ v \in {V}: \deg_{G'} (v) = n - 1 \}</tex>.

<tex>\forall S \subset {V}</tex> выполнено условие: <tex>\mathrm{odd}({G} \setminus S) \leqslant \left\vert S \right\vert</tex> (то есть в графе <tex>{G}</tex> нет ни одного множества Татта)

Одна из вершин каждой нечетной компоненты связности графа <tex> {G} \setminus S</tex> соединена ребром паросочетания <tex>M</tex> с какой-то вершиной из <tex>S</tex>. Иначе мы не сможем покрыть паросочетанием все вершины этой компоненты связности и получим противоречие с тем, что полное паросочетание существует по условию теоремы. Таким образом, получаем, что <tex>\mathrm{odd}({G} \setminus S) \leqslant \left\vert S \right\vert</tex>.

Пусть для графа <tex>{G}</tex> выполнено, что <tex>\mathrm{odd}({G} \setminus S) \leqslant \left\vert S \right\vert</tex>, но полного паросочетания в этом графе не существует.

Рассмотрим граф <tex>{G'}</tex> и множество вершин <tex>U</tex> (из леммы). Так как число нечетных компонент не увеличивается при добавлении новых ребер, то <tex>\forall S \subset {V}</tex> выполнено <tex>\mathrm{odd}({G'} \setminus S) \leqslant \mathrm{odd}({G} \setminus S) \leqslant \left\vert S \right\vert</tex>. По лемме, доказанной выше: <tex>{G'} \setminus U</tex> {{---}} объединение несвязных полных графов.

Очевидно, что в каждой четной компоненте связности графа <tex>{G'} \setminus U</tex> мы можем построить полное паросочетание. В каждой нечетной компоненте этого графа построим паросочетание, которое покрывает все вершины кроме одной, оставшуюся непокрытой вершину, соединим с какой-то вершиной множества <tex>U</tex>. При этом мы будем использовать различные вершины из <tex>U</tex>, это возможно, так как <tex>\mathrm{odd}({G'} \setminus U) \leqslant \left\vert U \right\vert</tex>. Если все вершины множества <tex>U</tex> оказались покрытыми, то мы получили полное паросочетание в графе <tex>{G'}</tex>. Противоречие, так как по построению в <tex>{G'}</tex> нет полного паросочетания.

Значит, в <tex>U</tex> осталось какое-то количество непокрытых вершин, при этом их четное число, потому что число вершин в <tex>{G'}</tex> четно, так как <tex>\mathrm{odd}({G'} \setminus \varnothing) \leqslant \left\vert \varnothing \right\vert = 0</tex> и уже покрыто паросочетанием четное число вершин. Так как в множество <tex>U</tex> входят вершины, которые в <tex>{G'}</tex> смежны со всеми остальными, то мы сможем разбить оставшиеся вершины на пары и покрыть их паросочетанием.

== Примечание См. также==* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]* [[Декомпозиция Эдмондса-Галлаи]] ==Примечания==