Nezávislá množina

Modře označené vrcholy tvoří maximální nezávislou množinu vyobrazeného grafu.

Nezávislá množina (NM) je pojem z teorie grafů. Nezávislá množina v grafu je taková množina jeho vrcholů, že žádné dva z nich nejsou spojeny hranou.

Definice

Nechť $G=(V,E)$ je graf, pak $N\subseteq V$ je nezávislá množina, pokud platí $\forall x,y\;\in N:xy\notin E$. Velikost největší nezávislé množiny v grafu $G$ se značí $\alpha (G)$ a nazývá se číslo nezávislosti grafu.

Problém nezávislé množiny

Rozhodovací varianta

Rozhodovací varianta problému nezávislé množiny má následující tvar:

• Vstup: Neorientovaný graf $G$ a číslo $k\in \mathbb {N}$.
• Otázka: Platí $\alpha (G)\geqslant k$?

Tento problém náleží do třídy NP. Je-li totiž odpověď kladná, lze jako certifikát předložit konkrétní množinu vrcholů $A\subseteq V$ a v polynomiálním čase ověřit, že $|A|\geqslant k$ a že žádné dva vrcholy z $A$ nejsou spojeny hranou.

Dokonce lze ukázat, že (rozhodovací) problém nezávislé množiny je NP-úplný. Tuto skutečnost lze dokázat redukcí z problému 3-SAT, jelikož problém SAT (který je NP-úplný z Cookovy-Levinovy věty) je polynomiálně převoditelný na 3-SAT.

Důkaz NP-úplnosti

Mějme tedy formuli $\varphi$ v konjunktivní normální formě, jejíž každá klauzule obsahuje právě tři literály. Nechť má formule celkem $m$ klauzulí. Sestrojíme příslušný graf $G$ takto:

• Pro každou klauzuli vytvoříme trojúhelník (tj. cyklus $C_{3}$) a jeho tři vrcholy označíme třemi literály dané klauzule.
• Dále spojíme hranou každé dva vrcholy z různých trojúhelníků, pokud odpovídají literálům vzájemně opačné polarity, tedy jednomu literálu $\ell$ a druhému $\neg \ell$.

Korektnost převodu je založena na dvou jednoduchých pozorováních. Protože každý trojúhelník je úplný graf na třech vrcholech, může nezávislá množina obsahovat z každé klauzule nejvýše jeden vrchol. Existence nezávislé množiny velikosti $m$ tedy znamená, že jsme vybrali právě jeden vrchol z každé klauzule. Hrany mezi konfliktními literály navíc zaručují, že takový výběr nemůže obsahovat současně $x$ i $\neg x$. Vybrané vrcholy proto určují konzistentní pravdivostní ohodnocení proměnných, které v každé klauzuli splní alespoň jeden literál.

Naopak, existuje-li splňující ohodnocení formule $\varphi$, z každé klauzule vybereme jeden pravdivý literál. Tím dostaneme množinu $m$ vrcholů, z nichž žádné dva nejsou spojeny hranou: uvnitř jedné klauzule jsme vybrali právě jeden vrchol a mezi různými klauzulemi nemohou být spojeny dva současně pravdivé konfliktní literály. Tato množina je tedy nezávislá a má velikost $m$.

Tím jsme dokázali, že formule $\varphi$ je splnitelná právě tehdy, když v grafu $G$ existuje nezávislá množina velikosti alespoň $k$. Navíc převod je zjevně polynomiální, neboť graf $G$ může mít maximálně ${\textstyle {\binom {n}{2}}}$ hran.

Optimalizační varianta

Optimalizační verzí problému nezávislé nezávislé množiny má následující tvar:

• Vstup: Neorientovaný graf $G$.
• Výstup: Číslo $\alpha (G)$.

Optimalizační varianta problému je alespoň stejně „těžká“ jako varianta rozhodovací. Kdybychom uměli v polynomiálním čase spočítat hodnotu $\alpha (G)$, uměli bychom tím v polynomiálním čase vyřešit i rozhodovací variantu.

Vztahy s dalšími problémy

Klika

Problém nezávislé množiny je úzce spjat s problémem kliky. Množina vrcholů $I\subseteq V(G)$ je nezávislá v grafu $G$ právě tehdy, když je klikou v jeho doplňku ${\overline {G}}$. Z toho plyne, že graf $G$ obsahuje nezávislou množinu velikosti alespoň $k$ právě tehdy, když doplňkový graf ${\overline {G}}$ obsahuje kliku velikosti alespoň $k$.

Tento vztah ukazuje, že problémy klika a nezávislá množina jsou v podstatě dvěma pohledy na tutéž otázku: v jednom případě hledáme podmnožinu vrcholů s co nejvíce hranami, ve druhém naopak podmnožinu bez hran.

Vrcholové pokrytí

Další vztah má problém nezávislé množiny k vrcholovému pokrytí. Množina $I\subseteq V(G)$ je nezávislá právě tehdy, když doplněk $V(G)\setminus I$ tvoří vrcholové pokrytí grafu $G$, tedy množinu vrcholů obsahující alespoň jeden konec každé hrany.

V důsledku toho pro každý graf platí $\alpha (G)+\tau (G)=|V(G)|,$ kde $\tau (G)$ značí velikost nejmenšího vrcholového pokrytí. Rozhodovací problém „existuje vrcholové pokrytí velikosti nejvýše $k$?“ je proto na problém nezávislé množiny polynomiálně převoditelný.

Barvení grafu

Barvení grafu s problémem nezávislé množiny souvisí tím, že každá barevná třída v korektním obarvení tvoří nezávislou množinu. Naopak každé rozdělení množiny vrcholů $V$ na $k$ nezávislých množin určuje korektní obarvení $k$ barvami. Hledání obarvení grafu tedy lze chápat jako úlohu rozložit vrcholy grafu na co nejmenší počet nezávislých množin.

Tato souvislost je důležitá i z hlediska výpočetní složitosti. Například problém 3-obarvitelnosti je NP-úplný.

Párování

Problém párování stojí vůči nezávislé množině v poněkud odlišné pozici. Sám o sobě nepředstavuje další NP-úplný problém v této rodině; naopak největší párování v bipartitním grafu lze nalézt v polynomiálním čase převodem na problém maximálního toku.

Právě proto je vztah k párování důležitý u speciálních tříd grafů.

Nezávislé množiny u speciálních tříd grafů

Ačkoliv je problém nezávislé množiny pro obecné grafy NP-úplný, pro některé důležité třídy grafů je řešitelný v polynomiálním čase.

Stromy a lesy

U stromů a obecněji lesů lze největší nezávislou množinu nalézt v polynomiálním, ba při vhodné implementaci i v lineárním čase. Základním krokem je následující pomocné lemma.

Lemma: Buď $T$ les a $\ell$ jeho libovolný list. Pak alespoň jedna z největších nezávislých množin grafu $T$ obsahuje vrchol $\ell$.

Důkaz: Mějme největší nezávislou množinu $M$, která list $\ell$ neobsahuje. Označme $p$ souseda vrcholu $\ell$. Pokud $p\notin M$, pak lze vrchol $\ell$ do množiny $M$ přidat, čímž bychom dostali větší nezávislou množinu, což je spor s maximalitou velikosti $M$. Musí tedy platit $p\in M$. Pak však můžeme z množiny $M$ odebrat vrchol $p$ a nahradit jej vrcholem $\ell$. Tak dostaneme nezávislou množinu stejné velikosti, která již vrchol $\ell$ obsahuje. Tím je lemma dokázáno.

Z lemmatu plyne jednoduchý hladový algoritmus: opakovaně vybereme libovolný list, zařadíme jej do výsledné množiny a z grafu odstraníme jeho souseda; izolované vrcholy přidáme do výsledné množiny také. Takto lze sestrojit největší nezávislou množinu lesa.

Bipartitní grafy

V bipartitních grafech je problém nezávislé množiny řešitelný v polynomiálním čase.

Souvisí to s tím, že největší párování v bipartitním grafu lze nalézt pomocí maximálního toku, a problém nezávislé množiny je zde úzce propojen s problémem vrcholového pokrytí. Bipartitní grafy tak tvoří důležitý příklad třídy grafů, na níž je obecně těžký problém řešitelný efektivně.

Máme bipartitní graf $G=(A\cup B,E)$, kde $A$ a $B$ jsou partity. Sestrojíme síť tak, že:

• přidáme zdroj $s$ a stok $t$,
• z $s$ vedeme hranu do každého vrcholu z $A$,
• každou hranu původního grafu orientujeme z $A$ do $B$,
• z každého vrcholu z $B$ vedeme hranu do $t$,
• pro všechny hrany nastavíme kapacitu 1.

Hrany původního bipartitního grafu, po nichž teče 1, pak tvoří párování; naopak z každého párování lze sestrojit tok stejné hodnoty. Velikost maximálního toku je tedy rovna velikosti největšího párování.

U bipartitních grafů platí tzv. Kőnigova věta. Z ní plyne, že velikost největší nezávislé množiny v bipartitním grafu je

$\alpha (G)=|V(G)|-\tau (G)=|A|+|B|-\nu (G),$

kde $\nu (G)$ je velikost největšího párování a $\tau (G)$ velikost nejmenšího vrcholového pokrytí.

Intervalové grafy

Také pro intervalové grafy lze problém nezávislé množiny řešit v polynomiálním čase.

Je-li intervalová reprezentace grafu známa, odpovídá hledání nezávislé množiny výběru co největšího počtu navzájem se nepřekrývajících intervalů. Tato formulace je ekvivalentní klasické úloze rozvrhování, kterou lze řešit jednoduchým hladovým algoritmem.

Externí odkazy

• Obrázky, zvuky či videa k tématu nezávislá množina na Wikimedia Commons

Portály: Matematika