Gallais identiteter

Gallai-identiteter i grafteorin är relationer mellan de numeriska egenskaperna hos en godtycklig graf : oberoende nummer , vertextäckningsnummer , matchande nummer och kanttäckningsnummer . $G$ $\alpha (G)$ $\tau (G)$ $\nu (G)$ $\rho (G)$

Identiteterna publicerades av den ungerske matematikern Tibor Gallai 1959 1Gallai själv hävdade att han hade fått dessa resultat redan 1932, samtidigt som han trodde att Koenig redan visste om dem vid den tiden.

Gallais första identitet

I vilken graf som helst är förhållandet uppfyllt . $G=(V,E)$ $\alpha (G)+\tau (G)=|V|$

Bevis

Låt vara det minsta vertextäcket i grafen . Betrakta en uppsättning av hörn . Eftersom vilken kant som helst faller samman med minst en hörn i mängden , förbinder ingen kant två hörn i mängden . Därför är en oberoende uppsättning av hörn i grafen , och dess storlek överstiger inte storleken på den största oberoende uppsättningen av hörn, det vill säga . $T$ $G$ $V\setminus T$ $e\in E$ $T$ $V\setminus T$ $V\setminus T$ $G$ $|V|-\tau (G)$ $\alpha (G)$

Med tanke på den största oberoende uppsättningen av hörn i grafen och gör samma resonemang omvänt, får vi olikheten , som tillsammans med den första olikheten ger . $G$ $|V|-\alpha (G)\geq \tau (G)$ $\alpha (G)+\tau (G)=|V|$

Gallais andra identitet

I varje graf som inte innehåller isolerade hörn (d.v.s. hörn med grad 0), gäller följande relation . $G=(V,E)$ $\nu (G)+\rho (G)=|V|$

Notera:

Om det finns minst en isolerad vertex i grafen, så finns det inget kantskydd, därför är antalet kantskydd inte definierat. $\rho (G)$

Bevis

Betrakta det minsta kantskyddet i grafen . Om den innehöll cykler skulle det vara möjligt att ta bort en av cykelns kanter och erhålla en kantbeläggning av storleken en mindre. Därför bildar en skog på uppsättningen av hörn , och jämlikheten gäller , där är antalet anslutningskomponenter i denna skog. Om vi tar en kant från varje ansluten komponent får vi en matchning i en graf med storlek . Därför är storleken på den största matchningen . $R$ $G$ $R$ $R$ $V$ $|V|-|R|=K$ $K$ $G$ $|V|-\rho (G)$ $\nu (G)\geq |V|-\rho (G)$

Tänk sedan på den största matchningen i grafen . Den mättar grafens hörn , så att hörnen förblir omättade. Låt oss ta en kant för varje omättad vertex i grafen, beteckna uppsättningen av sådana kanter . Om minst en kant från skulle ansluta två omättade hörn på en gång, kan denna kant läggas till matchningen , vilket är omöjligt, eftersom detta är den största matchningen. Därför innehåller setet exakt kanter. Uppsättningen är ett kantskydd i grafen , därför är dess storlek inte mindre än storleken på det minsta kantskyddet . $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)$

Genom att kombinera ojämlikheterna och får vi den önskade identiteten . $\nu (G)\geq |V|-\rho (G)$ $|V|-\nu (G)\geq \rho (G)$ $\nu (G)+\rho (G)=|V|$

Länkar

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