Teorie grafů

Diplomová práce, MFF UK
Lukáš Jirovský
Matematika - MIUZV


4. Procvičování / Malíř a míchání barev

Teorie

Úloha [15]

Malíř má sedm kelímků a tub s barvami, chce namíchat odstín barvy, který se nevyrábí.
Přál by si, aby "jeho barva" obsahovala aspoň jednu z barev D, E, nejvýše jednu z barev A, B a aby obsahovala barvu C právě tehdy, když bude obsahovat barvu B. Použije-li barvy C, musí použít barvu F, použije-li D, nesmí použít A. Nepoužije-li barvu B, musí použít barvu G, barvu F však nesmí míchat s G.
Nalezněte alespoň jednu možnost namíchání barev.

Nápověda

Zakreslete všechny implikace v zadání pomocí grafu s orientovanými hranami. Potom použijte barvení vrcholů - více informací.

Nápověda: jak budou vypadat vrcholy v grafu

Řešení

Po zakreslení implikací bude graf vypadat následovně:

Řešení: Implikace zakreslené orientovanými hranami

Jedno z možných řešení vzniklých barvením vrcholů:

Jedno z možných řešení

Malíř tedy může použít například barvy A, E a G.


Úvod

Základní pojmy

Vybrané problémy

Procvičování