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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

[править | править код]

В любом графе выполняется соотношение .

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

[править | править код]

Пусть — наименьшее вершинное покрытие в графе . Рассмотрим множество вершин . Поскольку любое ребро инцидентно хотя бы одной вершине из множества , ни одно ребро не соединяет две вершины из множества . Следовательно, является независимым множеством вершин в графе , и его размер не превосходит размера наибольшего независимого множества вершин, то есть, .

Рассмотрев наибольшее независимое множество вершин в графе и проделав такое же рассуждение в обратную сторону, получим неравенство , что в совокупности с первым неравенством даёт .

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

[править | править код]

В любом графе , не содержащем изолированных вершин (т.е. вершин со степенью 0), выполняется соотношение .

Примечание:

Если в графе есть хоть одна изолированная вершина, то рёберного покрытия не существует, следовательно, число рёберного покрытия не определено.

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

[править | править код]

Рассмотрим наименьшее рёберное покрытие в графе . Если бы содержало циклы, то можно было бы удалить одно из рёбер цикла, получив рёберное покрытие размера на единицу меньше. Следовательно, образует лес на множестве вершин , и выполняется равенство , где — количество компонент связности в этом лесе. Взяв из каждой компоненты связности по одному ребру, получим паросочетание в графе размера . Следовательно, размер наибольшего паросочетания .

Далее, рассмотрим наибольшее паросочетание в графе . Оно насыщает вершин графа , следовательно, вершин остаются ненасыщенными. Возьмём для каждой ненасыщенной вершины графа по одному ребру, обозначим множество таких рёбер . Если хотя бы одно ребро из соединяло бы сразу две ненасыщенные вершины, это ребро можно было бы добавить в паросочетание , что невозможно, поскольку это наибольшее паросочетание. Значит, во множестве ровно рёбер. Множество является рёберным покрытием в графе , следовательно, его размер не меньше размера наименьшего рёберного покрытия .

Объединив неравенства и , получим искомое тождество .


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