Greedy Algorithmus, Dijkstra Algorithmus, Inzidenz- und Adjazenzmatrix Flashcards
Wahr oder falsch?
Für ungerichtete Graphen ist die Adjazenzmatrix asymmetrisch.
Falsch!
Für ungerichtete Graphen ist die Adjazenzmatrix symmetrisch (Achtung! Gilt andersherum nicht!)
Wahr oder falsch?
Für ungerichtete Graphen kann die Inzidenzmatrix folgende Elemente enthalten: -1, 0, 1
Falsch!
Für gerichtete Graphen kann die Inzidenzmatrix folgende Elemente enthalten: -1, 0, 1
Das Element -1 gibt es nur bei gerichteten Graphen.
Wie funktioniert der Greedy Algorithmus?
Der Greedy Algorithmus wählt immer die “billigste Kante” ohne dabei Rücksicht auf Folgekanten zu nehmen.
Wahr oder falsch?
Der Greedy Algorithmus findet nicht immer eine zulässige bzw. die optimale Lösung.
Wahr!
Was liefert der Dijkstra Algorithmus?
Der Dijkstra Algorithmus findet immer den kürzesten Weg von einem Startknoten zu allen anderen Knoten.
Nenne die Voraussetzungen für den Dijkstra Algorithmus.
Keine negativen Kantengewichte
Wahr oder falsch?
Hat ein Graph n Konten und m Kanten, so ist die Adjazenzmatrix eine [n x m]-Matrix.
Falsch!
Hat ein Graph n Konten und m Kanten, so ist die Adjazenzmatrix eine [n x n]-Matrix.
Wie lässt sich bei einer Adjazenzmatrix erkennen, ob ein Graph Schlingen enthält?
Diagonaleintrag = 0 –> Keine Schlinge
Diagonaleintrag = 1 –> Schlinge
Wie lässt sich in einer Adjazenzmatrix erkennen ob ein Knoten Quelle/Senke ist?
Alle Spalteneinträge der i-ten Spalte = 0 –> i ist eine Quelle
Alle Zeileneinträge der i-ten Zeile = 0 –> i ist eine Senke
Wahr oder falsch?
Die Ableserichtung ist sowohl bei der Adjazenz- als auch bei der Inzidenzmatrix nicht definiert.
Wahr!
Die Ableserichtung ist eine Konvention.
Wahr oder falsch?
Hat ein Graph n Konten und m Kanten, so ist die Inzidenzmatrix eine [n x m]-Matrix.
Wahr!
Wahr oder falsch?
In der Inzidenzmatrix kann eine Schlinge sowohl mit 1 als auch mit -1 eingetragen werden.
Wahr!
Wahr oder falsch?
Bei einem gerichteten Graphen ohne Schlingen ist in der Inzidenzmatrix die Summe der Spalteneinträge jeweils 1..
Falsch!
Bei einem gerichteten Graphen ohne Schlingen ist in der Inzidenzmatrix die Summe der Spalteneinträge jeweils 0.
Wahr oder falsch?
Bei einem mit dem Dijkstra Algorithmus gefundenen kürzesten Weg sind alle Teilwege des gefundenen Weges ebenfalls optimal.
Wahr!
Teilwege von kürzesten Wegen sind selbst kürzeste Wege (Prinzip der optimalen Substruktur).
Bsp. Dijkstra Algorithmus
Kürzester Weg von a –> d:
a –> e –> j –> f –> g –> d
Kürzester Weg von f –> d:
f –> g –> d
Wie muss man beim Dijkstra-Algorithmus vorgehen, wenn man einen Weg haben will, der alle Wege mit kleineren Gewichten enthalten soll, d. h. das maximale Gewicht jedes benutzten Teilwegs minimiert?
Neugewichtung der Kanten
1 == 100^0
2 == 100^1
…
vgl. Aufgabenkatalog, Nr. 3.7 b), Nr. 3.8
