====== Orientované grafy ======
{{ http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/DirectedDegrees.svg/300px-DirectedDegrees.svg.png}}
[[wp>Directed graph]]

**Orientovaný graf** //G// = (//U//, //H//)
  * **//U//** je konečná množina uzlů
  * **//H//** je konečná množina uspořádaných dvojic určující orientované hrany mezi uzly

**Ohodnocený orientovaný graf** je orientovaný graf vbe kterém mají hrany přiřazené váhy.

Můžeme zde hovořit o vstupním a výtupním [[wp>Degree (graph theory)|stupni uzlu]], viz graf napravo.
===== Orientované cesty a kružnice =====
===== Souvislost a silná souvislost =====
Orientovaný graf je **souvislý**, pokud nemá izolované podgrafy (komponenty), je to prostě jeden ucelený graf. Jinak řečeno, pokud odstraníme orientace hran a dostaneme //souvislý obyčejný graf//, je i orientovaný graf //souvislý//.

Orientovaný graf je **silně souvislý**, pokud mezi každými dvěma uzly existuje orientovaná cesta.
===== Turnaj =====
[[wp>Tournament (graph theory)]]

Když vezmeme [[wp>Complete graph|úplný neorientovaný graf]] a libovolně mu "zorientujeme" hrany, dostáváme **turnaj**.
===== Eulerovský graf =====
**[[wp>Eulerian path|Eulerovský tah]]** (kružnice) je takový tah který každou hranou projde právě jednou.

Pokud dokážeme v grafu najít Eulerovský tah, je to **Eulerovký graf**. Jinak řečeno je to graf který dokážeme nakreslit jedním tahem.

Nutnou podmínkou pro existenci eulrovské kružnice je, aby [[wp>Degree (graph theory)|stupeň]] každého uzlu byl sudý.
===== Dijkstrův a Floyd-Warshallův algoritmus pro hledání cesty minimální délky =====
==== Dijkstrův algoritmus ====
{{ http://upload.wikimedia.org/wikipedia/commons/4/45/Dijksta_Anim.gif}}
**[[wp>Dijkstra's algorithm]]**
  - Nastav každému uzlu vzdálenost. Počátečnímu 0, všem ostatním ∞. Označ všechny uzly jako nenavštívené.
  - Najdi nenavštívený uzel s nejmenší známou vzdáleností a označ ho jako aktuální. Uvažuj všechny jeho nenavštívené sousedy.
  - Spočítej vzdálenosti k sousedům jako známá vzdálenost aktuálního uzlu + ohodnocení hrany k sousedovi. Pokud je vypočtená vzdálenost menší než známá vzdálenost souseda, použij místo ní novou vypočtenou vzdálenost.
  - Označ aktuální uzel za navštívený a pokračuj na 2.
<note important>Dijkstrův algoritmus nefunfguje se zápornými hranami!</note>
==== Floyd-Warshallův algoritmus ====
[[wp>Floyd–Warshall algorithm]], http://students.ceid.upatras.gr/~papagel/english/java_docs/allmin.htm

<code>
procedure FloydWarshall()
	for k := 1 to n
		for i := 1 to n
			for j := 1 to n
				path[i][j] = min(path[i][j], path[i][k] + path[k][j]);
</code>
<note tip>Pokud je na diagonále záporné číslo, je v grafu záporná smyčka!</note>