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

 

#2 08. 11. 2021 20:28

MichalAld
Moderátor
Příspěvky: 4405
Reputace:   117 
 

Re: Problém čtyř barev

Se obávám, že vzhledem k tomu, že důkaz obarvitelnosti rovinného grafu 4 barvami nelze provést bez počítače, že nepůjde (bez počítače) dokázat ani tohle.

Offline

 

#3 08. 11. 2021 20:41

Bati
Příspěvky: 2389
Reputace:   188 
 

Re: Problém čtyř barev

MichalAld napsal(a):

... důkaz obarvitelnosti rovinného grafu 4 barvami nelze provést bez počítače...

zkus to dokazat

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)

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1007
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

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)

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1007
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

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

 

#8 03. 12. 2022 15:47

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1007
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Problém čtyř barev

Myslím, že popsaný algoritmnus je vlastně hladový (greedy), že?

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

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1007
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

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

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson