4- Diskrete Optimierung Flashcards
Graphen
Ein Graph besteht aus einer Menge von Knoten und einer Menge von Kanten. Die Kanten verbinden stets 2 Knoten miteinander (die nicht unbedingt verschieden sind). Es kann Knoten ohne Verbindung geben.
Graphen - Kantenzug
Eine Folge aufeinanderstoßender Kanten (die nicht unbedingt verschieden sein müssen), die ohne abzusetzen gezeichnet werden kann. Eine Kante darf mehrfach durchlaufen werden.
Graphen - Weg
Ein spezieller Kantenzug ohne Kantenwiederholung
Graphen - vollständiger Graph
Jeder Knoten ist von jedem anderen Knoten direkt (über genau eine Kante) erreichbar.
Graphen - Durchmesser eines Graphen
Die Wege zwischen zwei Knoten sind höchstens X Kanten lang. Durchmesser = X.
Graphen - Baumgraphen
Die Länge des kürzesten Weges zwischen zwei Knoten ist direkt ablesbar. Baumartiges Erscheinungsbild
Graphen - Adjazenzmatrix
Graph mit n Knoten
-> (n,n)-Matrix (quadratisch und symmetrisch)
Wenn Knoten i mit j über eine Kante verbunden ist: aij=1, sonst 0
Graphen - isomorph
Zwei Graphen heißen isomorph, wenn man die Knoten beider Graphen so (um)benennen kann, dass die Adjazenzmatrizen beider Graphen gleich sind.
Graphen - Inzidenzmatrix
Graph mit n Knoten, m Kanten
-> (n,m)-Matrix
Wenn Knoten i mit j über eine Kante verbunden ist: aij=1, sonst 0
Graphen - Gradmatrix
Graph mit n Knoten
-> (n,n)- Diagonalmatrix
Trage den Grad eines Knotens ein: Anzahl der Kanten in diesem Knoten
Graphen - Zusammenhang zwischen Adjazenzmatrix, Gradmatrix und Inzidenzmatrix
A+G = I * I^T
Kürzeste Wege - Kreis
geschlossener Kantenzug,
d.h. Anfangsknoten = Endknoten
Kein Knoten wird doppelt durchlaufen
Kürzeste Wege - Breitensuche - Algo
Eingabe: Graph mit Knotennamen
Ausgabe: kürzeste Wege vom Startknoten zu allen anderen (erreichbaren) Knoten
1 - Startknoten wählen, markieren (O) und in Liste schreiben
2 - Ersten Knoten in der Liste streichen (aktiver Knoten), alle noch nicht markierten Nachbarn markieren und in Liste einstragen
3 - Liste leer? Wenn ja, beende. Wenn nein, gehe zu 2.
Bäume - Baumgraphen
Ein graph heißt zusammenhängend, wenn jeder Knoten mit einem anderen Knoten über einen Kantenzug verbunden ist. Besteht ein Graph aus nicht verbundenen Teilen, so heißen die Teile Zusammenhangskomponenten.
Bäume - Teilgraph
Beinhaltet alle Knoten und eine Teilmenge von Kanten
Bäume - aufspannender Baum
Ein aufspannender Baum eines zusammenhängenden Graphen ist ein Teilgraph, der kreisfrei und zusammenhängend ist und alle Knoten erreicht.
Bäume - Baum
zusammenhängender und kreisfreier Graph
Bäume - Baumgraphen - Eigenschaften
- Eindeutigkeit der Wege: Es gibt genau einen Weg von A nach B
- Anzahl der Kanten: bei n Knoten gibt es genau n-1 Kanten
Ein Baum ist minimal zusammenhängend und maximal kreisfrei
Bäume - Grad eines Knoten
Anzahl der Kantenenden in einem Knoten
Bäume - Blatt
Knoten mit Grad 1
Bäume - Anzahl aufspannender Bäume
In einem vollständigen Graphen mit n Knoten gibt es n^(n-2) aufspannende Bäume
Rundreiseproblem
Finde Rundreise, die jeden Knoten genau 1x besucht
-> vollständiger Graph
Rundreiseproblem - symmetrisches TSP
Entfernung A->B = B->A
Rundreiseproblem - asymmetrisches TSP
Kantengewicht A -> B != B -> A
Rundreiseproblem - Hamiltonkreis
geschlossener Kantenzug (= Kreis), der durch jeden Knoten genau einmal führt
Rundreiseproblem - Rechenaufwand
Bei n Knoten:
(n-1)! Rundreisen bei ATSP
(n-1)!/2 Rundreisen bei STSP
Rundreiseproblem - Greedy-TSP-Heuristik
wähle in jedem Schritt die bestmögliche Kante (min. Entfernung, ohne Hamiltonkreis zu verletzen)
Rundreiseproblem - Nächster Nachbar-Heuristik
Wähle Startknoten s und dann bestmögliche Nachbarn, ohne Hamiltonkreis zu verletzen
Rundreiseproblem - Doppelter-Nächster-Nachbar-Heuristik
Wähle Startknoten s und dann bestmögliche Nachbarn auf beiden Seiten ohne Hamiltonkreis zu verletzen.
Chinesisches Postbotenproblem
Finde möglichst kurze Rundtour in einem zusammenhängenden gewichteten Graphen, die jede Kante mindestens einmal besucht. Optimal: jede Kante GENAU einmal besuchen
Chinesisches Postbotenproblem - Eulerweg
Weg (Am Stück gezeichneter Kantenzug ohne Knotenwiederholung), bei dem jede Kante genau einmal durchlaufen wird
Chinesisches Postbotenproblem - Eulertour
Rundweg, der Eulerweg ist.
-> geschlossender Eulerweg mit Startpunkt = Endpunkt
Chinesisches Postbotenproblem - Eulergraph
Graph, der Eulertour enthält
Ein Graph ist ein Eulergraph genau dann, wenn alle Knoten einen geraden Grad haben
