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.