Teorie grafů

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


4. Procvičování / Přelévání mléka

Úloha [15]

Mlékařka má osm litrů mléka ve dvou nádobách, pětilitrové a třílitrové, zapomněla si však dnes litrovou odměrku.
Přichází zákaznice s dvoulitrovou nádobou, ale žádá jen litr mléka.
Může mlékařka najít postup, jak odměřit do dvoulitrové nádoby jeden litr mléka, smí-li použít jen přelévání mezi těmito třemi nádobami?

Pokud ano, popište postup.
Pokud ne, zdůvodněte, proč ne.

Příklad nádob

Nápověda

Použijte podobný princip jako v úloze o převozníkovi - zakreslete si všechna možná množství mléka v nádobách (na každém vrcholu tedy bude údaj ve tvaru (x,y,z) - x litrů mléka v pětilitrové nádobě, y litrů v třílitrové a z litrů v dvoulitrové). V tomto grafu pak budeme hledat vhodnou cestu.

Řešení

Všechny možnosti rozlití mléka si zakreslíme jako vrcholy grafu. Na každém vrcholu budou vždy tři čísla - počet mléka v první nádobě, druhé a třetí (zvolíme si například pořadí "pětilitrová, třílitrová, dvoulitrová").

Jeden vrchol znázorňující množství mléka v nádobách

Pokud se z jednoho vrcholu dokážeme dostat do druhého, zakreslíme mezi vrcholy hranu.

Rozepíšeme si tedy všechny možné stavy - v součtu dávají 8 litrů (množství mléka, které má mlékařka k dispozici) a v každé nádobě je maximálně tolik mléka, kolik se tam vejde (vrchol (6,1,1) nepadá v úvahu, protože první nádoba má kapacitu 5 litrů).

Všechny stavy:
(5,3,0), (5,2,1), (5,1,2), (4,3,1), (4,2,2), (3,3,2)

Proč budou hrany grafu orientované?
Například ze stavu (4,2,2) se dokážeme dostat do (3,3,2) (z první nádoby budeme lít do druhé třílitrové). Zpět to však nejde, protože cestou zpět nedokážeme odměřit litr.

Orientovaná hrana znázorňující možnost přelití mléka

Jak vypadají v grafu všechny možnosti přelití mléka?
Kompletní graf dané úlohy

Co je pro nás hledaný výsledek?
Začínáme ve vrcholu (5,3,0) a hledáme cestu do vrcholů, které mají na posledním místě 1 (1 litr mléka má být nádobě, kterou si přinesla zákaznice), tedy (4,3,1) a (5,2,1).

Žádnou takovou cestu nenajdeme - tím jsme ukázali, že úloha nemá řešení.


Úvod

Základní pojmy

Vybrané problémy

Procvičování