Graph Merkekästen

Question 1

Nenne alle möglichen Eigenschaften, die ein Graph haben kann

Answer 1

gerichtet/ungerichtet
gewichtet/ungewichtet
zusammenhängend (stark vs. schwach)
zyklisch/azyklisch

Question 2

Mathematische Definition eines Graphen

Answer 2

V = {v1, v2, … , vn}: eine endliche, nichtleere Menge aus Knoten
E = {e1, e2, … , em): eine endliche Menge aus Kanten
G = (V, E): Graph mit V und E
Kanten (Verbindungen zw. 2 Knoten) werden als zweielementige Teilmengen dargestellt: e = {v1, v3}

Question 3

Definition gerichtete Graphen

Answer 3

Kanten haben Pfeilspitzen, die angeben in welche Richtung sie zeigen
Hier werden Kanten als Tupel dargestellt:
e5 = (v3, v5) und e8 = (v5,v3)

Question 4

Was ist ein Pfad bzw. Weg?

Answer 4

eine Folge von Knoten, wobei aufeinanderfolgende Knoten durch eine Kante verbunden sind
einfacher Weg: alle Knoten sind paarweise verschieden
Schreibweise: (v1, … , vn)
Länge: Anzahl der Kanten bzw. n - 1

Question 5

Was ist ein Zyklus und welchen Spezialfall gibt es?

Answer 5

wenn Start- und Endknoten übereinstimmen und alle auf dem Weg verwendete Kanten paarweise verschieden sind (gleiche Kante nicht zweimal hintereinander)
Kreis: kein innerer Knoten wiederholt sich
zyklischer Graph enthält mindestens einen Zyklus

Question 6

Nachbarschaft

Answer 6

zwei Knoten sind benachbart oder adjazent, wenn sie durch eine Kante verbunden sind
N(x): Menge aller benachbarten Knoten zu einem Knoten x

Question 7

Wann ist ein Graph zusammenhängend? (mathematische Definition)

Answer 7

wenn für alle Knoten x,y ∈ V ein x,y-Weg existiert

Question 8

Ergänzungen zum gerichteten Graphen

Answer 8

(x,y) ∈ E: es gibt eine gerichtete Kante von x nach y –> x ist Vorgänger von y
(y,x) ∈ E: x ist Nachfolger von y
stark zusammenhängend vs. schwach zusammenhängend

Question 9

Ergänzungen gewichtete Graphen

Answer 9

Kanten als dreielementige Teilmengen:
e3 = {v1, v2,10)
Länge: Summe der Kantengewichte

Question 10

Wie stellt man einen Graph dar?

Answer 10

Mit einer Adjazenzmatrix:
erste Spalte und erste Zeile sind die Knoten und am Kreuzpunkt steht die Gewichtung
bei ungerichteten Graphen ist die Matrix symmetrisch

Question 11

Erkläre einen möglichen Graphendurchlauf

Answer 11

Mit dem Algorithmus der Tiefensuche:
Diese dringt immer so weit wie möglich in die Tiefe eines Pfades vor, und erst danach werden die restlichen Abzweigungen des Anfangsknotens bearbeitet.
Dieser Vorgang wird bei jedem Knoten wiederholt. Es ist eine rekursive Methode.
Diese Algorithmus funktioniert nur bei (stark) zusammenhängenden Graphen.

Question 12

Wann ist ein Graph ein Baum?

Answer 12

ungerichtet: zyklenfreiheit
gerichtet: zyklenfreiheit und jeder Knoten hat nur einen Vorgänger

Question 13

typische Graphenprobleme

Answer 13

Zusammenhangsprobleme: Suche nach Wegen von einem Knoten zu anderen Knoten (Navigationssysteme)

Suchprobleme: Suche nach kürzesten Wegen im Graphen (Navigationssysteme)

Euler-Kreise: Zyklus, bei dem jede Kante genau einmal besucht wird

Hamilton-Kreise: Zyklus, bei dem jeder Knoten genau einmal besucht wird, also ein Kreis (touristische Fahrten)