Gallain identiteetit

Gallai-identiteetit graafiteoriassa ovat suhteita mielivaltaisen graafin numeeristen ominaisuuksien välillä : riippumattomuusluku , kärjen peitenumero , täsmäysluku ja reunapeitenumero . $G$ $\alpha (G)$ $\tau (G)$ ${\näyttötyyli \nu (G)}$ ${\näyttötyyli \rho (G)}$

Unkarilainen matemaatikko Tibor Gallai julkaisi henkilöllisyydet vuonna 1959 1Gallai itse väitti saaneensa nämä tulokset jo vuonna 1932, mutta uskoi, että Koenig tiesi niistä jo tuolloin.

Gallain ensimmäinen identiteetti

Missä tahansa kuvaajassa relaatio täyttyy . $G=(V,E)$ $\alpha (G)+\tau (G)=|V|$

Todiste

Antaa olla pienin pisteen kansi kaaviossa . Harkitse joukkoa kärkipisteitä . Koska mikä tahansa reuna osuu vähintään yhteen joukon kärkeen , mikään reuna ei yhdistä kahta kärkeä joukossa . Siksi graafissa on itsenäinen kärkijoukko , ja sen koko ei ylitä suurimman riippumattoman kärkijoukon kokoa, eli . $T$ $G$ $V\setminus T$ $e\in E$ $T$ $V\setminus T$ $V\setminus T$ $G$ $|V|-\tau (G)$ $\alpha (G)$

Kun otetaan huomioon graafin suurin riippumaton kärkijoukko ja tehdään sama päättely käänteisesti, saadaan epäyhtälö , joka yhdessä ensimmäisen epäyhtälön kanssa antaa . $G$ $|V|-\alpha (G)\geq \tau (G)$ $\alpha (G)+\tau (G)=|V|$

Gallain toinen identiteetti

Missä tahansa graafissa , joka ei sisällä eristettyjä pisteitä (eli pisteitä, joiden aste on 0), seuraava relaatio pätee . $G=(V,E)$ $\nu (G)+\rho (G)=|V|$

merkintä:

Jos graafissa on ainakin yksi eristetty kärki, niin reunapeitettä ei ole, joten reunapeitteen lukumäärää ei ole määritelty. ${\näyttötyyli \rho (G)}$

Todiste

Tarkastellaan kaavion pienintä reunapeitettä . Jos se sisältäisi jaksoja , olisi mahdollista poistaa yksi syklin reunoista, jolloin saataisiin yhden kokoinen reunapeite. Siksi muodostaa metsän kärkijoukolle ja yhtäläisyys pätee , missä on tämän metsän liitettävyyskomponenttien lukumäärä. Ottamalla yksi reuna jokaisesta yhdistetystä komponentista, saamme sovituksen koon kuvaajassa . Siksi suurimman vastaavuuden koko on . $R$ $G$ $R$ $R$ $V$ $|V|-|R|=K$ $K$ $G$ $|V|-\rho (G)$ $\nu (G)\geq |V|-\rho (G)$

Harkitse seuraavaksi kaavion suurinta vastaavuutta . Se kyllästää graafin kärjet , joten kärjet pysyvät tyydyttymättöminä. Otetaan yksi reuna kullekin graafin tyydyttymättömälle kärjelle, merkitään tällaisten reunojen joukko . Jos ainakin yksi reuna kohteesta yhdistäisi kaksi tyydyttymätöntä kärkeä kerralla, tämä reuna voitaisiin lisätä sovitukseen , mikä on mahdotonta, koska tämä on suurin vastaavuus. Näin ollen sarja sisältää täsmälleen reunat. Joukko on kaavion reunapeite , joten sen koko ei ole pienempi kuin pienimmän reunakannen koko . $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)$ ${\näyttötyyli \rho (G)}$

Yhdistämällä epäyhtälöt ja , saadaan haluttu identiteetti . $\nu (G)\geq |V|-\rho (G)$ $|V|-\nu (G)\geq \rho (G)$ $\nu (G)+\rho (G)=|V|$

Linkit

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