Введение

Характеристика графов с полным соответствием

В математической дисциплине теории графов теорема Тютте, названная в честь Уильяма Томаса Тютте, является характеристикой конечных неориентированных графов с полным соответствием. Она является обобщением теоремы Холла о браке с двудольных графов на произвольные графы. Это частный случай формулы Тютте — Берже.

Интуиция

Цель состоит в том, чтобы охарактеризовать все графы, не имеющие идеального паросочетания. Начнем с наиболее очевидного случая графа без идеального паросочетания: графа с нечетным числом вершин. В таком графе любое паросочетание оставляет по крайней мере одну несыгранную вершину, поэтому оно не может быть идеальным. Немного более общим случаем является несвязный граф, в котором один или несколько компонентов имеют нечетное число вершин (даже если общее число вершин четно). Назовем такие компоненты нечетными компонентами. В любом паросочетании каждая вершина может быть сопоставлена только с вершинами в том же компоненте. Следовательно, любое паросочетание оставляет по крайней мере одну несыгранную вершину в каждом нечетном компоненте, поэтому оно не может быть идеальным. Далее рассмотрим граф G с вершиной u такой, что если удалить из G вершину u и все смежные с ней ребра, то оставшийся граф (обозначаемый G − u) имеет два или более нечетных компонента. Как и выше, любое паросочетание оставляет в каждом нечетном компоненте по крайней мере одну вершину, не сопоставленную с другими вершинами в том же компоненте. Такая вершина может быть сопоставлена только с u. Но поскольку есть две или более несыгранных вершин, и только одна из них может быть сопоставлена с u, по крайней мере одна другая вершина остается несыгранной, поэтому паросочетание не является идеальным. Наконец, рассмотрим граф G с множеством вершин U таким, что если удалить из G вершины из U и все смежные с ними ребра, то оставшийся граф (обозначаемый G − U) имеет более чем <nowiki> нечетных компонентов. Как объяснено выше, любое паросочетание оставляет по крайней мере одну несыгранную вершину в каждом нечетном компоненте, и эти вершины могут быть сопоставлены только с вершинами из U, но на U недостаточно вершин для всех этих несыгранных вершин, поэтому паросочетание не является идеальным. Мы пришли к необходимому условию: если G имеет идеальное паросочетание, то для каждого подмножества вершин U в G граф G − U имеет не более <nowiki> нечетных компонентов. Теорема Тютте утверждает, что это условие является необходимым и достаточным для существования идеального паросочетания.

Теорема Тютте

Граф , , имеет совершенное паросочетание тогда и только тогда, когда для каждого подмножества U множества V подграф G − U имеет не более нечетных компонент (связных компонент, содержащих нечетное число вершин).

Эквивалентность формуле Тютте-Берге

Формула Тютте — Берже утверждает, что размер максимального паросочетания графа равен, эквивалентно, число непокрытых вершин в максимальном паросочетании равно. Эта формула вытекает из теоремы Тютте вместе с наблюдением, что граф имеет паросочетание размера *k*, если и только если граф, полученный путем добавления *k* новых вершин, каждая из которых соединена со всеми исходными вершинами графа, имеет совершенное паросочетание. Поскольку любое множество вершин, которое разделяет граф на более чем *k* компонент связности, должно содержать все новые вершины, (*) выполняется для *k*, если и только если *k* равно .

В бесконечных графах

Для связных бесконечных графов, локально конечных (то есть, каждая вершина имеет конечную степень), выполняется обобщение условия Тютте: такие графы имеют совершенные паросочетания тогда и только тогда, когда не существует конечного подмножества, удаление которого приводит к образованию числа конечных нечётных компонент, превышающего размер этого подмножества.