Graphenalgorithmen

Question 1

Wie ist ein ungerichteter Graph definiert?

Answer 1

Question 2

Wie ist ein gerichteter Graph definiert?

Answer 2

Question 3

Wie ist ein Multigraph definiert?

Answer 3

Question 4

Wie ist ein Hypergraph definiert?

Answer 4

Question 5

Wie ist Adjazenz definiert?

Answer 5

Question 6

Wie ist Inzidenz definiert?

Answer 6

Question 7

Wie bestimmt man den Grad eines Knotens in einem ungerichteten Graphen?

Answer 7

Question 8

Wie bestimmt man den Grad eines Knotens in einem gerichteten Graphen?

Answer 8

Question 9

Wie nennt man Graphen ohne Zyklen?

Answer 9

azyklisch

Question 10

Wann ist ein ungerichteter Graph verbunden?

Answer 10

Wenn zwischen allen Knoten eine Verbindung besteht

Question 11

Wann ist ein gerichteter Graph stark verbunden?

Answer 11

Wenn zwischen allen Knoten in beiden Richtungen eine Verbindung besteht

Question 12

Was ist die Zusammenhangskomponente?

Answer 12

maximal zusammenhängender Subgraphen eines ungerichteten Graphen

Question 13

Was ist eine starke Zusammenhangskomponente?

Answer 13

maximal zusammenhängender Subgraphen eines ungerichteten Graphen

Question 14

Wann sind zwei Graphen isomoprh?

Answer 14

Question 15

Wie ist ein Baum anhand von Graphen definiert?

Answer 15

Question 16

Wie ist ein Wald anhand von Graphen definiert?

Answer 16

Question 17

Wie ist ein DAG definiert?

Answer 17

Question 18

Wie ist ein vollständiger Graph definiert?

Answer 18

Question 19

Wie ist ein bipartiter Graph definiert?

Answer 19

Question 20

Wie ist ein planarer Graph definiert?

Answer 20

Graph lässt sich ohne Kantenüberschneidungen zeichnen

Question 21

Wie lassen sich Graphen repräsentieren?

Answer 21

• Adjazenzmatrix
• Ajazenzlisten

Question 22

Was ist der Vorteil an einer Adjazenzmatrix?

Answer 22

Effizienter Test auf das Vorhandensein einer Kante

Question 23

Was ist der Nachteil an einer Adjazenzmatrix?

Answer 23

Speicherbedarf von Θ(N^2)

Question 24

Was sind die Vorteile von Ajazenzlisten?

Answer 24

Question 25

Beschreib die Breitensuche

Answer 25

Question 26

# 1 Was ist ein BFS-Baum? | Welche Laufzeit hat BFS()?

Answer 26

Baum, der bei der Breitensuche entsteht Θ(V+E)

Question 27

Was bestimmt man durch die Breitensuche?

Answer 27

Den kürzesten Pfad von s nach u

Question 28

# 1 Beschreib die Tiefensuche | Was ist die Laufzeit?

Answer 28

Θ(V+E)

Question 29

Was bedeutet DFS-Wald?

Answer 29

Question 30

Was besagt das Klammerungstheorem?

Answer 30

Question 31

Beschreib das Theorem der weißen Pfade

Answer 31

Question 32

Was sind Baumkanten?

Answer 32

Baumkante: wird durchlaufen beim ersten Besuch von v [dicke rote Kanten]

Question 33

Was sind Rückkanten?

Answer 33

Rückkante: zeigt auf einen Vorgänger im DFS-Baum [Typ B]

Question 34

Was sind Vorwärtskanten?

Answer 34

Vorwärtskante: zeigt auf einen Nachfolger im DFS-Baum [Typ F]

Question 35

Was sind Querkanten?

Answer 35

Querkante: nicht von anderem Typ [Typ C]

Question 36

Beschreib die Kantenklassifikation während der Tiefensuche

Answer 36

Question 37

In einem ungerichteten Graphen, was gilt für (v, u), wenn Type[(u, v] = TREE ist?

Answer 37

TYPE[v, u] = BACK

Question 38

In einem ungerichteten Graphen, was gilt für (v, u), wenn Type[(u, v] = BACK ist?

Answer 38

TYPE[(v, u)] = FORWARD

Question 39

Beschrieb topologisches Sortieren

Answer 39

Question 40

Wie ist eine starke Zusammenhangskomponente definiert?

Answer 40

Question 41

Was ist ein transponierter Graph?

Answer 41

Alle Pfadrichtungen umgekehrt

Question 42

Was ist ein Komponentengraph?

Answer 42

## Footnote ist ein DAG

Question 43

Wie kann man die Starken Zusammenhangskomponenten von einem Graphen bestimmen?

Answer 43

1. Tiefensuche 2. Kanten invertieren 3. Knoten besuchen in absteigender Reihenfolge nach der finishing time 4. Tiefensuche für Knoten und speichern der SCC Information

Question 44

In welcher Reihenfolge werden die Kompontenten bei der Suche von SCCs ausgegeben?

Answer 44

In einer Reihenfolge einer topologischen Sortierung

Question 45

Was ist das MST-Problem?

Answer 45

Question 46

Was sind Greedy Algorithmen?

Answer 46

Question 47

Wie sind sichere Kanten im Kontext von MSTs definiert?

Answer 47

Question 48

Definiere eine leichte Kante im Kontext von MSTs

Answer 48

Question 49

Was gilt für eine leichte Kante, die einen Schnitt eines Graphens kreuzt?

Answer 49

Sie ist eine sichere Kante

Question 50

Beschreib den Kruskals Algorithmus

Answer 50

* A beschreibt einen Wald, mit jeder Kante werden zwei Bäume zu einem verschmolzen. * Zu Beginn haben wir |V| Bäume mit je einem Knoten. * Kanten werden mit aufsteigendem Gewicht eingefügt. * Schnitt trennt jeweils einen Baum vom Rest des Graphen.

Question 51

Was ist die Idee der Union-Find Datenstruktur?

Answer 51

Question 52

Bschreib union-by-rank

Answer 52

(UNION-Operation) hänge den flacheren Baum unter den tieferen

Question 53

Beschreib path-compression

Answer 53

(FIND-SET-Operation) hänge alle Teilbäume auf dem Pfad zur Wurzel unter die Wurzel

Question 54

Was löst der Ford-Fulkerson Algorithmus?

Answer 54

Das Max-Flow-Problem

Question 55

Wie geht der Ford Fulkerson Algorithmus vor?

Answer 55

1. findet wiederholend argumentierende Pfade durch den residualen Graphen 2. argumentiert den Flow bis keine AP mehr gefunden werden können 3. addiert dann die bottleneck-values

Question 56

Was ist ein argumentierender Pfad?

Answer 56

ein Pfad mit einer ungenutzen kapazität größer als 0 von s zu t

Question 57

Wie argumentiert man den Flow?

Answer 57

Man aktualisiert die Flow Daten der Kanten in einem argumentierenden Pfad, indem man den kapazitätswert-flowwert der kleinsten Kante hinzuaddiert. Dannach verringert man den flow der Backwards-Kanten

Question 58

Wie funktioniert der Edmonds-Karp Algorithmus?

Answer 58

wie ford fulkerson method, aber: Wähle als augmentierenden Pfad den kürzesten Pfad (uniformes Kantengewicht von 1) von s nach t

Question 59

Was ist Maximales bipartites Matching?

Answer 59