# Algorithmen und Datenstrukturen: 11. Blatt

## Aufgabe 1

### 1a)


Grapheigenschaften:

- gerichtet
- kreisfrei
- lila und rosa

### 1b)

TopologicalSort(G) liefert: j e h f c a b d g l.
Die Reihenfolge ist durch die alphabetische Vorgabe eindeutig,
denn ohne diese könnte man als zweiten gefunden Knoten nicht a,
sondern b und dadurch würde sich dann die Reihenfolge ändern.

## Aufgabe 2

### 2a)

1. Berechne finish times für alle Knoten mit $DFS(G)$:
2. Berechne den transponierten Graphen $G^T$:
3. Rufe $DFS(G^T)$ auf, aber betrachte die Knoten in der Hauptschleife nach
absteigend sortierten finish times:
4. Gib die Knoten der DFS-Bäume aus Schritt 3
als Zusammenhangskomponenten aus:
{1,5,9,2},{6,10,12},{3,8,4,11,7}

### 2b)

DFSmitZusammenhang(Graph G = (V, E))
  foreach u ∈ V do
    u.color = white
    u.π = nil time = 0 // globale Variable! 
  Arraylist<Graph> Zusammenhangskomponenten = new Arraylist<Graph>()
  i = 0
  foreach u ∈ V do 
    if u.color == white then 
      Zusammenhangskomponenten[i] = DFSVisitMitZusammenhan(G, u)
      i++
  for j=0 to i
    return Zusammenhangskomponenten[j]

DFSVisitMitZusammenhang(Graph G, Vertex u)
  Komponente = new Graph()
  Komponente.addVertex(u)
  time = time + 1
  u.d = time
  u.color = gray
  foreach v ∈ Adj\[u\] do 
    if v.color == white then 
      Komponente.addEdge(u,v)
      v.π = u
      DFSVisitMitZusammenhang(G, v)
  time = time + 1
  u.f = time
  u.color = black
  return Komponente

## Aufgabe 3

### 3b)

Wir nehmen den kleinsten gerichteten azyklischen Graphen.
Dieser besitzt eine Quelle (lila markiert):

Nun nehmen wir einen weiteren Knoten dazu und
verbinden ihn mit einer gerichten Kante mit einem der vorherigen Knoten.
Wir können ihn entweder an die Quelle hängen oder an den anderen Knoten.
Je nachdem wie wir die Kante ausrichten, wird der neue Knoten selbst zur Quelle
oder die Anfangsquelle bleibt oder beides.
Fall 1:

- 1.1: 
- 1.2: 

Fall 2:

- 2.1: 
- 2.2: 

Wenn wir nun noch eine weitere Kante an den neu angefügten Knoten hängen,
um ihn mit dem restlichen Knoten zu verbinden, erhalten wir neue mögliche Graphen:

- 1.1.1: 
- 1.1.2: 
- 1.2.1: 
- 1.2.2: 

- 2.1.1: 
- 2.1.2: 
- 2.2.1: 
- 2.2.2: 

In genau einem der Fälle existiert anschließend keine Quelle mehr.
Jedoch ist dieser Graph nicht mehr azyklisch,
es existiert also ein Widerspruch zur Voraussetzung.
Dieses Verfahren lässt sich immer anwenden,
wenn ein neuer Knoten zu einem azyklisch gerichteten Graphen hinzugefügt wird.
Damit ist die Aussage bewiesen.

### 3c)

Wenn bei einer Tiefensuche genau eine Rückwärtskante entdeckt wird,
heißt dass, das genau ein Knoten existiert, der in dem Moment,
in dem die Rückwärtskante entlanggelaufen wird, folgendermaßen aussieht:
Wäre der Knoten weiß, wären wir an einer Baumkante entlanggelaufen,
wäre er schwarz, wären wir entweder eine Vorwärts- oder Kreuzkante entlanggelaufen.
Eine Rückwärtskante trifft also genau auf solch einen Knoten.
Da es allerdings vollkommen unabhängig davon ist,
welche der beiden Kanten wir in welcher Reihenfolge
zum Knoten entlanggehen, ergibt jede mögliche Tiefensuche
genau eine Rückwärtskante.