OBSAH

V této lekci se začneme zabývat další důležitou oblastí diskrétní matematiky - teorií grafů, kterou najdeme v mnoha oblastech informatiky. Úvodem si zavedeme pojem grafu a další základní pojmy jako podgrafy a isomorfismus, souvislost a komponenty. Rozsah pokrytí látky grafů v předmětu IB000 je sice omezený, ale dostatečný z hlediska deklarovaného profilu absolventa bakalářského studia (a více se naučíte také v kurzech algoritmizace). Více se o teorii grafů dozvíte v pokračujícím studiu, třeba v předmětu MA010.

Samostatné procvičení učiva - odpovědníky

Podívejte se pozorně na přiložené odpovědníky a sami si zkuste, nakolik látce rozumíte do detailu i do hloubky. Máte na výběr od velice snadných příkladů po (trochu) obtížnější testování isomorfismu a podgrafů. Hlavní poselství k těmto příkladům zní: Naučte se grafy správně "hezky" nakreslit, abyste jim lépe porozuměli a mnohem snadněji tak uměli příklady vyřešit. V příkladech si přímo můžete přesouvat vrcholy myší, abyste daný obrázek vylepšili. Skutečně, dobrý obrázek je základ, který i z (na první pohled) obtížného příkladu dokáže udělat trivialitu (a pokud ne, hledejte ještě lepší obrázek...).

Pokročilý odpovědník v této lekci sice zase zkouší tutéž látku isomorfismu, podgrafů a komponent, ale táže se na grafech, kde už hledání řešení není jen o rutinním "podívám se na hezký obrázek a vidím", nýbrž vyžaduje zapojení systematické práce s grafem a uvažování o možnostech. Zkuste si, jestli i takto obtížnou úroveň příkladů o grafech zvládáte. (A pokud pořád zvládáte, těšte se na ještě zajímavější příklady v příští lekci.)

Diskuse o látce

Jedná se o novější látku v IB000 a zajímavé diskuse k ní sebrány nebyly a asi ani nebudou...

Doplňkové a externí materiály

Pro širší studium grafů v prvé řadě doporučujeme materiály kurzu MA010 na FI MU. Doplňkově uvádíme další odkazy a především doporučujeme skvělou učebnici Kapitoly z diskrétní matematiky.