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
Ahoj,
napadlo mě, zda by níže uvedený algoritmus nemohl vést k požadovanému obarvení:
Označme množinu vrcholů obarvovaného grafu jako M.
Volme jako M1 maximální nezávislou množinu vrcholů, ze zbylých vrcholů volme další maximální nezávislou množinu (M2), atd. až získáme množiny M3,M4.
Pokud lze Mi volit více způsoby, postupujme tak, aby čtveřicie (|M1|,|M2|,|M3|,|M4|) byla v lexikografickém uspořádání maximální.
Nakonec obarvěme všechny vrcholy z každé Mi stejnou barvou.
Otázka tedy zní, zda tímto způsobem vždy dospějeme k cíli, tj. zda po vybrání množiny M4 již žádné další vrcholy v M nezbydou.
Offline
↑ MichalAld:
Já si naopak myslím, že ta moje hypotéza není správná. Ale bylo by zajímavé najít nějaký protipříkald.
Offline
Jestli dobře chápu zadání, tak protipříkladem by mohl být graf G, který vznikne ze čtyř kopií [mathjax]K_4[/mathjax], kde první a druhá kopie sdílí hranu, první a třetí kopie sdílí jinou hranu a první a čtvrtá kopie sdílí třetí hranu.
Tento graf je rovinný a jde jej obarvit čtyřmi barvami, přičemž barvou 1 obarvím 4 vrcholy a barvami 2, 3 a 4 jen dva vrcholy.
Avšak uvedený postup by preferovat obarvit 4 nezávislé vrcholy (až na izomorfismus jediná možnost které), potom 3 nezávislé vrcholy (jediná možnost) a pak zůstanou tři navzájem sousední vrcholy - budu potřebovat pět barev.
Offline
↑ petrkovar:
Aby to bylo jednoznačné, je potřeba přesněji říci jak budou vypadat ty sdílené hrany - zejména, které z nich budou/mohou mít společný vrchol.
Offline
↑ check_drummer:Aha, to jsem mohl trefit napoprvé správně;). Nakreslil jsem si jednu [mathjax]K_4[/mathjax] planárně a každá hrana vnější oblasti byla sdílená s další [mathjax]K_4[/mathjax]. Ty tři sdílené hrany první [mathjax]K_4[/mathjax] tvoří trojúhelník.
Offline
↑ petrkovar:
Ano, přesně tak. Tak nějak jsem předem tušil, že nebude fungovat, ale protipříklad jsem hned neviděl.
Offline
↑ petrkovar:
Já tam ale vidím u té první množiny M1 jen 3 nezávislé vrycholy a ne 4...
Offline
↑ check_drummer:Pro jistotu: graf má 10 vrchoů, Mám-li každou [mathjax]K_4[/mathjax] nakreslenou jako trojúhelník s vrcholem uprostřed, tak třeba ty čtyři prostřední vrcholy jsou nezávislé.
Offline
↑ petrkovar:
Aha, já měl [mathjax]K_4[/mathjax] jako čtverec. :-) Ale je pravda, že pak se hůř znázorňuje ta rovinnost.
Offline