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 S \subseteq V je nezávislá množina, pokud platí \forall x, y \; \in S: (x, y) \notin E.

Nezávislost grafu

Nezávislost grafu G (značíme \alpha(G) )je největší počet prvků nezávislé množiny grafu G.

Maximální nezávislá množina

Častou úlohou v teorii grafů je hledání maximální nezávislé množiny daného grafu. Ukazuje se ovšem, že je to NP-úplný problém. +more Důkaz se provádí polynomiálním převodem instance problému maximální kliky v grafu na instanci problému NM (hledání nezávislé množiny velikosti k odpovídá hledání kliky velikosti k v doplňkovém grafu). Pokud by bylo možné řešit tento problém deterministicky v polynomiálním čase, bylo by tak možné řešit i problém kliky, o kterém je dokázáno, že je NP-úplný.

Reference

Externí odkazy

Kategorie:Grafové pojmy Kategorie:NP-úplné problémy