Brainscape's Knowledge GenomeTM

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


See full index

Algorithmen und Datenstrukturen SS2018 > Kapitel 7: Graphen > Flashcards

Kapitel 7: Graphen Flashcards

1
Q

Definition Graph

A

Ein Graph G=(V,E) besteht aus einer menge von Knoten (vertices) V und einer Menge von Kanten (edges) E, die jeweils zwei Knoten miteinander verbinden.

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

Was bedeutet V bei Graphen ?

A

Vertices / Knoten

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

Was bedeutet E bei Graphen ?

A

Edges / Kanten

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

Was bedeutet gerichtet bei Graphen ?

A

Graphen bestehen aus Kanten aus geordneten Paaren (v,w) != (w,v)

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

Was bedeutet gewichtet bei Graphen ?

A

Die Kantenverbindungen der Graphen sind bewertet (mit einer Zahl)

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

Wann ist ein Knoten adjazent ?

A

Ein Knoten w ist adjazent (benachbart) zu v genau dann, wenn (v,w) existiert.

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

Was ist IVI bei Graphen ?

A

Anzahl der Knoten

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

Was ist IEI bei Graphen ?

A

Anzahl der Kanten

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

Was bedeutet adjazent ?

A

benachbart

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

Was ist eine reflexive Kante ?

A

Eine reflexive Kante (self-loop), auch Schlinge genannt, ist eine Kante, die einen Knoten mit sich selbst verbindet.

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

Wie nennt man auch Self-loops bei Graphen ?

A

reflexive Kanten

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

Was charakterisiert Multigraphen ?

A

parallele Kanten sind vorhanden

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

Was charakterisiert einfache Graphen ?

A

Graphen ohne parallele oder reflexive Kanten

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

Was ist ein Pfad bei Graphen ?

A 
Ein Pfad in einem Graphen besteht
aus einer Folge von Knoten, die
durch Kanten verbunden sind. In
einem einfachen Pfad kommt jeder
Knoten nur einmal vor.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Was ist ein Zyklus ?

A

Ein Zyklus ist ein Pfad, der im selben

Knoten beginnt und endet.

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

Was ist ein einfacher Zyklus ?

A 
Als einfachen Zyklus wird ein Zyklus
bezeichnet, bei dem sich keine
Kanten und Knoten wiederholen (bis
auf den ersten und den letzten
Knoten).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Was ist die Länge eines Pfades oder eines

Zyklus ?

A

die Anzahl der Kanten.

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

Wann ist ein Graph zusammenhängend ?

A

wenn es von jedem Knoten aus einen
Pfad zu allen anderen Knoten im
Graphen gibt.

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

Wann ist ein Graph stark zusammenhängend ?

A

wenn im
Graphen von jedem Knoten zu jedem
anderen Knoten eine Kante existiert.

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

Wie heißt ein Graph ohne Zyklen ?

A

azyklischer Graph

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

Welche Graphen-Eigenschaften werden durch einen Baum repräsentiert ?

A
  • azyklischer Graph

- zusammenhängender graph

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

Was ist ein Spannbaum eines

zusammenhängenden Graphen ?

A

ein Teilgraph, der alle Knoten des
Graphen enthält und ein Baum ist.
(aber nicht alle Kante)

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

Was charakterisiert einen Wald ?

A

eine disjunktive (einander ausschließende) Menge von Bäumen

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

Was ist ein Spannwald eines nicht (!)

zusammenhängenden Graphen

A

die Vereinigung der Spannbäume

seiner Zusammenhangskomponenten.

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

Was gibt die Dichte eines Graphen an ?

A

wie viele der möglichen Knotenpaare

tatsächlich durch Kanten verbunden sind.

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

Was ist ein dünner Graph ?

A

hat wenige der möglichen Kanten miteinander verbunden

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

Was ist ein dichter Graph ?

A

fehlen nur wenige der

möglichen Kanten

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

Was ist ein bipartiter Graph ?

A

ein Graph, dessen Knoten in zwei Mengen aufgeteilt werden können, wobei jede Kante jeweils einen Knoten der einen Menge mit einem Knoten der anderen Menge verbindet.
(Rot Schwarz)

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

Was ist die Speicherung der Kantenliste ?

A

G[0] = lVl
G[1] = lEl
anschließend kommen die paare
z.b. { 6,11,1,2,1,3..}

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

Kantenliste interpetieren

{ 6,11,1,2,1,3..}

A
  • 6 Knoten
  • 11 Kanten und einer
  • Verbindung von 1-2
  • Verbindung von 1-2 1-3
31
Q

Was ist bei der Speicherung in Form einer Kantenliste bei unterrichteten Graphen zu achten

A

die Kante von v zu w muss doppelt gespeichert werden

v,w) und (w,v

32
Q

Speicheraufwand Kantenliste

A

2+2*E

33
Q

Was ist die Speicherung der Knotenliste ?

A 
G[0] = lVl
G[1] = lEl
zudem
- Anzahl ausgehend Kanten
- Und Zile der Kanten
z.b. { 6,11,2,2,3,0,3,1,4,6}...
34
Q

Knotenliste interpetieren

z.b. { 6,11,2,2,3,0,3,1,4,6}…

A
  • 6 Knoten
  • 11 Kanten und einer
  • 2 Verbindung vom 1. Knoten zu K2 und K3
  • 0 Verbindung vom 2. Knoten
  • 3 Verbindung vom 3. Knoten zu K1, K4 und K6
35
Q

Speicheraufwand Knotenliste

A

2 + lVl + lEl

36
Q

Bei dichten Graphen benötigt welche Datenstruktur weniger Speicher ?

A

Knotenliste

37
Q

Wie liest man die Adjazenzmatrix ?

A

Zeilen = von Knoten
Spalten = nach Knoten
Dort wo eine 1 steht gibt es die Verbindung

38
Q

Eigenschaft der Adjazenzmatrix bei ungerichteten Graphen ?

A

Symmetrische Matrix (gespiegelt da G(v,w) = G(w,v))

39
Q

Speicheraufwand Adjazenzmatrix

A

lVl * lVl

40
Q

Für wann ist die Adjazenzmatrix geeignet ?

A

für dichte Graphen

41
Q

Was ist die Adjazenzliste ?

A

Vector der Knoten: jedes Element enthält einen weiteren Vector der die adjazenzten Knoten enthält

42
Q

Speicheraufwand Adjazenzliste

A

lVl + lEl

43
Q

Was ist der Grad (bzw. die Valenz) eins Knotens ?

A

Dabei ist dG(v) in Graphen ohne Mehrfachkanten und Hypergraphen die Anzahl der Nachbarn von v, Graphen mit Mehrfachkanten die Summe der Vielfachheiten aller mit v inzidenten Kanten.

44
Q

Welche Grade gibt es noch bei Graphen ?

A

Minimalgrad, Maximalgrad , Durchschnittsgrad

45
Q

Formel Durchschnittsgrad eines Graphen

A

2 * lEl / lVl

46
Q

Mit welchem Aufwand kann eine Kante (v,w) bei einem Graph hinzugefügt werden ?

A

1

47
Q

Aufwand : prüfen ob w Nachbar von v ist : Kantenliste

A

E

48
Q

Aufwand : prüfen ob w Nachbar von v ist : Adjazenzmatrix

A

1

49
Q

Aufwand : prüfen ob w Nachbar von v ist : Adjazenzliste

A

degree(v)

50
Q

Aufwand : Über Nachbarknoten von v iterieren: Kantenliste

A

E

51
Q

Aufwand : Über Nachbarknoten von v iterieren: Adjazenzmatrix

A

V

52
Q

Aufwand : Über Nachbarknoten von v iterieren: Adjazenzliste

A

degree(v)

53
Q

Was ist die Methode von Tremaux ?

A 
Erkunde alle Wege eines Labyrinths
- Rolle Faden hinterher
- markiere alle Kreuzungen und Wege, wenn sie das erste Mal betreten werden
- gehe mithilfe des Fadens zurück, wenn
man an eine markierte Kreuzung
kommt.
- Gehe noch weiter zurück, wenn man
beim Zurückgehen an eine Kreuzung
kommt, deren Wege bereits alle
besucht wurden.
54
Q

Verfahren der Tiefensuche

A
  1. Markiere alle Knoten v E V als nicht besucht.
  2. Wähle einen nicht besuchten Knoten v E V und markiere diesen als besucht.
  3. Besuche (rekursiv) alle benachbarten Knoten w von v, die noch nicht markiert sind und führe für diesen Knoten die Tiefensuche durch.
55
Q

Conncected Components: Wie überprüfe ich ob v und w verbunden sind ?

A

id[v] == id[w]

56
Q

Connected Components: was bedeutet

id[2] = 0 und id[3] = 1

A

der dritte Knoten ist in einem anderen Teilgraphen als der vierte Knoten (unzusammenhängende Graphen)

57
Q

Connected Components: Aus wie vielen Zusammenhangskomponenten besteht der Graph?

A

count +1

58
Q

Vorteil Breitensuche

A

Die Breitensuche liefert für alle verbundenen Knoten die kürzesten Pfade. Der Suchbaum hat somit die geringste Höhe.

59
Q

was bedeutet MST ?

A

minimum spanning tree

60
Q

Definition Minimaler Spannbaum

A

Der minimale Spannbaum eines kantengewichteten Graphen ist ein Spannbaum, dessen Summe seiner Kantengewichte minimal ist gegenüber irgendeines anderen Spannbaums.

(möglichst wenig Kanten um alle Knoten miteinander zu verbinden)

61
Q

Was ist der Prim Algorithmus ?

A
  • Startknoten für MST auswählen
  • immer günstigste Kante auswählen (erweitern)
  • nach lVl-1 Kanten ist der MST gefunden
62
Q

Welche DS benutzt der Prim Algorithmus ?

A

Knoten: knotenindiziertes boolsches Array
Kanten : Warteschlange mst und Array
Randkanten: Prioritätswarteschlange

63
Q

Was sind Randkanten ?

A

Randkanten sind die Menge der adjazenten Kanten, die den Baum um einen nicht besuchten Knoten erweitern. Dafür wird eine

64
Q

Aufwand Prim Algorithmus

A

ungefähr O(E*logE)

65
Q

Was ist der Algorithmus von Kruskal ?

A
  • Sortiere die Kanten nach ihren Gewichten.
  • Verarbeite die Kanten in der Reihenfolge ihrer Gewichte (vom kleinsten zum größten).
  • Nehme immer eine Kanten zum MST hinzu, wenn dadurch kein Zykel im Baum entsteht.
  • Nach V - 1 Kanten ist der MST gefunden.
66
Q

Definition (Gerichteter Graph (Digraph))

A

besteht aus
- einer Menge von Knoten
- einer Menge von gerichteten Kanten
Jede gerichtete Kante verbindet ein geordnetes Paar von Knoten.

67
Q

Definition (Kürzester Pfade mit einem Startknoten)

A

Ein Kürzester Pfad von einem Knoten s zu einem Knoten t in einem kantengewichteten Digraphen ist ein gerichteter Pfad von s zu t mit der Eigenschaft, dass kein anderer Pfad ein niedrigeres Gewicht hat.

68
Q

Was ist ein Digraph ?

A

Ein Gerichteter Graph

69
Q

Definition (Kürzeste Pfade Baum)

A

Ein Kürzester-Pfade-Baum für einen Startknoten s ist ein Teilgraph, der s und alle von s aus erreichbaren Knoten enthält, die einen gerichteten Baum mit der Wurzel s bilden, so dass jeder Baumpfad ein kürzester Pfad im Digraphen ist.

70
Q

Was ist eine Kantenrelaxation ?

A

Eine Kante v -> w wird relaxiert, wenn der kürzeste Weg von s nach w über die Kante von v nach w verläuft.

Alternative: Ein Knoten w wird relaxiert, wenn der kürzeste Weg von s über die Kante v -> w zum Knoten w verläuft.

71
Q

Was berechnet der Dijkstra Algorithmus?

A

einen Kürzeste-Pfade-Baum (SPT)

72
Q

Laufzeit Dijkstra

A

ungefähr O(ElogV)

73
Q

Speicher Dijkstra und Prim

A

Ungefähr O(V)

Algorithmen und Datenstrukturen SS2018 (6 decks)

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