Bordák száma

Egy gráf élfedésének száma a benne lévő legkisebb élfedő mérete . $G$

Ha a gráfnak vannak izolált csúcsai (vagyis 0 fokú csúcsok), akkor nincs élfedés, ezért az élfedések száma nincs meghatározva. $G$

Egy tetszőleges, izolált csúcsok nélküli gráfban az éllefedettség számát az Edmonds-algoritmus segítségével találhatjuk meg az időben történő illesztéshez , majd hozzáadjuk azokat a csúcsokat fedő éleket, amelyek nem telítettek a legnagyobb illesztéssel. $O(|E||V|^{2})$

Izolált csúcsok nélküli gráfban az élfedő számot a második Gallai-azonossággal : , az egyező számhoz viszonyítja , ami viszont az egyenlőtlenséget jelenti . Ha van tökéletes egyezés a grafikonon, akkor . $G=(V,E)$ $\rho (G)$ $\nu (G)$ $\nu (G)+\rho (G)=|V|$ $\rho (G)\geq \nu (G)$ $\rho (G)=\nu (G)=|V|/2$

Egy izolált csúcsok nélküli gráfra is igaz az egyenlőtlenség , ahol a gráf függetlenségi száma . Kétrészes gráfban a Koenig - tétel miatt . $\rho (G)\geq \alpha (G)$ $\alpha (G)$ $G$ $G$ $\rho (G)=\alpha (G)$

Linkek

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