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

Тождества опубликованы венгерским математиком в 1959 году . Сам Галлаи утверждал, что получил эти результаты ещё в 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.