Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 20. 05. 2012 02:15
Důkaz - 3-COL je NP-úplný problém
Ahoj,
snažím se nastudovat důkaz, že 3-COL (3-obarvení) je NP-úplný problém. Používám tento zdroj www.cam.zcu.cz/~ryjacek/students/ps/TGD1.pdf, přesněji strana 71-72.
Není mi přesně jasný výrok na straně 72, kdy se říká:
"Především: G je obarvitelný 
G je 3-obarvitelný tak, že uzel 
má barvu 0, uzel 
barvu 1 a uzel 
barvu 2..."
Nechápu hlavně tu ekvivalenci "G je obarvitelný G je 3-obarvitelný tak..."
Mohl by mi prosím někdo osvětlit, jestli to třeba není nějaká chyba? Mně to totiž moc smysl nedává. Každý graf je přece obarvitelný, kdy se použije dostatek barev.
Děkuji za odpověď
Offline