Zjištění chromatického čísla – Java – Fórum – Programujte.com

Ahoj potřebuju co nejjednodušeji zjistit chromatiké číslo grafu, který načtu ze vstupu. nemáte někdo nějakou radu co na to použít? Mám vytvořený vlastní algoritmus a tohle potřebuju jenom pro kontrolu.Díky moc

Ako budes nacitavat dany graf? Matica alebo mnozinovy opis?

Vstup je reprezentovany seznamem hran. A nebo mě napadla druhá varianta nevíte jestli někde nejsou grafy kde by tyto výsledky byly už spočítané?

Mozno sa mylim, ale chromaticke cislo je vlastne pocet farieb potrebnych na regularne zafarbenie uzlov grafu - dva uzly spojene jednou hranou musia mat roznu farbu. Z toho mi vyplyva, ze chromaticke cislo +1 by bolo rovne maximalnemu stupnu deg(u) zo vsetkych uzlov. X(G) = deg(u) + 1  (Neviem ci je taketo zjednodusenie mozne, protoze podla definice chromaticke cislo zavisi od poctu disjunktnych podmnozin). Ak by si graf nacitaval ako maticu susednosti, kde sucet riadku predstavuje stupen daneho uzla, tak staci vybrat najvyssi, pripocitat 1 a to cislo by predstavovalo chromaticke cislo grafu. Uprava pre vstup zoznamu hran by nemal byt problem.