Identitățile lui Gallai

Identitățile Gallai în teoria grafurilor sunt relații între caracteristicile numerice ale unui graf arbitrar : numărul de independență , numărul de acoperire a vârfurilor , numărul de potrivire și numărul de acoperire a muchiei . $G$ $\alpha (G)$ $\tau (G)$ $\nu (G)$ $\rho (G)$

Identităţile au fost publicate de matematicianul ungur Tibor Gallai în 1959 1Gallai însuși a susținut că a obținut aceste rezultate încă din 1932, în timp ce credea că Koenig știa deja despre ele în acel moment.

Prima identitate a lui Gallai

În orice grafic , relația este satisfăcută . $G=(V,E)$ $\alpha (G)+\tau (G)=|V|$

Dovada

Fie cea mai mică acoperire a vârfurilor din grafic . Luați în considerare un set de vârfuri . Deoarece orice muchie este incidentă la cel puțin un vârf din mulțime , nicio muchie nu conectează două vârfuri în mulțime . Prin urmare, este un set independent de vârfuri în grafic , iar dimensiunea sa nu depășește dimensiunea celui mai mare set independent de vârfuri, adică . $T$ $G$ $V\setminus T$ $e\in E$ $T$ $V\setminus T$ $V\setminus T$ $G$ $|V|-\tau (G)$ $\alpha (G)$

Considerând cea mai mare mulțime independentă de vârfuri din grafic și făcând același raționament invers, obținem inegalitatea , care împreună cu prima inegalitate dă . $G$ $|V|-\alpha (G)\geq \tau (G)$ $\alpha (G)+\tau (G)=|V|$

A doua identitate a lui Gallai

În orice grafic care nu conține vârfuri izolate (adică vârfuri cu gradul 0), următoarea relație este valabilă . $G=(V,E)$ $\nu (G)+\rho (G)=|V|$

Notă:

Dacă există cel puțin un vârf izolat în grafic, atunci nu există acoperire de margine, prin urmare, numărul de acoperire de margine nu este definit. $\rho (G)$

Dovada

Luați în considerare cea mai mică acoperire de margine din grafic . Dacă ar conține cicluri , atunci ar fi posibilă îndepărtarea uneia dintre marginile ciclului, obținându-se o acoperire de margine cu o dimensiune mai mică. Prin urmare, formează o pădure pe setul de vârfuri , iar egalitatea este valabilă , unde este numărul de componente de conectivitate din această pădure. Luând o muchie de la fiecare componentă conectată, obținem o potrivire într-un grafic de dimensiune . Prin urmare, dimensiunea celei mai mari potriviri este . $R$ $G$ $R$ $R$ $V$ $|V|-|R|=K$ $K$ $G$ $|V|-\rho (G)$ $\nu (G)\geq |V|-\rho (G)$

Apoi, luați în considerare cea mai mare potrivire din grafic . Saturează vârfurile graficului , prin urmare vârfurile rămân nesaturate. Să luăm câte o muchie pentru fiecare vârf nesaturat al graficului, notăm setul de astfel de muchii . Dacă cel puțin o muchie din ar conecta două vârfuri nesaturate simultan, această muchie ar putea fi adăugată la potrivire , ceea ce este imposibil, deoarece aceasta este cea mai mare potrivire. Prin urmare, setul conține exact margini. Setul este un capac de margine în grafic , prin urmare, dimensiunea sa nu este mai mică decât dimensiunea celui mai mic capac de margine . $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)$

Combinând inegalitățile și , obținem identitatea dorită . $\nu (G)\geq |V|-\rho (G)$ $|V|-\nu (G)\geq \rho (G)$ $\nu (G)+\rho (G)=|V|$

Link -uri

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