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 06. 11. 2021 16:55
- check_drummer
- Příspěvky: 3862
- Reputace: 91
Problém čtyř barev
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.
Ve 21. století i vzdělaní lidé učili své děti, že látka je tvořená z atomů.
Offline
#4 09. 11. 2021 16:47
- check_drummer
- Příspěvky: 3862
- Reputace: 91
Re: Problém čtyř barev
↑ 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.
Ve 21. století i vzdělaní lidé učili své děti, že látka je tvořená z atomů.
Offline
#5 03. 12. 2022 14:49 — Editoval petrkovar (03. 12. 2022 15:13)
Re: Problém čtyř barev
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
#6 03. 12. 2022 15:24
- check_drummer
- Příspěvky: 3862
- Reputace: 91
Re: Problém čtyř barev
↑ 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.
Ve 21. století i vzdělaní lidé učili své děti, že látka je tvořená z atomů.
Offline
#7 03. 12. 2022 15:34 — Editoval petrkovar (03. 12. 2022 15:36)
Re: Problém čtyř barev
↑ 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
#9 03. 12. 2022 17:47
- check_drummer
- Příspěvky: 3862
- Reputace: 91
Re: Problém čtyř barev
↑ petrkovar:
Ano, přesně tak. Tak nějak jsem předem tušil, že nebude fungovat, ale protipříklad jsem hned neviděl.
Ve 21. století i vzdělaní lidé učili své děti, že látka je tvořená z atomů.
Offline
#10 03. 12. 2022 17:50
- check_drummer
- Příspěvky: 3862
- Reputace: 91
Re: Problém čtyř barev
↑ petrkovar:
Já tam ale vidím u té první množiny M1 jen 3 nezávislé vrycholy a ne 4...
Ve 21. století i vzdělaní lidé učili své děti, že látka je tvořená z atomů.
Offline
#11 03. 12. 2022 18:13
Re: Problém čtyř barev
↑ 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
#12 03. 12. 2022 19:10 — Editoval check_drummer (03. 12. 2022 19:14)
- check_drummer
- Příspěvky: 3862
- Reputace: 91
Re: Problém čtyř barev
↑ petrkovar:
Aha, já měl [mathjax]K_4[/mathjax] jako čtverec. :-) Ale je pravda, že pak se hůř znázorňuje ta rovinnost.
Ve 21. století i vzdělaní lidé učili své děti, že látka je tvořená z atomů.
Offline