Тождества Галлаи

Тождества Галлаи в теории графов — это соотношения между численными характеристиками произвольного графа ${\displaystyle G}$: числом независимости ${\displaystyle \alpha (G)}$, числом вершинного покрытия ${\displaystyle \tau (G)}$, числом паросочетания ${\displaystyle \nu (G)}$ и числом рёберного покрытия ${\displaystyle \rho (G)}$.

Тождества опубликованы венгерским математиком Тибором Галлаи^[англ.] в 1959 году[1]. Сам Галлаи утверждал, что получил эти результаты ещё в 1932 году, при этом полагая, что в то время Кёнигу о них уже было известно.

Первое тождество Галлаи

В любом графе ${\displaystyle G=(V,E)}$ выполняется соотношение ${\displaystyle \alpha (G)+\tau (G)=|V|}$.

Доказательство

Пусть ${\displaystyle T}$ — наименьшее вершинное покрытие в графе ${\displaystyle G}$. Рассмотрим множество вершин ${\displaystyle V\setminus T}$. Поскольку любое ребро ${\displaystyle e\in E}$ инцидентно хотя бы одной вершине из множества ${\displaystyle T}$, ни одно ребро не соединяет две вершины из множества ${\displaystyle V\setminus T}$. Следовательно, ${\displaystyle V\setminus T}$ является независимым множеством вершин в графе ${\displaystyle G}$, и его размер ${\displaystyle |V|-\tau (G)}$ не превосходит размера наибольшего независимого множества вершин, то есть, ${\displaystyle \alpha (G)}$.

Рассмотрев наибольшее независимое множество вершин в графе ${\displaystyle G}$ и проделав такое же рассуждение в обратную сторону, получим неравенство ${\displaystyle |V|-\alpha (G)\geq \tau (G)}$, что в совокупности с первым неравенством даёт ${\displaystyle \alpha (G)+\tau (G)=|V|}$.

Второе тождество Галлаи

В любом графе ${\displaystyle G=(V,E)}$, не содержащем изолированных вершин (т.е. вершин со степенью 0), выполняется соотношение ${\displaystyle \nu (G)+\rho (G)=|V|}$.

Примечание:

Если в графе есть хоть одна изолированная вершина, то рёберного покрытия не существует, следовательно, число рёберного покрытия ${\displaystyle \rho (G)}$ не определено.

Доказательство

Рассмотрим наименьшее рёберное покрытие ${\displaystyle R}$ в графе ${\displaystyle G}$. Если бы ${\displaystyle R}$ содержало циклы, то можно было бы удалить одно из рёбер цикла, получив рёберное покрытие размера на единицу меньше. Следовательно, ${\displaystyle R}$ образует лес на множестве вершин ${\displaystyle V}$, и выполняется равенство ${\displaystyle |V|-|R|=K}$, где ${\displaystyle K}$ — количество компонент связности в этом лесе. Взяв из каждой компоненты связности по одному ребру, получим паросочетание в графе ${\displaystyle G}$ размера ${\displaystyle |V|-\rho (G)}$. Следовательно, размер наибольшего паросочетания ${\displaystyle \nu (G)\geq |V|-\rho (G)}$.

Далее, рассмотрим наибольшее паросочетание ${\displaystyle N}$ в графе ${\displaystyle G}$. Оно насыщает ${\displaystyle 2\cdot \nu (G)}$ вершин графа ${\displaystyle G}$, следовательно, ${\displaystyle |V|-2\cdot \nu (G)}$ вершин остаются ненасыщенными. Возьмём для каждой ненасыщенной вершины графа по одному ребру, обозначим множество таких рёбер ${\displaystyle N_{1}}$. Если хотя бы одно ребро из ${\displaystyle N_{1}}$ соединяло бы сразу две ненасыщенные вершины, это ребро можно было бы добавить в паросочетание ${\displaystyle N}$, что невозможно, поскольку это наибольшее паросочетание. Значит, во множестве ${\displaystyle N_{1}}$ ровно ${\displaystyle |V|-2\cdot \nu (G)}$ рёбер. Множество ${\displaystyle N\cup N_{1}}$ является рёберным покрытием в графе ${\displaystyle G}$, следовательно, его размер ${\displaystyle |V|-\nu (G)}$ не меньше размера наименьшего рёберного покрытия ${\displaystyle \rho (G)}$.

Объединив неравенства ${\displaystyle \nu (G)\geq |V|-\rho (G)}$ и ${\displaystyle |V|-\nu (G)\geq \rho (G)}$, получим искомое тождество ${\displaystyle \nu (G)+\rho (G)=|V|}$.

Ссылки

1. T. Gallai: Über extreme Punkt- und Kantenmengen. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 2 (1959), 133–138.