Matematické Fórum

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.

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

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

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

↑ petrkovar:
Já tam ale vidím u té první množiny M1 jen 3 nezávislé vrycholy a ne 4...

↑ petrkovar:
Aha, já měl [mathjax]K_4[/mathjax] jako čtverec. :-) Ale je pravda, že pak se hůř znázorňuje ta rovinnost.

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

↑ 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ů).