Nezávislá množina
Z Multimediaexpo.cz
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 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. 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ý.
| 200 sociálních sítí a dalších služeb ! |
|---|
|
 |
| Informace o článku.
Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. |