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ň )