Теорема Татта о существовании полного паросочетания
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Определение: |
компонента связности, содержащая нечетное число вершин. | — число нечетных компонент связности в графе , где нечетная компонента (англ. odd component) — это
Определение: |
Множество Татта графа | — множество , для которого выполнено условие:
Критерий Татта
Пусть полного паросочетания, но оно появляется при добавлении любого нового ребра.
— граф, полученный из добавлением ребер, при этом в нетТак как новых вершин не добавлялось, то
Пусть
.Очевидно, что
, потому что — не полный граф.Лемма: |
— объединение несвязных полных графов. |
Доказательство: |
Пусть это не так, тогда существуют вершины , такие что , но . Так как , то .По построению в графе существует полное паросочетание . Аналогично, в графе существует полное паросочетание . Так как в нет полного паросочетания, то и .Возможны два случая:
|
Теорема Татта
Теорема: |
В графе существует полное паросочетание выполнено условие: (то есть в графе нет ни одного множества Татта) |
Доказательство: |
Одна из вершин каждой нечетной компоненты связности графа соединена ребром паросочетания с какой-то вершиной из . Иначе мы не сможем покрыть паросочетанием все вершины этой компоненты связности и получим противоречие с тем, что полное паросочетание существует по условию теоремы. Таким образом, получаем, что .
Рассмотрим граф и множество вершин (из леммы). Так как число нечетных компонент не увеличивается при добавлении новых ребер, то выполнено . По лемме, доказанной выше: — объединение несвязных полных графов.Очевидно, что в каждой четной компоненте связности графа мы можем построить полное паросочетание. В каждой нечетной компоненте этого графа построим паросочетание, которое покрывает все вершины кроме одной, оставшуюся непокрытой вершину, соединим с какой-то вершиной множества . При этом мы будем использовать различные вершины из , это возможно, так как . Если все вершины множества оказались покрытыми, то мы получили полное паросочетание в графе . Противоречие, так как по построению в нет полного паросочетания.Значит, в Таким образом, получили в осталось какое-то количество непокрытых вершин, при этом их четное число, потому что число вершин в четно, так как и уже покрыто паросочетанием четное число вершин. Так как в множество входят вершины, которые в смежны со всеми остальными, то мы сможем разбить оставшиеся вершины на пары и покрыть их паросочетанием. полное паросочетание, что противоречит тому, как мы задали этот граф изначально. Значит, начальное предположение не верно, и в существует полное паросочетание. |
См. также
Примечания
Источники информации
- Д.В Карпов. Теория графов (2 глава, стр. 29)
- Wikipedia — Tutte theorem