4- Diskrete Optimierung

Question 1

Graphen

Answer 1

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.

Question 2

Graphen - Kantenzug

Answer 2

Eine Folge aufeinanderstoßender Kanten (die nicht unbedingt verschieden sein müssen), die ohne abzusetzen gezeichnet werden kann. Eine Kante darf mehrfach durchlaufen werden.

Question 3

Graphen - Weg

Answer 3

Ein spezieller Kantenzug ohne Kantenwiederholung

Question 4

Graphen - vollständiger Graph

Answer 4

Jeder Knoten ist von jedem anderen Knoten direkt (über genau eine Kante) erreichbar.

Question 5

Graphen - Durchmesser eines Graphen

Answer 5

Die Wege zwischen zwei Knoten sind höchstens X Kanten lang. Durchmesser = X.

Question 6

Graphen - Baumgraphen

Answer 6

Die Länge des kürzesten Weges zwischen zwei Knoten ist direkt ablesbar. Baumartiges Erscheinungsbild

Question 7

Graphen - Adjazenzmatrix

Answer 7

Graph mit n Knoten
-> (n,n)-Matrix (quadratisch und symmetrisch)
Wenn Knoten i mit j über eine Kante verbunden ist: aij=1, sonst 0

Question 8

Graphen - isomorph

Answer 8

Zwei Graphen heißen isomorph, wenn man die Knoten beider Graphen so (um)benennen kann, dass die Adjazenzmatrizen beider Graphen gleich sind.

Question 9

Graphen - Inzidenzmatrix

Answer 9

Graph mit n Knoten, m Kanten
-> (n,m)-Matrix
Wenn Knoten i mit j über eine Kante verbunden ist: aij=1, sonst 0

Question 10

Graphen - Gradmatrix

Answer 10

Graph mit n Knoten
-> (n,n)- Diagonalmatrix
Trage den Grad eines Knotens ein: Anzahl der Kanten in diesem Knoten

Question 11

Graphen - Zusammenhang zwischen Adjazenzmatrix, Gradmatrix und Inzidenzmatrix

Answer 11

A+G = I * I^T

Question 12

Kürzeste Wege - Kreis

Answer 12

geschlossener Kantenzug,
d.h. Anfangsknoten = Endknoten

Kein Knoten wird doppelt durchlaufen

Question 13

Kürzeste Wege - Breitensuche - Algo

Answer 13

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.

Question 14

Bäume - Baumgraphen

Answer 14

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.

Question 15

Bäume - Teilgraph

Answer 15

Beinhaltet alle Knoten und eine Teilmenge von Kanten

Question 16

Bäume - aufspannender Baum

Answer 16

Ein aufspannender Baum eines zusammenhängenden Graphen ist ein Teilgraph, der kreisfrei und zusammenhängend ist und alle Knoten erreicht.

Question 17

Bäume - Baum

Answer 17

zusammenhängender und kreisfreier Graph

Question 18

Bäume - Baumgraphen - Eigenschaften

Answer 18

1. Eindeutigkeit der Wege: Es gibt genau einen Weg von A nach B
2. Anzahl der Kanten: bei n Knoten gibt es genau n-1 Kanten

Ein Baum ist minimal zusammenhängend und maximal kreisfrei

Question 19

Bäume - Grad eines Knoten

Answer 19

Anzahl der Kantenenden in einem Knoten

Question 20

Bäume - Blatt

Answer 20

Knoten mit Grad 1

Question 21

Bäume - Anzahl aufspannender Bäume

Answer 21

In einem vollständigen Graphen mit n Knoten gibt es n^(n-2) aufspannende Bäume

Question 22

Rundreiseproblem

Answer 22

Finde Rundreise, die jeden Knoten genau 1x besucht

-> vollständiger Graph

Question 23

Rundreiseproblem - symmetrisches TSP

Answer 23

Entfernung A->B = B->A

Question 24

Rundreiseproblem - asymmetrisches TSP

Answer 24

Kantengewicht A -> B != B -> A

Question 25

Rundreiseproblem - Hamiltonkreis

Answer 25

geschlossener Kantenzug (= Kreis), der durch jeden Knoten genau einmal führt

Question 26

Rundreiseproblem - Rechenaufwand

Answer 26

Bei n Knoten:

(n-1)! Rundreisen bei ATSP
(n-1)!/2 Rundreisen bei STSP

Question 27

Rundreiseproblem - Greedy-TSP-Heuristik

Answer 27

wähle in jedem Schritt die bestmögliche Kante (min. Entfernung, ohne Hamiltonkreis zu verletzen)

Question 28

Rundreiseproblem - Nächster Nachbar-Heuristik

Answer 28

Wähle Startknoten s und dann bestmögliche Nachbarn, ohne Hamiltonkreis zu verletzen

Question 29

Rundreiseproblem - Doppelter-Nächster-Nachbar-Heuristik

Answer 29

Wähle Startknoten s und dann bestmögliche Nachbarn auf beiden Seiten ohne Hamiltonkreis zu verletzen.

Question 30

Chinesisches Postbotenproblem

Answer 30

Finde möglichst kurze Rundtour in einem zusammenhängenden gewichteten Graphen, die jede Kante mindestens einmal besucht. Optimal: jede Kante GENAU einmal besuchen

Question 31

Chinesisches Postbotenproblem - Eulerweg

Answer 31

Weg (Am Stück gezeichneter Kantenzug ohne Knotenwiederholung), bei dem jede Kante genau einmal durchlaufen wird

Question 32

Chinesisches Postbotenproblem - Eulertour

Answer 32

Rundweg, der Eulerweg ist.

-> geschlossender Eulerweg mit Startpunkt = Endpunkt

Question 33

Chinesisches Postbotenproblem - Eulergraph

Answer 33

Graph, der Eulertour enthält

Ein Graph ist ein Eulergraph genau dann, wenn alle Knoten einen geraden Grad haben