![Logo Matematická biologie](images/logo-matbiol.png)
Základní pojmy
Pro úspěšnou manipulaci s grafy je vhodné je definovat. Definice je velmi jednoduchá, protože graf obsahuje pouze uzly a hrany. Grafem tedy nazýváme dvojici množin
a
kde množina V označuje množinu uzlů grafu a
množinu hran grafu. Formálně
Někdy se ještě k této dvojici přidává třetí množina, tzv. incidenční funkce
která definuje počáteční a koncové uzly pro každou hranu. Potom můžeme graf zapsat jako trojici
Pro grafickou reprezentaci grafů budeme používat následující notaci:
- vrcholy (uzly) grafu znázorňujeme kroužkem nebo tečkou,
- hrany grafu jsou zobrazeny úsečkou, směr hrany je pak vyjádřen orientací, tedy šipkou z počátečního uzlu do uzlu koncového.
O uzlech spojených hranou, říkáme, že spolu sousedí, jsou to tedy sousední uzly. Ve vztahu uzel - hrana se používá pojem incidence.
Úloha: Zadefinujte graf z náledujícího obrázku.
Řešení
Definice: Je-li pak hrana
je označována jako smyčka.
![](/res/image/teoreticke_zaklady_informatiky/obr-tzi-2.png)