Cvičení 6 se z časových důvodů dělí na dva výrazně odlišné tematické celky. Zde v 6a se dokončí látka grafů s důrazem na orientované grafy, sítě. (Kdežto 6b bude zaměřeno na dokazování algoritmů, pokud již algoritmy byly načaty na přednášce.)

Rámcová náplň cvičení

Orientované grafy

• Orientované grafy - čím se liší od obyčejných grafů, kdy třeba v aplikacích potřebujeme orientaci hran, souvislost s relacemi, které nemusí být symetrické. Krátké shrnutí pojmů, které se na orientované grafy přímo přenášejí, jako podgrafy, isomorfismus, atd.
• Co je v orientovaných grafech odlišné, třeba orientované kružnice oproti neorientovaným (graf bez orientovaných kružnic stále může mít mnoho hran, na rozdíl od stromů!) nebo výrazná odlišnost orientovaných verzí souvislosti (dosažitelnost a silná souvislost).

Toky v sítích

• Úlohy využívající sítí a toků v nich, ukázky všelijakých "transportních úloh". Ukázky definovaných sítí a použití základního algoritmu vylepšování nenasycených cest pro nalezení toku, se zdůrazněním rovnosti velikosti toku s nalezeným minimálním řezem na konci.

• Volitelně lze probrat, jak algoritmus nenasycených cest implementovat pro rychlejší práci (tj. především hledat nejkratší nenasycené cesty do šířky - Edmonds-Karp, Dinitz). Toto však není nutné, neboť k tomu budou kurzy návrhu algoritmů.

• Lehce se uvedou v příkladech některé odvozené úlohy od toků - jako bipartitní párování nebo systémy různých reprezentantů. Studenti by měli vědět, že takové úlohy existují, a spojit si je s toky v síti.

Možné příklady k procvičení orientovaných grafů

• Zorientujte hrany úplných grafů na 6 a na 7 vrcholech tak, aby
  • nebyla ve výsledku obsažena orientovaná kružnice;
  • z každého vrcholu vycházela alespoň jedna šipka a přitom neexistovala orientovaná kružnice;
  • z každého vrcholu vycházela alespoň jedna šipka a přitom neexistovala orientovaná kružnice délky větší než 3;
  • výsledek měl právě 3 silně souvislé komponenty;
  • z každého vrcholu vycházely nejvýše 3 šipky.

Možné příklady k procvičení toků

xxx