Neorientovaný graf

• Uspořádaná dvojice

• - konečná množina vrcholů

• - konečná množina hran

• Hrana - podmnožina 2 vrcholů

• Množina všech možných hran -

• Sled - sekvence vrcholů a hran v grafu

• Cesta

  • Sled, ve kterém se neopakují vrcholy (ani hrany)
  • Pro koncové vrcholy mluvíme o s-t-cestě (připouštíme , tedy může mít i 0 délku)
  • Délka je počet hran v této cestě
• Nechť je hrana v grafu

  • jsou koncové vrcholy hrany
  • je sousedem a naopak
  • je incidentní s hranou ( je také incidentní s hranou )

Orientovaný graf

• Uspořádaná dvojice

• = konečná množina vrcholů

• = konečná množina orientovaných hran

• Orientovaná hrana - podmnožina 2 vrcholů , kde je předchůdce a je následník

• Zdroj - vrchol orientovaného grafu, do kterého nevede žádná hrana

Stupeň vrcholu - počet hran obsahující vrchol (tedy počet sousedů vrcholu)

Regulární graf - všechny vrcholy mají stejný stupeň (případně "-regulární", když všechny vrcholy mají stupeň )

Speciální případy grafů

• Úplný graf - hrana každý s každým, tj.
• Úplný bipartitní graf - dvě části (levá, pravá), každý vrchol vlevo má hranu ke každému vpravo, tedy počet hran
• Cesta - vrcholy propojené jeden za druhým
• Kružnice - vrcholy propojené do kruhu (taková cyklická cesta)
• Doplněk grafu - úplný graf se všemi hranami kromě hran grafu
• Podgraf - množiny vrcholů a hran jsou podmnožinami vrcholů a hran jiného grafu
• Indukovaný podgraf - podgraf, jehož množina hran je maximální možná

Izomorfismus grafů - grafy jsou izomorfní, pokud mají hranami spojené stejné vrcholy (i když jinak pojmenované) - takové jakoby popřeházení rozložení

Automorfismus grafů - izomorfismus se sebou samým, permutace vrcholů, množství automorfismů ukazuje míru pravidelnosti (symetrie) grafu