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í.
Řešení
Po zakreslení implikací bude graf vypadat následovně:
Jedno z možných řešení vzniklých barvením vrcholů:
Malíř tedy může použít například barvy A, E a G.