Gallaiho identita

Gallaiovy identity v teorii grafů jsou vztahy mezi numerickými charakteristikami libovolného grafu : číslo nezávislosti , krycí číslo vrcholu , odpovídající číslo a krycí číslo hrany . $G$ $\alpha (G)$ $\tau (G)$ $\nu (G)$ $\rho (G)$

Totožnosti publikoval maďarský matematik Tibor Gallai v roce 1959 1Sám Gallai tvrdil, že tyto výsledky získal již v roce 1932, přičemž věřil, že Koenig o nich v té době již věděl.

Gallaiova první identita

V každém grafu je vztah splněn . $G=(V,E)$ $\alpha (G)+\tau (G)=|V|$

Důkaz

Dovolit být nejmenší pokrytí vrcholu v grafu . Uvažujme množinu vrcholů . Protože jakákoli hrana je incidentní s alespoň jedním vrcholem v množině , žádná hrana nespojuje dva vrcholy v množině . Proto je v grafu nezávislá množina vrcholů a její velikost nepřesahuje velikost největší nezávislé množiny vrcholů, tedy . $T$ $G$ $V\setminus T$ $e\in E$ $T$ $V\setminus T$ $V\setminus T$ $G$ $|V|-\tau (G)$ $\alpha (G)$

Pokud vezmeme v úvahu největší nezávislou množinu vrcholů v grafu a provedeme stejnou úvahu obráceně, dostaneme nerovnost , která spolu s první nerovností dává . $G$ $|V|-\alpha (G)\geq \tau (G)$ $\alpha (G)+\tau (G)=|V|$

Gallaiova druhá identita

V každém grafu , který neobsahuje izolované vrcholy (tj. vrcholy se stupněm 0), platí následující vztah . $G=(V,E)$ $\nu (G)+\rho (G)=|V|$

Poznámka:

Pokud je v grafu alespoň jeden izolovaný vrchol, není zde žádné krytí hran, proto není definován počet krytí hran . $\rho (G)$

Důkaz

Zvažte nejmenší pokrytí hran v grafu . Pokud by obsahoval cykly , pak by bylo možné odstranit jednu z hran cyklu a získat tak pokrytí hran o velikosti o jednu menší. Tvoří tedy les na množině vrcholů a platí rovnost , kde je počet komponent konektivity v tomto lese. Vezmeme-li jednu hranu z každé připojené součásti, získáme shodu v grafu velikosti . Proto je velikost největší shody . $R$ $G$ $R$ $R$ $PROTI$ $|V|-|R|=K$ $K$ $G$ $|V|-\rho (G)$ $\nu (G)\geq |V|-\rho (G)$

Dále zvažte největší shodu v grafu . Nasycuje vrcholy grafu , takže vrcholy zůstávají nenasycené. Vezměme jednu hranu pro každý nenasycený vrchol grafu, označme množinu takových hran . Pokud by alespoň jedna hrana z spojovala dva nenasycené vrcholy najednou, mohla by být tato hrana přidána do párování , což je nemožné, protože se jedná o největší shodu. Sada tedy obsahuje přesně hrany. Množina je v grafu pokrytím hran , proto jeho velikost není menší než velikost nejmenšího krytu hran . $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)$

Kombinací nerovností a získáme požadovanou identitu . $\nu (G)\geq |V|-\rho (G)$ $|V|-\nu (G)\geq \rho (G)$ $\nu (G)+\rho (G)=|V|$

Odkazy

↑ T. Gallai: Über extreme Punkt- und Kantenmengen. Ann. Univ. sci. Budapešť. Sekta Eötvös. Matematika. 2 (1959), 133–138.