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: 3536
- 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
#4 09. 11. 2021 16:47
- check_drummer
- Příspěvky: 3536
- 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