Graphen und Netzwerke
Aus welchen zwei Grundelementen besteht ein Graph?
Erklärung: 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.
Erklärung: 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.
Erklärung: 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?
Erklärung: 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.
Erklärung: 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?
Erklärung: 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?
Erklärung: 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.
Ordne die Schritte des Dijkstra-Algorithmus in die richtige Reihenfolge:
Erklärung: 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.
Erklärung: 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.
Erklärung: 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.
Welches reale Szenario laesst sich gut als Graph modellieren?
Erklärung: Kreuzungen sind Knoten, Strassen sind Kanten. Einbahnstrassen ergeben gerichtete Kanten, Entfernungen oder Fahrzeiten ergeben Gewichte. Navigationssysteme nutzen Graphenalgorithmen fuer die Routenplanung.
In einem ungerichteten Graphen mit 6 Knoten hat jeder Knoten den Grad 2. Wie viele Kanten hat der Graph?
Erklärung: 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.
Ordne die folgenden Graphentypen vom einfachsten zum komplexesten:
Erklärung: Jede Erweiterung fuegt Informationen hinzu: Richtung (gerichtet) und Gewichte. Ein gewichteter Digraph ist die allgemeinste Form und kann alle anderen als Spezialfall darstellen.
In sozialen Netzwerken werden Personen als ___ und Freundschaften als Kanten modelliert.
Erklärung: 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.
Die Adjazenzmatrix eines ungerichteten Graphen ist immer symmetrisch.
Erklärung: 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?
Erklärung: 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 10 Knoten hat wie viele Kanten?
Erklärung: 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:
Erklärung: 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.
Erklärung: 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?
Erklärung: 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).