cards-deck: 100-199_university::111-120_theoretic_cs::111_algorithms_datastructures

Topologisches Sortieren:

anchored to [[111.00_anchor]]

Definition

Betrachten wir einen DAG -> directed acyclic graph <- also einen solchen Graph, der gerichtet ist und dabei kein Zykel erzeugt. Wir möchten jetzt eine Abbildung erzeugen, die folgend nach der Menge von ausgehenden Kanten bei Knoten sortiert. Wir definieren sie folgend: $n u m : V ⟶ {1, 2, \dots, n}$ wobei $n = ∣ V ∣$ . Es muss jetzt $\forall (v, w) \in E$ gelten: $n u m (v) < n u m (w)$

[!Definition] Definition of topological sorting linear ordering of given vertices such that whenever there exists a directed edge from vertex u to vertex v, u comes before v in the ordering. > Vertices of a graph that point towards another node always come first, their pointed directions after them.

example of sort :
graph TD
job1 --> job2;
job1 --> job3;
execute 1 then 3 and 2 at the end

[!Important] Intuition für Topologisches Sortieren wie sortieren wir einen Graph? #card Prinzipiell sortieren wir so, dass das Element ganz ganz oben immer zuerst kommen wird. Weiterhin priorisieren wir dann immer die linken Kinder zuerst, werden diese also als nächstes in der Reihenfolge aufsetzen. Es existiert hier die Prämisse, dass Knoten immer vor den Kindern gesetzt werden.

^1704708770714

[!Example] Topologisches Sortieren: ![[Pasted image 20231112194730.png]] Wie sieht der Graph in topologischer Sortierung aus? #card ![[Pasted image 20231112194736.png]] ^1704708770726

[!Definition] topologische Sortierung möglich, wenn $G$ azyklisch ist: warum? #card Der Graph $G$ besitzt genau dann eine topologische Sortierung, wenn $G$ azyklisch ist. Wir möchten folgend den Beweis dieser Struktur herausfinden:

$⟹$ : Angenommen $G$ sei zyklisch, dann sei etwa $v_{o}, \dots, v_{k}$ ein Zykel, wob $v_{0} = v_{k}$ . Daraus muss dann für die topologische Sortierung gelten: $n u m (v_{0}) < u m (v_{1}) < \dots < u m (v_{k}) = u m (v_{0})$ Was im Widerspruch steht!

$L o n g l e f t a rro ww :$ Sei $G$ jetzt azyklisch. Wir behaupten, dass $v \in G : in d e g (v) = 0$ existiert. Wir setzen jetzt $v, u m (v) = 1$ und löschen diesen anschließend. Danach können wir mit einem induktiven Beweis fortfahren.

Beweis: Wir starten bei einem beliebigen $w$ und möchten jetzt dei eingehenden Kanten, zu diesem Knoten entlang laufen ( Also den Graph rückwärts ablaufen). Wir sollte nach spätestens $n - 1$ Schritten $v$ finden –> oder ein Zykel trat auf, was im Widerspruch steht. ^1704708770733

Algorithmische Darstellung TopSort:

Wir möchten mit der Laufzeit gerne $O (n + m)$ erreichen. Betrachten wir dafür folgenden PseudoCode:

int count = 0;
while(v in V: indeg(v) =0 ) {  # also noch nicht vom Algorithmus bearbeitet 
	count++;
	num(v) = count;
	entferne v mit ausgehenden Kanten 
	# --> dadurch werden alle Knoten, die wir schon betrachtet haben, herausgenommen bzw halt v selbst auch.
	
}
if (count < |V|) { 
	# also nach durchlaufen des ganzen Graphen haben wir kein Zykel gefunden --> was sich dadurch zeigt, dass wir mehr Knoten zählen, als sich in dem Graphen befinden!

}

Was dieser Algorithmus tun wird: ER sucht einen Startpunkt, also einen Knoten, der keine eingehende Kante aufweist. Dadurch wissen wir, dass dieser als Startpunkt dienen kann. Anschließend entfernen wir jetzt den gefundenen Knoten und auch seine ausgehenden Kanten. Durch das Entfernen werden wir neue Knoten erhalten, die keine eingehenden Kanten mehr haben und können so bei diesen weiterarbeiten. So arbeiten wir uns durch den ganzen Graphen und wenn wir am Ende mehr Punkte besucht haben, als enthalten sind, wissen wir, dass das nicht geht :D. Oder haben einen Azyklischen Graphen vorliegen!

[!Definition] Implementation mit Matrix oder Liste –> Ziel $O (n + m)$ ? #card Wir möchten den Algorithmus mit einer Adjazenzliste umsetzen, denn sie brauch im Platz nur $O (n + m)$ !

mit jedem Durchlauf werden wir $v$ und dessen ausgehenden Kanten löschen.

Das setzen wir um, indem wir $O u t A D J (v)$ durchlaufen und dabei $O (o u t d e g (v))$ konsultieren. Die gesamte Laufzeit ist dabei dann: $v \sum (O (o u t d e g (v))) = O (n + m)$ ^1704708770740

[!Question] Wie finden wir ein passend $v$ für den Start? #card Wir können dafür einen Counter erstellen: $in C o u n t er []$ für InDegrees und weiterhin nutzen wir die Menge $ZERO$ . Wenn wir jetzt eine Kante $(v, w)$ löschen, dann dekrementieren wir den inCounter[w], denn es wird eine Kante weniger auf diesen zeigen. Wir können eventuell $w$ anschließend in die Menge von $w$ aufnehmen –> da es womöglich keine eingehenden Kanten mehr hat! Wir schauen dann, ob wir ein geeignetes $v$ finden können und ziehen es in ZERO hinein. ZERO ist also Stack konzipiert und wird durch die Verarbeitung dann mit $O (1)$ laufen! ^1704708770747

[!Question] Wie initialisieren wir den $in Z a e h l er$ und $ZERO$ ? #card Dafür durchlaufen wir dei Adjazenz-liste und erhöhen dabei immer $in Z a e h l er [w]$ entsprechend für die Kante $(v, w)$ Wir müssen nun noch $ZERO$ initialisieren.

–> durch diese Operationen folgt dann: $O (n + m)$ ^1704708770753

Folgerung für Topologisches Sortieren:

[!Definition] SATZ | Lauzeit und Fähigkeit von TopSort #card Sei $G = (V, E)$ ein gerichteter Graph. In der Zeit $O (n + m)$ kann man jetzt feststellen, ob $G$ einen Zykel hat und wenn es keinen hat, $G$ entsprechend topologische sortieren. ^1704708770759

Eindeutigkeit für Topologische Sortierung

The topological sort of a DAG is unique if and only if the DAG contains a Hamiltonian path ) that is, a directed path that visits each vertex exactly once. >> Shortest path for Salesman as example for such graph.

Beispiele für Topologisches Sortieren:

Consider the following example of a problem: requirement :

schedule of jobs, one after the other, no parallel execution
dependencies like :
- job3 only happen after job 13 is done
- job 7 only available afer job 1 is done

task -> figure out whether a correct scheduling is possible at all

solution

directed graph with constraints as their edges

vertices correspond to jobs put an edge from job i to job j if job i has to be finished before job j

(job i) –> (job j) for | job i has to be finished before job j

afterwards applying topological sort:

when is it not possible anymore | Example

**when is a topological sort possible at all ? **

Is there a topological sort for any directed graph ?

NO whenever a cycle occurs within the graph we cant solve it anymore >> as that would resolve with endless dependencies and the paradox of needing something done before itself is able to be executed.

However if we have a DAG - directed acyclic graph >> graph with no cycle in itself - we can create a topological sort

if it exists, is a topological sort always unique ?

Furthermore the topological sort, if possible, is not strictly unique(eindeutig), because execution can be sorted with different starts :: job1 -> job 2 -> job 3 or job 1 -> job 3 -> job 2 . ^1704708770790 ![[Pasted image 20221107212022.png]]

Further references:

This topic is also covered in other fields.

we had to work and exercise it in [[111.84_assignment_04]]

scattered-lenity