Některé základní pojmy
Základní pojmy teorie grafů jsou srozumitelné.
Sled v grafu
Je posloupnost vrcholů a hran
v0 e1 v1 e2 ... en vn
kde hrana
ei má koncové vrcholy
vi a
vi
Tah v grafu
Je sled, ve kterém se neopakují hrany.
Cesta v grafu
Je sled, ve kterém se neopakují vrcholy.
Souvislý graf
Ve kterém mezi každými dvěma vrcholy existuje sled (cesta).
Podgraf
Graf
H se nazývá podgraf grafu
G, jestliže
VH je podmnožinou
VG a
EH je podmnožinou
EG.
Cyklus
Cyklus je graf, ve kterém jsou všechny vrcholy stupně 2 (pravidelný podgraf stupně 2).
Komponenta grafu
Komponenta grafu je jeho maximální souvislý podgraf.
Ohodnocení
Je zobrazení množiny hran do množiny reálných čísel (každé hraně přiřadíme reálné číslo).
Algoritmus
Posloupnost operací, která pro přesně definovaná vstupní data vede po konečném počtu kroků k odpovídajícím výsledkům.
