Ein Graph modelliert vernetzte Strukturen als Knoten und Kanten — Straßennetze, soziale Netzwerke, Verbindungspläne, wahlweise gerichtet und gewichtet; im Rechner gespeichert als Adjazenzmatrix oder Adjazenzliste. Auf ihm arbeiten die klassischen Verfahren: kürzeste Wege mit Dijkstra (Vorgänger-Tabelle), Durchlauf in die Breite mit einer Schlange und in die Tiefe mit einem Stapel. Die Modellierungs-Einsicht: Erst die Abstraktion aufs Wesentliche — Was ist ein Knoten? Was ist eine Kante? — macht so verschiedene Netze mit denselben Algorithmen behandelbar.
Aus welchen zwei Grundelementen besteht ein Graph?
○ Tabellen und Spalten
● Knoten (Vertices) und Kanten (Edges)
○ Wurzel und Blaetter
○ Schluessel und Werte
Ein Graph G = (V, E) besteht aus einer Menge von Knoten V (Vertices) und einer Menge von Kanten E (Edges). Kanten verbinden jeweils zwei Knoten miteinander.
In einem ungerichteten Graphen hat jede Kante eine festgelegte Richtung.
✓ Falsch
Falsch. In einem ungerichteten Graphen sind Kanten bidirektional: Die Kante {A, B} kann in beide Richtungen durchlaufen werden. In einem gerichteten Graphen (Digraph) hingegen hat jede Kante eine Richtung: (A, B) ist nicht gleich (B, A).
Die Anzahl der Kanten, die an einem Knoten anliegen, heisst der ___ des Knotens.
✓ Antwort: Grad
Der Grad (degree) eines Knotens zaehlt seine Kanten. In einem ungerichteten Graphen gilt: Die Summe aller Knotengrade ist doppelt so gross wie die Anzahl der Kanten (Handschlaglemma).
Welche Darstellung beschreibt einen gewichteten Graphen?
○ Knoten A(4), B(7), C(9); Kanten A–B, B–C, A–C
○ Kanten A→B, B→C, C→A
● Kanten A–B: 4 km, B–C: 7 km, A–C: 9 km
In einem gewichteten Graphen trägt jede Kante einen Zahlenwert (Entfernung, Kosten, Zeit) – wichtig für Kürzeste-Wege-Algorithmen wie Dijkstra. Zahlen an den Knoten machen den Graphen nicht kantengewichtet, und Pfeile machen ihn gerichtet, nicht gewichtet.
Ein Graph ohne Zyklen heisst ___. Ein zusammenhaengender azyklischer Graph ist ein Baum.
✓ Antwort: azyklisch
Ein Zyklus ist ein Pfad, der zum Ausgangsknoten zurueckfuehrt. Ein azyklischer Graph (ohne Zyklen), der zusammenhaengend ist, wird als Baum bezeichnet. Ein gerichteter azyklischer Graph heisst DAG.
Ein vollstaendiger ungerichteter Graph hat 5 Knoten. Wie viele Kanten hat er?
✓ Antwort: 10
In einem vollstaendigen Graphen ist jeder Knoten mit jedem anderen verbunden. Die Anzahl der Kanten ist n*(n-1)/2 = 5*4/2 = 10. Jedes Knotenpaar ist durch genau eine Kante verbunden.
Wie kann ein Graph im Computer gespeichert werden?
○ Nur als Bild
● Als Adjazenzmatrix oder Adjazenzliste
○ Nur als sortiertes Array
○ Als Binaerbaum
Adjazenzmatrix: Eine n x n Matrix, wobei der Eintrag [i][j] angibt, ob eine Kante zwischen Knoten i und j existiert. Adjazenzliste: Fuer jeden Knoten eine Liste seiner Nachbarn. Adjazenzlisten sind speichereffizienter bei duennen Graphen.
In sozialen Netzwerken werden Personen als ___ und Freundschaften als Kanten modelliert.
✓ Antwort: Knoten
Soziale Netzwerke sind ein klassisches Anwendungsbeispiel fuer Graphen. Jede Person ist ein Knoten, jede Freundschaft/Verbindung eine Kante. Metriken wie Zentralitaet oder Cliquenbildung lassen sich mit Graphenalgorithmen analysieren.
Ordne die Schritte des Dijkstra-Algorithmus in die richtige Reihenfolge:
✓ Antwort: Startknoten mit Distanz 0 initialisieren, alle anderen mit unendlich, Knoten mit kleinster Distanz auswaehlen (noch nicht besucht), Distanzen aller Nachbarn aktualisieren (Relaxation), Knoten als besucht markieren, Wiederholen, bis alle Knoten besucht sind oder Ziel erreicht
Dijkstra findet den kuerzesten Weg vom Startknoten zu allen anderen. Er arbeitet gierig: In jedem Schritt wird der naechstgelegene noch nicht besuchte Knoten bearbeitet. Voraussetzung: keine negativen Kantengewichte.
Der Dijkstra-Algorithmus funktioniert korrekt, auch wenn der Graph negative Kantengewichte enthaelt.
✓ Falsch
Falsch. Dijkstra setzt voraus, dass alle Kantengewichte nicht-negativ sind. Bei negativen Gewichten kann er falsche Ergebnisse liefern. Fuer Graphen mit negativen Gewichten verwendet man den Bellman-Ford-Algorithmus.
Bei der ___ (BFS) werden Knoten ebenenweise besucht: zuerst alle Nachbarn, dann deren Nachbarn usw.
✓ Antwort: Breitensuche
Die Breitensuche (Breadth-First Search, BFS) verwendet eine Warteschlange. Sie besucht alle Knoten in der Reihenfolge ihrer Entfernung (Anzahl Kanten) zum Startknoten. BFS findet den kuerzesten Weg in ungewichteten Graphen.
In einem ungerichteten Graphen mit 6 Knoten hat jeder Knoten den Grad 2. Wie viele Kanten hat der Graph?
✓ Antwort: 6
Nach dem Handschlaglemma: Summe aller Grade = 2 * Anzahl Kanten. Summe aller Grade = 6 * 2 = 12. Also: Anzahl Kanten = 12 / 2 = 6. Der Graph bildet einen Zyklus durch alle 6 Knoten.
Jede Erweiterung fuegt Informationen hinzu: Richtung (gerichtet) und Gewichte. Ein gewichteter Digraph ist die allgemeinste Form und kann alle anderen als Spezialfall darstellen.
Die Adjazenzmatrix eines ungerichteten Graphen ist immer symmetrisch.
✓ Wahr
Richtig. Wenn Knoten i mit Knoten j verbunden ist, dann auch j mit i. Daher gilt: Matrix[i][j] = Matrix[j][i]. Bei gerichteten Graphen ist die Matrix im Allgemeinen nicht symmetrisch.
Was versteht man unter einem zusammenhaengenden Graphen?
○ Ein Graph, bei dem alle Knoten denselben Grad haben
● Ein Graph, bei dem es zwischen jedem Knotenpaar mindestens einen Pfad gibt
○ Ein Graph ohne Kanten
○ Ein Graph mit genau einem Zyklus
Ein zusammenhaengender Graph hat keine isolierten Teile. Von jedem Knoten aus kann man jeden anderen Knoten erreichen. Ein nicht-zusammenhaengender Graph besteht aus mehreren Zusammenhangskomponenten.
Ein Baum mit n Knoten hat immer genau n-1 Kanten. Das ist eine grundlegende Eigenschaft: Ein Baum ist ein zusammenhaengender, azyklischer Graph, und das Entfernen einer Kante wuerde ihn in zwei Teile trennen.
Ordne die Schritte der Breitensuche (BFS) ab einem Startknoten s in die richtige Reihenfolge:
✓ Antwort: Startknoten s in die Warteschlange einfuegen und als besucht markieren, Vordersten Knoten aus der Warteschlange entnehmen, Alle unbesuchten Nachbarn in die Warteschlange einfuegen und als besucht markieren, Schritte wiederholen, bis die Warteschlange leer ist
BFS nutzt eine Queue (FIFO). Sie besucht Knoten in aufsteigender Entfernung zum Start. BFS findet den kuerzesten Pfad in ungewichteten Graphen und prueft den Zusammenhang.
Der Algorithmus von ___ berechnet die kuerzesten Wege von einem Startknoten zu allen anderen Knoten in einem gewichteten Graphen ohne negative Kantengewichte.
✓ Antwort: Dijkstra
Der Dijkstra-Algorithmus (1959, Edsger W. Dijkstra) ist ein Greedy-Algorithmus. Er waehlt in jedem Schritt den Knoten mit der kleinsten bekannten Distanz und aktualisiert die Distanzen seiner Nachbarn.
Welche Eigenschaft hat ein Eulerkreis in einem Graphen?
○ Er besucht jeden Knoten genau einmal
● Er durchlaeuft jede Kante genau einmal und kehrt zum Startknoten zurueck
○ Er ist der kuerzeste Weg zwischen zwei Knoten
○ Er enthaelt keine Zyklen
Ein Eulerkreis existiert genau dann, wenn der Graph zusammenhaengend ist und alle Knoten einen geraden Grad haben. Das geht zurueck auf das Koenigsberger Brueckenproblem von Euler (1736).