Grundbegriffe

Question 1

einfacher Weg

Answer 1

ohne Kantenwiederholung

Question 2

elementarer Weg

Answer 2

ohne Knotenwiederholung

Question 3

Euler Weg

Answer 3

jede kante wird benutzt

Question 4

Hamilitonischer Weg

Answer 4

jeder Knoten wird benutzt

Question 5

azyklischer Graph

Answer 5

kreisfreier Graph

Question 6

Baum

Answer 6

azyklischer (Kreisfreier), zusammenhängender Graph

Question 7

Grad eines Knotens

Answer 7

d(i) Anzahl der zu i indizierten Knoten
Innengrad (eingehend): d-
Außengrad (ausgehend): d+

Question 8

schreibweise Weg im gerichteten, ungerichteten Graphen

Answer 8

ungerichtet: a->b: { {a,x}, {x,y}, {y,b} }
gerichtet: a->b: { (a,x), (x,y), (y,b) }

Question 9

Schnitt (gerichtet/ ungerichtet): Schreibweise, Vokabular

Answer 9

Knotenmenge X={a, b, c} induziert den Schnitt
δ(X)={{}, {}, {} ungerichtete Kanten}
oder (gerichtet)
δ+(X)={(),() ausgehende Kanten}
δ-(X)={(),() eingehende Kanten}

Question 10

Netzplan

Answer 10

• zusammenhängender, zyklenfreier, gerichteter Graph

- eindeutiger Anfang, eindeutiges Ende

Question 11

Vorgangsknotennetz

Answer 11

• Knoten entspricht Vorgang
• Kanten: Abhängigkeitsbeziehungen
  !! Im Netzplan dürfen keine Kreise auftreten (a müsste vor beginn von b beendet werden)

Question 12

zusammenhängend, stark zusammenhängend

Answer 12

jeder Knoten kann von jedem knoten im gerichteten (stark zusammenhängend)/ ungerichteten (zusammenhängend) Graph erreicht werden.

Question 13

Clique

Answer 13

Knotenfärbungsproblem: Eine Gruppe von zusammenhängenden Knoten die eine unterschiedliche Farbe haben

Question 14

Vorgangsknotennetz: Frühestens/ Spätestens

Answer 14

i: Knoten
Ti=[o̱,ō]
o̱:frühestens -> vorwärts rechnen (größte zeit für knoten wählen)
ō:spätestens -> rückwärts rechnen (kleinste zeit für knoten wählen)

Question 15

Vorgangsknotennetz: kritische Pfade

Answer 15

Knoten i mit Ti=[o̱,ō] mit o̱ = ō

Es kann mehrere geben!

Question 16

Breitensuche

Answer 16

FiFo: Alle Kanten werden parallel betrachtet, erst wenn alle kanten gefunden sind, wird ein level tiefer gegangen und der Prozess wiederholt. L von vorne nach hinten

Question 17

Tiefensuche

Answer 17

LiFo: Von jedem entdeckten Knoten wird an einer kante weitergesucht. Es entsteht ein! weg der alle Knoten verbindet. L von hinten nach vorne

Question 18

Bedingungen für kürzesten Pfad

Answer 18

1. stark Zusammenhängend

2. keine Negativen Zirkel

Question 19

Topologische Sortierung Ziel/ Vorraussetzungen

Answer 19

Beste Reihnfolge durch den Graphen finden, um alle Knoten zu erreichen.

gerichtet, keine Zyklen

Question 20

Kreisfreiheit überprüfen

Answer 20

Topologische Sortierung

Question 21

Residualgraph

Answer 21

Flüsse (x/y) aufteilen in:

• wie viel kann noch erhöht werden: Vorwärtskante
• wie weit kann noch zurückgefahren werden: Rückwärtskante

Question 22

augumentierter Weg

Answer 22

Weg durch den Residualgraphen von Start zu Ziel

Question 23

Optimalitätskriterium für maximale s-t-Flüsse

Answer 23

Residualgraph enthält keinen augumentierten Pfad mehr

Question 24

minimaler s-t-Schnitt

Answer 24

Alle Knoten die von S aus im Residualgraph noch zu erreichen sind.
X={s, alle knoten aus dem schnitt}
δ(X)=δ+(X)={(),() ausgehende Kanten}

Question 25

Modellierung: Zeitexpansion

Answer 25

jeweils ein ort zu einem zeitpunkt bildet eine kante (minimalfluss)

Question 26

Zulässigkeit eines b-Flusses bestimmen/ kann es einen b-Fluss geben?

Answer 26

∑bi = 0 (notwendige Bedingung)

Question 27

Kosten eines b-Flusses

Answer 27

Kosten = Kapazität(i) * Kante(i)

Question 28

Residualgraffffffff b-Fluss

Answer 28

Vorwärtskante: (+a [Kosten: durch Erhöhung entstehen Kosten], Potential)
Rückwärtskante: (-a [Ersparnisse: durch Verringerung sinken die Kosten], Potential)

b´s an die Knoten schreiben.