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.[1][2]

Definice

Nechť G = (V, E) je graf, pak je nezávislá množina, pokud platí .

Nezávislost grafu

Nezávislost grafu G (značíme )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.[2] 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

  1. Algoritmy.net [online]. INFO WEB [cit. 2016-10-27]. Kapitola Nezávislé množiny → Vrcholové pokrytí. Dostupné online. 
  2. a b Grafy a grafové algoritmy (3): Nezávislost, klikovost, dominance a barevnost grafu [online]. Praha: ČVUT [cit. 2016-11-01]. Dostupné v archivu pořízeném dne 2016-11-03. 

Externí odkazy

Média použitá na této stránce

Independent set graph.svg
Autor: Life of Riley, Licence: GFDL
Independent set graph illustration used in the article w:en:Independent set (graph theory) in the English Wikipedia and other Wikipedias. This image is based upon, and is an SVG replacement for File:Independent set graph.gif by User:Rocchini.