Vrcholy a hrany
Graf tvoří 2 části, množina vrcholů , , , které jsou propojeny hranami . Množinu všech vrcholů označujeme V a množinu všech hran E.
Formální definice
- V je neprázdná konečná množina vrcholů (nebo také uzlů),
- E množina hran grafu. Může být prázdná.
V základu rozlišujeme dva základní druhy grafů. Orientované grafy představují obecnější prostředek než grafy neorientované. Neorientovaný graf totiž snadno nahradíme takovýme takovým orientovaným grafem sestejnou množinou vrcholů, v němž místo jedné neorientované hrany mezi vrcholy $x$, $y$ vedou dvě orientované, jedna z vrcholu $x$ do vrcholu $y$ a druhá naopak z vrcholu $y$ do vrcholy $x$.
Orientovaný graf
E obsahuje orientované hrany.Hrana je
(u, v) ∈ E je uspořádaná dvojice.
Platí tedy E ⊆ V × V
Neorientovaný graf
E obsahuje neorientované hrany.Hrana je dvouprvková podmnožina
{u, v} ∈ E.
Platí tedy E ⊆ $\binom{V}{2}$
Vlastnosti
Počet hran orientovaného grafu: |E| = Variace bez opakování V(2, V).
Počet hran neorientovaného grafu: |E| = Kombinace bez opakování $\binom{V}{2}$.
Speciální typy grafů
Prostý graf (Simple graph)
Graf v němž je násobnost každé hrany nejvýše jedna. Nebo jinak řečeno, neobsahuje smyčky a násobné hrany.
- Úplný graf obsahuje všechny hrany. Tzn. každá hrana je spojená s každým vrcholem.
Multigraf
Multigraf je graf, v němž násobnost hran mohou být i větší. Symetrizací prostého orientovaného grafu může vzniknout multigraf.
Acyklický graf
Orientovaný graf neobsahující žádný cyklus.
Diskrétní grafy
Neobsahují žádné hrany.
Ohodnocené grafy
V ohodnoceném grafu je každé hraně přiřazeno ohodnocení, což je běžně číslo, např. reálné číslo, nebo celé číslo.