OR

> in einem ungerichteten Graphen heisst eine Kette Kreis, wenn gilt io = it

> in einem gerichteten Graphen heisst ein Weg mit io = it Zyklus 

> Baum: Baum in G ist ein zusammenhängender, ungerichteter, zyklusloser Graph 

> Wald: ungerichteter kreisloser Graph, seine Komponenten sind Bäume 

• beginne beim Knoten welcher kein Vorgänger hat 
• wähle den nächsten Knoten indem l_v maximiert wird 
• fahre so fort 
• sucht den längsten Weg von einer Quelle s zu allen anderen Knoten im gerichtetem Graphen

Ein Gerüst in G ist ein Baum in G, welcher alle Knoten von G umfasst 

> sucht die kürzesten Wege von Knoten s zu allen anderen Knoten im gerichtetem/ungerichtetem Graphen "one to all"

> alle Längen der Kanten sind nichtnegativ 

> Zyklen sind zulässig, aber Zyklen negativer Länge dürfen nicht auftreten

> da keine negativ bewerten Kanten im Graphen vorkommen dürfen 

• Menge A der Knoten, zu denen bereits kürzester Weg von der Quelle S bekannt ist 
• Menge B der Knoten, zu denen Wege von s aus bekannt sind, jedoch nicht sicher ist, ob diese minimal sind 
• Menge C der Knoten, zu denen noch kein Wege von s aus bekannt sind 

• sortiere Kanten nach aufsteigenden Gewichten 
• markiere diese Kanten rot 
• es dürfen keine Zyklen entstehen 
• alle Orte müssen besucht werden und es muss eine verbindung zwischen den Punkten bestehen 

Eröffnungsverfahren: Bilde eine gute zulässige Lösung 

Verbesserungsverfahren: Verbessere diese Tour iterativ (2-opt) 

Die länge eines Weges ist die SUmme der Löngen seiner Kanten

kürzesten: keine negativen Zyklen im Graphen 

längsten: keine positiven Zyklen im Graphen 

1. wähle einen Knoten v, der kein Vorgänger hat und gebe ihm die nächste Nr. (v existiert immer wenn kein Zyklen vorhanden sind) 
2. Entferne Knoten v (mit seinem Bogen) und fange wieder bei Schritt 1 an 

• wähle einen Startknoten 
• von diesem aus zum nächsten mit der kleinsten Distanz 
• fahre von diesem Knoten genau gleich fort, also zum nächsten Knoten mit der kleinsten Distanz 

1. wähle 2 Knoten v und w und starte mit der Teiltour v,w,v(Wähle sie som dass d_vw minimal ist) 
2. wähle den einzufügenden Knoten mit der minimalen distanz
3. berechne delta(j,p,q) = d_pj + d_jq - d_pq 
4. Einfügestelle: j hat beste Stelle, da wo delta(j,p,q) minimal ist

1. wähle 2 Knoten v und w und starte mit der Teiltour v,w,v(Wähle sie som dass d_vw minimal ist) 
2. wähle den einzufügenden Knoten mit der maximalen distanz
3. berechne delta(j,p,q) = d_pj + d_jq - d_pq 
4. Einfügestelle: j hat beste Stelle, da wo delta(j,p,q) minimal ist

1. wähle 2 Knoten v und w und starte mit der Teiltour v,w,v(Wähle sie som dass d_vw minimal ist) 
2. wähle den einzufügenden Knoten j, welcher die Länge der Tour am wenigsten erhöht  
3. berechne delta(j,p,q) = d_pj + d_jq - d_pq 
4. Einfügestelle: j hat beste Stelle, da wo delta(j,p,q) minimal ist

• die matrix ist symmetrisch 
• ich habe da eine 1, wo es zwischen zwei Knoten einen Weg gibt 

• Liegt ein Knoten nicht an einer Kante an, dann schreiben wir in die zugehörige Zelle, einfach eine 0 
• liegt ein Knoten an einer Kante, dann schreiben wird eine 1 in die Zelle 
• eignet sich vor allem für viele Knoten mit wenig Kanten 

Knotengrade: deg(1) = 3, deg(2) = 2, deg(6) = 1, deg(5) = 0 

hängender Knoten: G = {4,6,7}

isolierter Knoten: G = {5} 

Knotenmenge:

1. S{1,3,4} → delta(S) = {(1,2),(2,3)}, gamma(S) = {(1,3), (1,4)}
2. S{6,7} → delta(S) = Ø, gamma(S) = {(6,7)}

Ein ungerichteter Graph, ist ein Paar G = (V,E) wobei V eine endlich eMengen und E eine Menge von uneordneten Paaren von Elementen aus V ist. 

ein gerichteter Graph ist ein Paar G = (V,E) wobei V eine endliche Menge und E eine Menge von geordneten Paaren von Elementen aus V ist. 

Die Elemente von V werden als Knoten und die Elemente von E als die Bogen von G bezeichent. 

• es gibt da eine 1 wo es Kanten zwischen zwei Knoten hat
• die 1 setzt ich da von wo aus der Graph beginnt (also beim head) 

• eine -1 beim austritt aus einem Knoten
• eine 1 beim eintritt in eine Knoten 
• zeilen = Knoten
• Spalten = Kanten 

es wird zu jedem Teilmodell die zugehörige LP-Relaxion gelöst

Die Forderung der Ganzzahligkeit wird aufgehoben

wenn das primale problem eine optimale Lösung besitzt, so hat auch das duale Problem eine optimale lösung

The duality gap = 0, dual and primal problem are the same

das zugehörige dualproblem ist unzulässig, weil das P gegen unendlich geht und wenn man es kehren würde, würde das D gegen minus gehen, was nicht funktioniert.

the duality gap is >= 0

That means the solution to the dual (minimization) problem is always greater than or equal to the solution to an associated primal problem

1. maximierungsform * -1 rechnen
2. ungleichung zu Gleichungen umformen mittels Schlupf steht <= darf sofort eingefügt werden
3. wähle nichtbasisvariable mit dem kleinsten negativen koeffizienten in der Zielfunktionszeile
4. pivotzeile bestimmt sich durch die Berechnung aller Quotienten der Form rechte seize dividiert durch das entsprechende Element aus der Pivotspalte. (ignoriere alle Elemente in Pivotspalte = negativ oder null sind)
5. Wähle die Zeile mit dem kleinsten Quotienten Basisvariable dieser Zeile wird zur Nichtbasisvariablen
6. Pivotzeile so multiplizieren, das pivotelement = 1

Er sucht im Polyeder, nach der optimalen ganzzahligen Ecke

ist unzulässig, weil sich Ungleichungen widersprechen, z.B. x1 <= 1 und x1 >= 2.

In diesem Falle gibt es keine Lösung, welche alle Ungleichungen erfüllen würde, das zugehörige Polyeder ist die leere Menge

• Es wird nämlich immer die aktuell beste Entscheidung getroffen, ohne auf Vorherige oder auf Auswirkungen dieser Wahl zu achten.
• oft schnelle Lösung
• kann sein, dass aus diesem Grund nicht die optimale Lösung gefunden wird
• Kruskal oder dijkstra sind greedy algorithmen

es gibt unendlich viele zulässige Lösungen mit beliebig hohen Zielfunktionswerten (z. B. max { x | x ≥ 0 } ).

Ein steiner Baum entsteht wenn alle obligatorischen Knoten aus N und zusätzlich (muss nicht sein) die fakultativen Knoten, also die Steiner Knoten benutzt werden um jeden obligatorischen Knoten im Baum ohne Zyklen zu erreichen.

das Problem des minimalen Steiner Baums besteht darin, unter allen möglichen Steiner Bäumen von G, einen mit minimalem Gewicht zu finden.

Ein Schattenpreis einer Restriktion gibt an, wie viel sich der Zielfunktionswert ändert, wenn die Kapazität der entsprechenden Ressource um eine Einheit erhöht wird.

dann ist dessen D unzulässig, weil das P gegen unendlich geht und wenn man es kehrt, geht das D gegen minus unendlich, was nicht zulässig ist

ich weiss e=(v,w), Kante e verbindet Knoten v und w

Knotengerade deg(v) und deg(w), werden zweimal gezählt

siehe inzidenzmatrix , doppelt so viele Kanten wie Knoten

In jdem Graphen gibt es eine gerade Anzahl Knoten mit ungeradem Knotengrad → da Kanten immer zweimal gezählt werden, kann es gar nie eine ungerade Anzahl geben.

• im ungerichtetem/gerichtetem Graphen sucht er nach dem kürzesten Wegen von jedem Knoten i zu jedem Knoten j
• Zyklen sind erlaubt
• erkennt negative Zyklen
• für den längsten Weg, einfach Vorzeichen wechseln