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.