Graf

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

Graf je uspořádaná dvojice $(V, E)$, kde

• $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

Orientovaný graf je graf, jehož množina $E$ obsahuje orientované hrany.

Hrana je $(u, v) ∈ E$ je uspořádaná dvojice. Platí tedy $E ⊆ V × V$

Neorientovaný graf

Neorientovaný graf je graf, jehož množina hran $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.