Uafhængighedsnummer

Uafhængighedstallet for en graf er størrelsen af det største uafhængige sæt af hjørner i den. $G$

Da det uafhængige sæt-problem er NP-komplet , er der ingen kendte algoritmer til at bestemme uafhængighedstallet i en vilkårlig graf, der virker i polynomisk tid.

I enhver graf er uafhængighedstallet relateret til toppunktets dækningsnummer ved den første Gallai-identitet : desuden er komplementet af det største uafhængige toppunktsæt det mindste toppunktsdæksel. Ved at bruge denne kendsgerning kan en todelt graf findes i polynomisk tid, da problemet med det mindste toppunktsdæksel i den er reduceret til at finde den største matchning . $G=(V,E)$ $\alpha (G)$ $\tau (G)$ $\alpha (G)+\tau (G)=|V|$ $G$ $\alpha (G)$

I en graf uden isolerede hjørner (hjørnepunkter af grad 0) gælder uligheden også , hvor er antallet af kantdækninger af grafen . I en todelt graf uden isolerede hjørner, på grund af Königs sætning , . $G$ $\alpha (G)\leq \rho (G)$ $\rho (G)$ $G$ $G$ $\alpha (G)=\rho (G)$

Uafhængighedsnummer

Links