Motivace

Grafy jsou jedním ze základních pojmů informatiky a zároveň se jedná o velmi užitečnou a praktickou pomůcku k řešení nejrůznějších druhů problémů. Graf je možné si představit jako zjednodušení reálného světa, kdy daný problém znázorníme pomocí bodů a čar, které je spojují.  Tyto body se nazývají uzly (vrcholy) grafu a spojnice mezi nimi se nazývají hrany grafu.

Graf může reprezentovat nějaký problém, síť, uspořádání prvků, algoritmus a podobně. Grafy mají využití nejen v informatice a matematice, ale také např. ve fyzice, v chemii, v elektrotechnice, v ekonomii nebo v sociologii. Grafy můžeme využít k hledání nejkratší cesty mezi dvěma místy, k řešení úloh umělé inteligence při hraní šachů, k optimalizaci elektrizační soustavy a k řešení mnohých dalších úloh.

Hrana má vždy počátek a konec v nějakém uzlu. Většinou jsou počáteční a koncové uzly různé, pokud ale nejsou, hovoříme o tzv. smyčce. Teoreticky může vést mezi dvěma uzly i více hran – v tom případě hovoříme o multigrafu.