Orientované grafy

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 stupni uzlu, viz graf napravo.

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.

Tournament (graph theory)

Když vezmeme úplný neorientovaný graf a libovolně mu „zorientujeme“ hrany, dostáváme turnaj.

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 stupeň každého uzlu byl sudý.

Dijkstra's algorithm

1. Nastav každému uzlu vzdálenost. Počátečnímu 0, všem ostatním ∞. Označ všechny uzly jako nenavštívené.
2. 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.
3. 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.
4. Označ aktuální uzel za navštívený a pokračuj na 2.

Floyd–Warshall algorithm, http://students.ceid.upatras.gr/~papagel/english/java_docs/allmin.htm

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]);