— — Orientované grafy

Orientované grafy

Orientovaný graf: \overrightarrow{G} = (V, \overrightarrow{E}), kde V je libovolná konečná množina a \overrightarrow{E} ≡ V × V.

Definice:

deg^{+} v = vstupní stupeň v = počet hran vedoucích do v. deg^{−} v = výstupní stupeň v = počet hran vedoucích z v.

Příklad:

\overrightarrow{G} = (\{a, b, c\}, \{(a, b), (b, b), (a, c), (c, a)\})

¡“ ˙ *-/ /— b

/ a /

* -----¿ * c ¡-----

deg^{+} a = 1  deg^{+} b = 2
deg^{−} a = 2  deg^{−} b = 1

Definice:

\overrightarrow{G} je slabě souvislý, pokud ∀x, y ∈ V existuje (neorientovaná) cesta z x do y.

x• → • ← • → • ← •y

\overrightarrow{G} je slabě souvislý, pokud ∀x, y ∈ V existuje orientovaná cesta z x do y.

x• → • → • → • → •y

Definice:

Orientovaný graf \overrightarrow{G} je eulerovský, pokud lze nakreslit jedním uzavřeným orientovaným tahem.

⋯ → • → • → ⋯

VĚTA (podmínka eulerovského grafu):

\overrightarrow{G} = (V, \overrightarrow{E}) je eulerovský ⟺ \overrightarrow{G} je slabě souvislý a \underbrace{∀v ∈ V : deg^{+} v = deg^{−} v}_{(∗)}.

DŮKAZ:

“⇒”

Zřejmé.

“⇐”

LEMMA: Každou hranou grafu splňujícího (∗) vede uzavřený orientovaný tah.

DŮKAZ:

Nejdelší orientovaný tah danou hranou je uzavřený. Když ho totiž vedeme, postupně umazáváme hrany a nakonec nám podle rovnosti v (∗) zbyde jen poslední hrana, která vede do v.

Q.E.D.

Nejdelší uzavřený orientovaný tah v \overrightarrow{G} je eulerovský. Jinak (obdobně jako v neorientovaném případě, schematicky):

/¡-“

— * nejdelší uzavřený orientovaný tah “-¿/

Po použití lemmatu a odstranění hran tahu bychom však našli ještě další jiný uzavřený orientovaný tah, díky souvislosti má alespoň jeden společný vrchol. Pak ale můžeme oba tahy propojit do jednoho delšího uzavřeného tahu.

♯̸ Spor