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

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

Тотожності 1959 року опублікував угорський математик Тібор Галлаї. Сам Галлаї стверджував, що отримав ці результати ще 1932 року, при цьому вважаючи, що Кеніг у той час про них вже знав.

Перша тотожність Галлаї

У будь-якому графі $G=(V,E)$ виконується співвідношення $\alpha (G)+\tau (G)=|V|$.

Доведення

Нехай $T$ — найменше вершинне покриття в графі $G$. Розглянемо множину вершин $V\setminus T$. Оскільки будь-яке ребро $e\in E$ інцидентне хоча б одній вершині з множини $T$, жодне ребро не з'єднує двох вершин із множини $V\setminus T$. Отже, $V\setminus T$ є незалежною множиною вершин у графі $G$, і її розмір $|V|-\tau (G)$ не перевищує розміру найбільшої незалежної множини вершин, тобто, $\alpha (G)$.

Розглянувши найбільшу незалежну множину вершин у графі $G$ і виконавши таке ж міркування у зворотний бік, отримаємо нерівність $|V|-\alpha (G)\geq \tau (G)$, що в сукупності з першою нерівністю дає $\alpha (G)+\tau (G)=|V|$.

Друга тотожність Галлаї

У будь-якому графі $G=(V,E)$, що не містить ізольованих вершин (тобто вершин зі степенем 0), виконується співвідношення $\nu (G)+\rho (G)=|V|$.

Примітка:

Якщо у графі є хоч одна ізольована вершина, то реберного покриття не існує, отже, число реберного покриття $\rho (G)$ не визначене.

Доведення

Розглянемо найменше реберне покриття $R$ у графі $G$. Якби $R$ містило цикл, то можна було б видалити одне з ребер циклу, отримавши реберне покриття розміру на одиницю менше. Отож, $R$ утворює ліс на множині вершин $V$, і виконується рівність $|V|-|R|=K$, де $K$ — кількість компонент зв'язності в цьому лісі. Взявши з кожної компоненти зв'язності по одному ребру, отримаємо парування в графі $G$ розміру $|V|-\rho (G)$. Отже, розмір найбільшого парування $\nu (G)\geq |V|-\rho (G)$.

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

Об'єднавши нерівності $\nu (G)\geq |V|-\rho (G)$ і $|V|-\nu (G)\geq \rho (G)$, отримаємо шукану тотожність $\nu (G)+\rho (G)=|V|$.