Gallais identiteter

Gallai-identiteter i grafteori er forhold mellem de numeriske karakteristika for en vilkårlig graf : uafhængighedsnummer , vertex-dækningsnummer , matchende nummer og kantdækselnummer . $G$ $\alpha (G)$ $\tau (G)$ $\nu (G)$ $\rho (G)$

Identiteterne blev offentliggjort af den ungarske matematiker Tibor Gallai i 1959 1Gallai hævdede selv, at han havde opnået disse resultater allerede i 1932, mens han mente, at Koenig allerede kendte til dem på det tidspunkt.

Gallais første identitet

I enhver graf er relationen opfyldt . $G=(V,E)$ $\alpha (G)+\tau (G)=|V|$

Bevis

Lad være det mindste toppunktsdæksel i grafen . Overvej et sæt toppunkter . Da enhver kant falder sammen med mindst ét toppunkt i sættet , forbinder ingen kant to toppunkter i sættet . Derfor er et uafhængigt sæt af knudepunkter i grafen , og dets størrelse overstiger ikke størrelsen af det største uafhængige sæt knudepunkter, det vil sige . $T$ $G$ $V\setminus T$ $e\in E$ $T$ $V\setminus T$ $V\setminus T$ $G$ $|V|-\tau (G)$ $\alpha (G)$

Tager vi det største uafhængige sæt af hjørner i grafen i betragtning og gør det samme ræsonnement omvendt, får vi uligheden , som sammen med den første ulighed giver . $G$ $|V|-\alpha (G)\geq \tau (G)$ $\alpha (G)+\tau (G)=|V|$

Gallais anden identitet

I enhver graf , der ikke indeholder isolerede knudepunkter (dvs. knudepunkter med grad 0), gælder følgende relation . $G=(V,E)$ $\nu (G)+\rho (G)=|V|$

Bemærk:

Hvis der er mindst et isoleret toppunkt i grafen, er der ingen kantafdækning, derfor er antallet af kantafdækninger ikke defineret. $\rho (G)$

Bevis

Overvej det mindste kantdæksel i grafen . Hvis den indeholdt cyklusser , så ville det være muligt at fjerne en af kanterne på cyklen og opnå en kantbeklædning i størrelse en mindre. Danner derfor en skov på sættet af toppunkter , og ligheden gælder , hvor er antallet af forbindelseskomponenter i denne skov. Ved at tage en kant fra hver tilsluttet komponent opnår vi en matchning i en graf med størrelse . Derfor er størrelsen på den største matchning . $R$ $G$ $R$ $R$ $V$ $|V|-|R|=K$ $K$ $G$ $|V|-\rho (G)$ $\nu (G)\geq |V|-\rho (G)$

Overvej derefter den største matchning i grafen . Det mætter hjørnerne af grafen , hvorfor hjørnerne forbliver umættede. Lad os tage en kant for hvert umættet toppunkt på grafen, betegne sættet af sådanne kanter . Hvis mindst én kant fra ville forbinde to umættede hjørner på én gang, kunne denne kant føjes til matchningen , hvilket er umuligt, da dette er den største matchning. Derfor indeholder sættet nøjagtigt kanter. Sættet er et kantdæksel i grafen , derfor er dets størrelse ikke mindre end størrelsen på det mindste kantdæksel . $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\kop N_{1))$ $G$ $|V|-\nu (G)$ $\rho (G)$

Ved at kombinere ulighederne og opnår vi den ønskede identitet . $\nu (G)\geq |V|-\rho (G)$ $|V|-\nu (G)\geq \rho (G)$ $\nu (G)+\rho (G)=|V|$

Gallais identiteter

Gallais første identitet

Bevis

Gallais anden identitet

Bevis

Links