Teorie grafů

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


3. Vybrané problémy / Rozvrh

Úvod

Podobný princip, jaký jsme využili v úlohách s barvením mapy a o výrocích, lze úspěšně použít i při hledání optimálního rozvrhu.

Zadání [16]

Mějme 6 hodin (lekcí) označených h1h6, mezi kterými si mohou studenti vybírat. Všechny lekce trvají stejně dlouho.
Nalezněte takový rozvrh, ve kterém všechny lekce proběhnou v nejkratším čase a zároveň umožněte, aby se nepřekrývaly hodiny h1 a h2; h1 a h4; h3 a h5; h2 a h6; h4 a h5; h5 a h6; h1 a h6.

Řešení

Nejjednodušším řešením by bylo všechny hodiny seřadit za sebou - zajistili bychom tak, že každý, kdo si vybral hodinu h1, může jít i na hodinu h2 či jakoukoliv jinou (a tím bychom snadno splnili všechny podmínky ze zadání).
Úkolem je ale umožnit souběh hodin, u kterých nejsou studenti, kteří by měli zájem jít na obě hodiny současně.

Všechny hodiny zakreslíme jako vrcholy grafu. Hrany mezi nimi (které jsou neorientované) spojí vrcholy odpovídající hodinám, které nemají probíhat zároveň.
Zakreslujeme relaci "nemá probíhat zároveň" na množině hodin h1h6.

Hodiny s podmínkami zakreslené jako graf
Obr. č. 3.21 - Graf popisující požadavky na rozvrh

Jednotlivým vrcholům budeme přiřazovat čísla (již v úloze barvení mapy jsme si ukázali, že přiřazování barev odpovídá přiřazování čísel).
Tato čísla budou odpovídat pořadí hodin v rozvrhu (pokud dvě hodiny dostanou číslo 1, budou v rozvrhu probíhat zároveň).

Při číslování budeme používat podobnou podmínku jako u sousedních států při barvení mapy - pokud dvě hodiny nemají začínat ve stejnou chvíli, jejich čísla budou různá.

Postup přiřazení hodin

Krok animace (č. 1) Krok animace (č. 2) Krok animace (č. 3) Krok animace (č. 4) Krok animace (č. 5)

Animace

Závěr

Hledaný rozvrh hodin vyčteme z obarvení vrcholů grafu - vrcholy se stejnou barvou představují hodiny probíhající souběžně.

1.2.3.
h1 a h5 h2, h3, h4 h6

Minimální počet hodin, během kterých je možné odučit h1h6 za předepsaných podmínek, je 3.

Úloha na procvičení


Úvod

Základní pojmy

Vybrané problémy

Procvičování