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


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#2 08. 11. 2021 20:28

MichalAld
Moderátor
Příspěvky: 4196
Reputace:   111 
 

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: 2375
Reputace:   187 
 

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


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson