Cvičení 6 se 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ě.

Obecná náplň cvičení

Vysvětlení orientovaných grafů a jejich využití pro "síťové" problémy.

• Orientované grafy - čím se liší od obyčejných,kdy třeba 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.

• Ú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). Tot 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.