Független ponthalmazok

Először három szorosan kapcsolódó fogalmat ismertetünk.

Definíció: Egy F csúcshalmazt független csúcshalmaznak nevezünk, ha F csúcsai nem köti össze él.

Definíció: Egy K csúcshalmazt klikknek nevezünk, ha K bármély két különböző csúcsát él köti össze.

Definíció: Egy L csúcshalmazt lefogó ponthalmaznak nevezünk, ha bármely él esetén legalább az egyik végpont L-beli.

A három fogalom közötti kapcsolatot a következőkben összefoglaljuk. Ehhez megjegyezzük, hogy G- a G egyszerű gráf komplementere, amely a V(G) csúcshalmazon akkor és csak akkor tartalmaz egy élt, ha az nem volt él G-ben. Formálisan V(G-)=V(G), E(G-)=E(G)-=(V2)-E(G).

Lemma: Legyen G egy egyszerű gráf.
(i) F akkor és csak akkor független ponthalmaza G-nak, ha F klikkje G--nek.
(ii) K akkor és csak akkor klikkja G-nek, ha K független ponthalmaz G--ben.
(iii) L akkor és csak akkor lefogó ponthalmaz, ha L-=V(G)-L független ponthalmaz.

A három fogalomhoz egy-egy optimalizálási probléma is tartozik.

Definíció: alfa(G)=\max{|F|:F független ponthalmaz}

Definíció: omega(G)=max{|K|:K klikk G-ben}

Definíció: tau(G)=min{|L|:L lefogó ponthalmaz G-ben}

A fogalmak közötti kapcsolat a gráfparaméterek kapcsolatára vezet.

Lemma:
(i) alfa(G)=omega(G-)=|V(G)|-tau(G),
(ii) omega(G)=alfa(G-)=|V(G)|-tau(G-),
(iii) tau(G)=|V(G)|-alfa(G)=|V(G)|-omega(G-).

Mindegyik paraméter mögött egy algoritmikus problémá rejlik.

Független ponthalmaz probléma: Adott G gráf, keressünk meg egy maximális elemszámú független ponthalmazát.

Sokkal könnyebb az alábbi relaxált kérdésen gondolkozni: Adott G gráf, keressünk minál nagyobb elemszámú független ponthalmazt.