Grundbegriffe Flashcards Preview

Operations Research > Grundbegriffe > Flashcards

Flashcards in Grundbegriffe Deck (28):
1

einfacher Weg

ohne Kantenwiederholung

2

elementarer Weg

ohne Knotenwiederholung

3

Euler Weg

jede kante wird benutzt

4

Hamilitonischer Weg

jeder Knoten wird benutzt

5

azyklischer Graph

kreisfreier Graph

6

Baum

azyklischer (Kreisfreier), zusammenhängender Graph

7

Grad eines Knotens

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

8

schreibweise Weg im gerichteten, ungerichteten Graphen

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

9

Schnitt (gerichtet/ ungerichtet): Schreibweise, Vokabular

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

10

Netzplan

-zusammenhängender, zyklenfreier, gerichteter Graph
-eindeutiger Anfang, eindeutiges Ende

11

Vorgangsknotennetz

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

12

zusammenhängend, stark zusammenhängend

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

13

Clique

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

14

Vorgangsknotennetz: Frühestens/ Spätestens

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)

15

Vorgangsknotennetz: kritische Pfade

Knoten i mit Ti=[o̱,ō] mit o̱ = ō
Es kann mehrere geben!

16

Breitensuche

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

17

Tiefensuche

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

18

Bedingungen für kürzesten Pfad

1. stark Zusammenhängend
2. keine Negativen Zirkel

19

Topologische Sortierung Ziel/ Vorraussetzungen

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

gerichtet, keine Zyklen

20

Kreisfreiheit überprüfen

Topologische Sortierung

21

Residualgraph

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

22

augumentierter Weg

Weg durch den Residualgraphen von Start zu Ziel

23

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

Residualgraph enthält keinen augumentierten Pfad mehr

24

minimaler s-t-Schnitt

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

25

Modellierung: Zeitexpansion

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

26

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

∑bi = 0 (notwendige Bedingung)

27

Kosten eines b-Flusses

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

28

Residualgraffffffff b-Fluss

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.