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: 4781
Reputace:   105 
 

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.


"Máte úhel beta." "No to nemám."

Offline

 

#2 08. 11. 2021 20:28

MichalAld
Moderátor
Příspěvky: 4980
Reputace:   125 
 

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: 2437
Reputace:   191 
 

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: 4781
Reputace:   105 
 

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.


"Máte úhel beta." "No to nemám."

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: 1012
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: 4781
Reputace:   105 
 

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.


"Máte úhel beta." "No to nemám."

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: 1012
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: 1012
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: 4781
Reputace:   105 
 

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.


"Máte úhel beta." "No to nemám."

Offline

 

#10 03. 12. 2022 17:50

check_drummer
Příspěvky: 4781
Reputace:   105 
 

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...


"Máte úhel beta." "No to nemám."

Offline

 

#11 03. 12. 2022 18:13

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1012
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: 4781
Reputace:   105 
 

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.


"Máte úhel beta." "No to nemám."

Offline

 

#13 26. 02. 2023 15:18

MichalAld
Moderátor
Příspěvky: 4980
Reputace:   125 
 

Re: Problém čtyř barev

Nemáte mmch někdo představu, jak ten důkaz, že lze rovinný graf obarvit 4 barvami vlastně vypadá? Vím, že se to řeší počítačem, ale na čem to vlastně stojí?

To je třeba nějaká rekurzivní (v principu jednoduchá) funkce a nechá se běžet a čeká se, jestli to skončí (což znamená důkaz proveden) nebo neskončí?

Offline

 

#14 26. 02. 2023 15:48

check_drummer
Příspěvky: 4781
Reputace:   105 
 

Re: Problém čtyř barev

MichalAld napsal(a):

Nemáte mmch někdo představu, jak ten důkaz, že lze rovinný graf obarvit 4 barvami vlastně vypadá? Vím, že se to řeší počítačem, ale na čem to vlastně stojí?

To je třeba nějaká rekurzivní (v principu jednoduchá) funkce a nechá se běžet a čeká se, jestli to skončí (což znamená důkaz proveden) nebo neskončí?

Myslím, že se tam vyšetřují různé typy grafů, které se mohou vyskytnout a pro ty se to obarvení hledá. A těch grafů je dost.

Jinak ta funkce podle mě skončí vždy - buď to obarvení najde nebo nenajde (vyzkoušením všech možností). Ale ono je to jedno - víme-li, že ten program skončil a řešení našel (což se tedy stalo), tak už nás vlastně nemusí zajímat co by se stalo, kdyby ho nenašel - zda poběží nekonečně dlouho a nebo zda napíše po nějaké době "nenalezeno".


"Máte úhel beta." "No to nemám."

Offline

 

#15 26. 02. 2023 16:49

MichalAld
Moderátor
Příspěvky: 4980
Reputace:   125 
 

Re: Problém čtyř barev

Já jsem právě myslel ty typy grafů. Že se jako neví, jestli je jich konečný nebo nekonečný počet ...

Offline

 

#16 26. 02. 2023 18:49

check_drummer
Příspěvky: 4781
Reputace:   105 
 

Re: Problém čtyř barev

↑ MichalAld:

Přesně detail toho důkazu neznám, ale kdyby jich byl nekonečný počet, tak by to počítatč v konečném čase nezvládl ověřit - pokud tedy v konečném čase zvládne prověřit jen konečně mnoho grafů (a ne třeba skupinu nekonečných podobných grafů).


"Máte úhel beta." "No to nemám."

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson