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.