В математической дисциплине теории графов теорема Тутта , названная в честь Уильяма Томаса Тутта , является характеристикой конечных неориентированных графов с совершенными паросочетаниями . Это частный случай формулы Тутта–Бержа .
Цель состоит в том, чтобы охарактеризовать все графы, не имеющие идеального паросочетания. Начнем с самого очевидного случая графа без идеального паросочетания: графа с нечетным числом вершин. В таком графе любое паросочетание оставляет по крайней мере одну непарную вершину, поэтому оно не может быть идеальным.
Немного более общим случаем является несвязный граф, в котором один или несколько компонентов имеют нечетное число вершин (даже если общее число вершин четное). Назовем такие компоненты нечетными компонентами . В любом сопоставлении каждая вершина может быть сопоставлена только вершинам в том же компоненте. Следовательно, любое сопоставление оставляет по крайней мере одну несовпадающую вершину в каждом нечетном компоненте, поэтому оно не может быть идеальным.
Далее рассмотрим граф G с вершиной u, такой что если удалить из G вершину u и ее смежные ребра, то оставшийся граф (обозначаемый G − u ) будет иметь два или более нечетных компонента. Как и выше, любое сопоставление оставляет в каждом нечетном компоненте по крайней мере одну вершину, которая не сопоставлена с другими вершинами в том же компоненте. Такая вершина может быть сопоставлена только с u . Но поскольку есть две или более не сопоставленных вершин, и только одна из них может быть сопоставлена с u , по крайней мере одна другая вершина остается не сопоставленной, поэтому сопоставление не является идеальным.
Наконец, рассмотрим граф G с множеством вершин U таким образом, что если удалить из G вершины из U и все смежные с ними ребра, то оставшийся граф (обозначаемый G − U ) будет иметь более | U | нечетных компонент. Как объяснялось выше, любое сопоставление оставляет по крайней мере одну непарную вершину в каждой нечетной компоненте, и они могут быть сопоставлены только вершинам U , но для всех этих непарных вершин на U недостаточно вершин , поэтому сопоставление не является идеальным.
Мы пришли к необходимому условию: если G имеет совершенное паросочетание, то для каждого подмножества вершин U в G граф G − U имеет не более | U | нечетных компонент. Теорема Тутта утверждает, что это условие является как необходимым, так и достаточным для существования совершенного паросочетания.
Граф G = ( V , E ) имеет совершенное паросочетание тогда и только тогда, когда для каждого подмножества U из V подграф G − U имеет не более | U | нечетных компонентов ( связных компонентов, имеющих нечетное число вершин ). [1]
Сначала запишем условие:
где обозначает число нечетных компонент подграфа, индуцированного .
Необходимость (∗): Это направление уже обсуждалось в разделе «Интуиция» ниже, но давайте подведем итоги доказательства здесь. Рассмотрим граф G с совершенным паросочетанием. Пусть U — произвольное подмножество V . Удалим U . Пусть C — произвольный нечетный компонент в G − U . Поскольку G имеет совершенное паросочетание, по крайней мере одна вершина в C должна быть сопоставлена вершине в U . Следовательно, каждый нечетный компонент имеет по крайней мере одну вершину, сопоставленную вершине в U . Поскольку каждая вершина в U может находиться в этом отношении не более чем с одним связным компонентом (из-за того, что она сопоставлена не более одного раза в совершенном паросочетании), нечетное ( G − U ) ≤ | U | . [2]
Достаточность (∗): Пусть G — произвольный граф без идеального паросочетания. Найдем так называемый нарушитель Тутте , то есть подмножество S из V такое, что | S | < нечетное ( G − S ) . Можно предположить, что G является рёберно-максимальным, то есть G + e имеет идеальное паросочетание для каждого ребра e, которого еще нет в G. Действительно, если мы найдем нарушитель Тутте S в рёберно-максимальном графе G , то S также будет нарушителем Тутте в каждом остовном подграфе G , так как каждый нечетный компонент G − S будет разделен на возможно большее количество компонентов, по крайней мере один из которых снова будет нечетным.
Мы определяем S как множество вершин со степенью | V | − 1. Сначала рассмотрим случай, когда все компоненты G − S являются полными графами. Тогда S должен быть нарушителем Тутте, поскольку если нечетное ( G − S ) ≤ | S | , то мы могли бы найти идеальное паросочетание, сопоставив одну вершину из каждого нечетного компонента с вершиной из S и объединив все остальные вершины (это сработает, если только | V | нечетное, но тогда ∅ является нарушителем Тутте).
Теперь предположим, что K является компонентой G − S и x , y ∈ K являются вершинами такими, что xy ∉ E . Пусть x , a , b ∈ K являются первыми вершинами на кратчайшем x , y -пути в K . Это гарантирует, что xa , ab ∈ E и xb ∉ E . Поскольку a ∉ S , существует вершина c такая, что ac ∉ E . Из рёберной максимальности G , мы определяем M 1 как совершенное паросочетание в G + xb и M 2 как совершенное паросочетание в G + ac . Заметим, что, несомненно, xb ∈ M 1 и ac ∈ M 2 .
Пусть P будет максимальным путем в G , который начинается из c с ребром из M 1 и чьи ребра чередуются между M 1 и M 2 . Как может закончиться P ? Если только мы не придем к «специальной» вершине, такой как x , a или b , мы всегда можем продолжить: c является M 2 -сопоставленным с ca , поэтому первое ребро P не находится в M 2 , поэтому вторая вершина является M 2 -сопоставленным с другим ребром, и мы продолжаем таким образом.
Пусть v обозначает последнюю вершину P . Если последнее ребро P находится в M 1 , то v должно быть a , так как в противном случае мы могли бы продолжить с ребром из M 2 (даже чтобы прийти к x или b ). В этом случае мы определяем C := P + ac . Если последнее ребро P находится в M 2 , то, конечно, v ∈ { x , b } по аналогичной причине и мы определяем C := P + va + ac .
Теперь C — это цикл в G + ac четной длины с каждым другим ребром в M 2 . Теперь мы можем определить M := M 2 Δ C (где Δ — симметрическая разность ), и мы получаем совершенное паросочетание в G , противоречие.
Формула Тутте –Бержа гласит, что размер максимального паросочетания графа равен . Эквивалентно, количество непарных вершин в максимальном паросочетании равно .
Эта формула следует из теоремы Тутта вместе с наблюдением, что имеет соответствие размера тогда и только тогда, когда граф, полученный путем добавления новых вершин, каждая из которых присоединена к каждой исходной вершине , имеет совершенное соответствие. Поскольку любой набор , который разделяется на более чем компонентов, должен содержать все новые вершины, (*) выполняется для тогда и только тогда, когда .
Для связных бесконечных графов, которые локально конечны (каждая вершина имеет конечную степень), выполняется обобщение условия Тутта: такие графы имеют совершенные паросочетания тогда и только тогда, когда нет конечного подмножества, удаление которого создает некоторое количество конечных нечетных компонентов, превышающих размер подмножества. [3]
