Тотожності Галлаї

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

Тотожності 1959 року опублікував угорський математик ^[en]. Сам Галлаї стверджував, що отримав ці результати ще 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.