Graf
Definice
Graf
G je uspořádaná dvojice
(V,E), kde
V je neprázdná množina vrcholů a
E je množina dvouprvkových podmnožin množiny
V, zvaných hrany.
Obvykle píšeme
G = (VG, EG).
Vrcholy
u a
v nazýváme
koncovými vrcholy hrany
e={u,v} (psáno
ij nebo
i-j), nebo také
incidentní s hranou
e.
Vrcholy
u a
v nazýváme
sousední, jestliže v
EG existuje hrana
e={u,v}.
Hrany se nazývají
incidentní, jestliže mají společný koncový vrchol.
Stupeň vrcholu je počet hran s ním incidentních.
Nakreslení grafu
| Grafy znázorňujeme jako diagramy v rovině, kde vrcholy jsou kroužky a hrany jsou křivky spojující dvojice vrcholů. |
 |
Rozšíření pojmu graf
- hrany mohou být orientované - digraf
- hrany mohou být vícenásobné - multigraf
- hrana může vest z vrcholu do stejného vrcholu - smyčka
