Diskuse:Nezávislá množina

Je třeba rozlišovat maximální a největší nezávislou množinu! Maximální = už do ní více prvků nepřidám, ale největší = má nejvíce možných nezávislých prvků = ta "nejpočetnější maximální". Hledání maximální je P-problém (stačí jednoduchý greedy algoritmus) oproti nalezení největší, která je skutečně NP-těžká (nelze polynomiálně správnost ani verifikovat), jak je uvedeno.

Bydga 78.108.109.105 9. 1. 2013, 22:24 (UTC)

Teď teprv koukám, že tam je navíc uvedeno, že to je NP úplný problém - to je taky blbě..