Függetlenségi szám

Egy gráf függetlenségi száma a benne lévő legnagyobb független csúcshalmaz mérete . $G$

Mivel a független halmaz probléma NP-teljes , nem ismertek olyan algoritmusok, amelyek a függetlenségi szám meghatározására egy tetszőleges gráfban polinomiális időben működnének.

Bármely gráfban a függetlenségi számot a csúcsfedő számhoz viszonyítja az első Gallai-azonosság : , sőt, a legnagyobb független csúcshalmaz komplementere a legkisebb csúcsfedő. Ezt a tényt felhasználva egy bipartit gráfban megtalálható polinomiális időben, mivel a benne lévő legkisebb csúcsfedő problémája a legnagyobb illesztés megtalálására redukálódik . $G=(V,E)$ $\alpha (G)$ $\tau (G)$ $\alpha (G)+\tau (G)=|V|$ $G$ $\alpha (G)$

Izolált csúcsok nélküli gráfban (0 fokú csúcsok) az egyenlőtlenség is fennáll , ahol a gráf éllefedettségének száma . Izolált csúcsok nélküli bipartit gráfban a König-tétel miatt , . $G$ $\alpha (G)\leq \rho (G)$ $\rho (G)$ $G$ $G$ $\alpha (G)=\rho (G)$

Linkek

Lovász László, Michael D. Plummer. Párosítási elmélet. - Észak-Hollandia, 1986. - ISBN 0-444-87916-1 .