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


Тождества Галлаи в теории графов — это соотношения между численными характеристиками произвольного графа G {displaystyle G} : числом независимости α ( G ) {displaystyle alpha (G)} , числом вершинного покрытия τ ( G ) {displaystyle au (G)} , числом паросочетания ν ( G ) {displaystyle u (G)} и числом рёберного покрытия ρ ( G ) {displaystyle ho (G)} .

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

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

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

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

Пусть T {displaystyle T} — наименьшее вершинное покрытие в графе G {displaystyle G} . Рассмотрим множество вершин V ∖ T {displaystyle Vsetminus T} . Поскольку любое ребро e ∈ E {displaystyle ein E} инцидентно хотя бы одной вершине из множества T {displaystyle T} , ни одно ребро не соединяет две вершины из множества V ∖ T {displaystyle Vsetminus T} . Следовательно, V ∖ T {displaystyle Vsetminus T} является независимым множеством вершин в графе G {displaystyle G} , и его размер | V | − τ ( G ) {displaystyle |V|- au (G)} не превосходит размера наибольшего независимого множества вершин, то есть, α ( G ) {displaystyle alpha (G)} .

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

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

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

Примечание:

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

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

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

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

Объединив неравенства ν ( G ) ≥ | V | − ρ ( G ) {displaystyle u (G)geq |V|- ho (G)} и | V | − ν ( G ) ≥ ρ ( G ) {displaystyle |V|- u (G)geq ho (G)} , получим искомое тождество ν ( G ) + ρ ( G ) = | V | {displaystyle u (G)+ ho (G)=|V|} .