Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algorithmen und Datenstrukturen > Graphenalgorithmen > Flashcards

Graphenalgorithmen Flashcards

1
Q

Wie ist ein ungerichteter Graph definiert?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Wie ist ein gerichteter Graph definiert?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Wie ist ein Multigraph definiert?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Wie ist ein Hypergraph definiert?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Wie ist Adjazenz definiert?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Wie ist Inzidenz definiert?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Wie nennt man Graphen ohne Zyklen?

A

azyklisch

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Wann ist ein ungerichteter Graph verbunden?

A

Wenn zwischen allen Knoten eine Verbindung besteht

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Wann ist ein gerichteter Graph stark verbunden?

A

Wenn zwischen allen Knoten in beiden Richtungen eine Verbindung besteht

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Was ist die Zusammenhangskomponente?

A

maximal zusammenhängender Subgraphen eines ungerichteten Graphen

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Was ist eine starke Zusammenhangskomponente?

A

maximal zusammenhängender Subgraphen eines ungerichteten Graphen

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Wann sind zwei Graphen isomoprh?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Wie ist ein Baum anhand von Graphen definiert?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Wie ist ein Wald anhand von Graphen definiert?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Wie ist ein DAG definiert?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Wie ist ein vollständiger Graph definiert?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Wie ist ein bipartiter Graph definiert?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Wie ist ein planarer Graph definiert?

A

Graph lässt sich ohne Kantenüberschneidungen zeichnen

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Wie lassen sich Graphen repräsentieren?

A
  • Adjazenzmatrix
  • Ajazenzlisten
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Was ist der Vorteil an einer Adjazenzmatrix?

A

Effizienter Test auf das Vorhandensein einer Kante

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Was ist der Nachteil an einer Adjazenzmatrix?

A

Speicherbedarf von Θ(N^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Was sind die Vorteile von Ajazenzlisten?

A
25
Q

Beschreib die Breitensuche

A
26
Q

1

Was ist ein BFS-Baum?

Welche Laufzeit hat BFS()?

A

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

27
Q

Was bestimmt man durch die Breitensuche?

A

Den kürzesten Pfad von s nach u

28
Q

1

Beschreib die Tiefensuche

Was ist die Laufzeit?

A

Θ(V+E)

29
Q

Was bedeutet DFS-Wald?

A
30
Q

Was besagt das Klammerungstheorem?

A
31
Q

Beschreib das Theorem der weißen Pfade

A
32
Q

Was sind Baumkanten?

A

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

33
Q

Was sind Rückkanten?

A

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

34
Q

Was sind Vorwärtskanten?

A

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

35
Q

Was sind Querkanten?

A

Querkante: nicht von anderem Typ [Typ C]

36
Q

Beschreib die Kantenklassifikation während der Tiefensuche

A
37
Q

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

A

TYPE[v, u] = BACK

38
Q

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

A

TYPE[(v, u)] = FORWARD

39
Q

Beschrieb topologisches Sortieren

A
40
Q

Wie ist eine starke Zusammenhangskomponente definiert?

A
41
Q

Was ist ein transponierter Graph?

A

Alle Pfadrichtungen umgekehrt

42
Q

Was ist ein Komponentengraph?

A

ist ein DAG

43
Q

Wie kann man die Starken Zusammenhangskomponenten von einem Graphen bestimmen?

A
  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
44
Q

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

A

In einer Reihenfolge einer topologischen Sortierung

45
Q

Was ist das MST-Problem?

A
46
Q

Was sind Greedy Algorithmen?

A
47
Q

Wie sind sichere Kanten im Kontext von MSTs definiert?

A
48
Q

Definiere eine leichte Kante im Kontext von MSTs

A
49
Q

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

A

Sie ist eine sichere Kante

50
Q

Beschreib den Kruskals Algorithmus

A
  • 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.
51
Q

Was ist die Idee der Union-Find Datenstruktur?

A
52
Q

Bschreib union-by-rank

A

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

53
Q

Beschreib path-compression

A

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

54
Q

Was löst der Ford-Fulkerson Algorithmus?

A

Das Max-Flow-Problem

55
Q

Wie geht der Ford Fulkerson Algorithmus vor?

A
  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
56
Q

Was ist ein argumentierender Pfad?

A

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

57
Q

Wie argumentiert man den Flow?

A

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

58
Q

Wie funktioniert der Edmonds-Karp Algorithmus?

A

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

59
Q

Was ist Maximales bipartites Matching?

A

Algorithmen und Datenstrukturen (8 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions