Gallai kilétei

A gráfelméletben a Gallai-azonosságok egy tetszőleges gráf numerikus jellemzői közötti kapcsolatok : függetlenségi szám , csúcsfedőszám , illesztési szám és élfedőszám . $G$ $\alpha (G)$ $\tau (G)$ $\nu (G)$ $\rho (G)$

A személyazonosságokat Gallai Tibor magyar matematikus tette közzé 1959 - ben 1Maga Gallai azt állította, hogy ezeket az eredményeket már 1932-ben megszerezte, miközben úgy vélte, hogy Koenig akkor már tudott róluk.

Gallai első identitása

Bármely gráfban teljesül az összefüggés . $G=(V,E)$ $\alpha (G)+\tau (G)=|V|$

Bizonyítás

Legyen a legkisebb csúcsfedő a gráfban . Tekintsünk egy csúcskészletet . Mivel bármely él a halmaz legalább egy csúcsára esik , egyetlen él sem köt össze két csúcsot a halmazban . Ezért van egy független csúcshalmaz a gráfban , és mérete nem haladja meg a legnagyobb független csúcshalmaz méretét, azaz . $T$ $G$ $V\setminus T$ $e\in E$ $T$ $V\setminus T$ $V\setminus T$ $G$ $|V|-\tau (G)$ $\alpha (G)$

Figyelembe véve a gráf legnagyobb független csúcskészletét, és ugyanezt az okoskodást fordítva, megkapjuk az egyenlőtlenséget , amely az első egyenlőtlenséggel együtt . $G$ $|V|-\alpha (G)\geq \tau (G)$ $\alpha (G)+\tau (G)=|V|$

Gallai második identitása

Minden olyan gráfban , amely nem tartalmaz izolált csúcsokat (azaz 0 fokú csúcsokat), a következő összefüggés érvényesül . $G=(V,E)$ $\nu (G)+\rho (G)=|V|$

Jegyzet:

Ha van legalább egy izolált csúcs a gráfban, akkor nincs élfedés, ezért az élfedések száma nincs meghatározva. $\rho (G)$

Bizonyítás

Tekintsük a gráf legkisebb élfedését . Ha ciklusokat tartalmazna , akkor a ciklus egyik élét el lehet távolítani, így eggyel kisebb élfedést kapunk. Ezért egy erdőt alkot a csúcsok halmazán , és az egyenlőség teljesül , ahol az ebben az erdőben lévő kapcsolódási összetevők száma. Minden egyes összekapcsolt komponensből egy élt veszünk, és egy méretű gráfban egy illesztést kapunk . Ezért a legnagyobb egyezés mérete . $R$ $G$ $R$ $R$ $V$ $|V|-|R|=K$ $K$ $G$ $|V|-\rho (G)$ $\nu (G)\geq |V|-\rho (G)$

Ezután vegye figyelembe a legnagyobb egyezést a grafikonon . Telíti a gráf csúcsait , ezért a csúcsok telítetlenek maradnak. Vegyünk egy élt a gráf minden telítetlen csúcsához, jelöljük az ilyen élek halmazát . Ha legalább egy él két telítetlen csúcsot köt össze egyszerre, akkor ezt az élt hozzá lehetne adni az illesztéshez , ami lehetetlen, mivel ez a legnagyobb egyezés. Ezért a készlet pontosan éleket tartalmaz. A halmaz egy élfedő a gráfban , ezért mérete nem kisebb, mint a legkisebb élfedő mérete . $N$ $G$ $2\cdot \nu (G)$ $G$ $|V|-2\cdot \nu (G)$ $N_1$ $N_1$ $N$ $N_1$ $|V|-2\cdot \nu (G)$ ${\displaystyle N\cup N_{1))$ $G$ $|V|-\nu (G)$ $\rho (G)$

A és az egyenlőtlenségeket kombinálva megkapjuk a kívánt azonosságot . $\nu (G)\geq |V|-\rho (G)$ $|V|-\nu (G)\geq \rho (G)$ $\nu (G)+\rho (G)=|V|$

Linkek

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