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

Rozšířené hledání ›

Nejnovější témata ve fóru

22:06, Startupy Megastroj.cz – Vše na jednom místě: půjčovna, bazar a inze…

21:17, Inzerce FPGA vývojová deska XILINX VIRTEX 5 ML507

20:59, OS - GNU / Linux Ubuntu a OpenSuse

21:47, Offtopic Digitalizace v Česku

10:10, Cinema 4D Export USDC do DaVinci Resolve

16:58, Photoshop Jak odstranit (potlačit) odlesky

Stavba Laser Arény
Laser Game Brno

Zjištění chromatického čísla

Honza

~ Anonymní uživatel
~ 451 příspěvků

8. 5. 2012 #1

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

Nahlásit jako SPAM

IP: 2001:718:2:80e:60c4:199:d...–

Buco0

Newbie

8. 5. 2012 #2

Ako budes nacitavat dany graf? Matica alebo mnozinovy opis?

Nahlásit jako SPAM

IP: 178.40.25.–

Honza

~ Anonymní uživatel
~ 451 příspěvků

8. 5. 2012 #3

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é?

Nahlásit jako SPAM

IP: 2001:718:2:80e:b924:3d1e:...–

Buco0

Newbie

8. 5. 2012 #4

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.

Nahlásit jako SPAM

IP: 178.40.25.–

← Zpět na seznam vláken ← Zpět do Fóra