Introduction to Network Science - Exam

Aufgabe 1)

Nehmen wir an, Du untersuchst ein Netzwerk, das sowohl Elemente von regulären Netzwerken als auch von zufälligen Netzwerken aufweist. Es besteht aus 100 Knoten und hat eine mittlere Kantenanzahl pro Knoten (\bar{k}) von 10. Untersuche die Struktur und Eigenschaften dieses Netzwerks.

a)

Vergleiche die erwartete Länge eines typischen kürzesten Pfads in einem regulären Netzwerk mit dem Theorie-Modell eines Zufallsnetzwerks (Erdős-Rényi Modell) mit derselben Anzahl von Knoten (N = 100) und der gleichen mittleren Kantenanzahl pro Knoten (\bar{k} = 10). Berechne die durchschnittliche Pfadlänge in beiden Fällen mittels der entsprechenden Formeln.

Lösung:

Um die durchschnittliche Pfadlänge in beiden Netzwerken zu berechnen, gehen wir wie folgt vor:

• Reguläres Netzwerk: In einem regulären Netzwerk sind die Knoten gleichmäßig verbunden, d.h., jeder Knoten ist mit genau \(\bar{k}\) anderen Knoten verbunden. Für ein Netzwerk dieser Art mit \(N = 100\) Knoten und einer mittleren Kantenanzahl pro Knoten von 10, kann die berechnete durchschnittliche Pfadlänge durch Simulationen ermittelt werden. Eine Vereinfachung liefert die folgende Näherung:
• Formel für die kürzeste Pfadlänge (L) im regulären Netzwerk: \[ L \thickapprox \frac{N}{2\bar{k}} \]
• Setze die gegebenen Werte ein: \[ L = \frac{100}{2 \times 10} = 5 \]
• Die durchschnittliche Pfadlänge in einem regulären Netzwerk beträgt daher etwa 5.
• Zufallsnetzwerk (Erdős-Rényi Modell): Im Erdős-Rényi Modell (Zufallsnetzwerk) mit \(N = 100\) Knoten und einer mittleren Kantenanzahl pro Knoten von \(\bar{k} = 10\), wird die durchschnittliche Pfadlänge (L) durch die folgende Formel approximiert:
• Formel für die durchschnittliche Pfadlänge (L) im Erdős-Rényi Modell: \[ L \thickapprox \frac{\text{ln}(N)}{\text{ln}(\bar{k})} \]
• Setze die gegebenen Parameter ein: \[ L = \frac{\text{ln}(100)}{\text{ln}(10)} \]
• Da \(\text{ln}(100) \thickapprox 4.61\) und \(\text{ln}(10) \thickapprox 2.30\), erhalten wir: \[ L \thickapprox \frac{4.61}{2.30} \thickapprox 2 \]
• Die durchschnittliche Pfadlänge in einem Zufallsnetzwerk der Größe 100 und \(\bar{k} = 10\) beträgt daher etwa 2.

Zusammenfassend lässt sich feststellen, dass die durchschnittliche Pfadlänge in einem regulären Netzwerk mit \(\text{N} = 100\) und \(\bar{k} = 10\) etwa 5 beträgt, während sie in einem zufälligen Netz vom Typ Erdős-Rényi mit denselben Parametern etwa 2 beträgt. Dies verdeutlicht, dass Zufallsnetzwerke im Allgemeinen kürzere Pfade zwischen den Knoten aufweisen als reguläre Netzwerke.

b)

Analysiere, ob das gegebene Netzwerk eher Eigenschaften eines Kleinwelt-Netzwerks (Watts-Strogatz Modell) aufweisen könnte. Begründe Deine Antwort, indem Du die Strukturmerkmale wie Clustering-Koeffizient und Pfadlänge vergleichst.

Lösung:

Um zu analysieren, ob das gegebene Netzwerk Eigenschaften eines Kleinwelt-Netzwerks (Watts-Strogatz Modell) aufweisen könnte, betrachten wir zwei Hauptstrukturmerkmale: den Clustering-Koeffizienten und die durchschnittliche Pfadlänge.

• Clustering-Koeffizient:
  • Der Clustering-Koeffizient misst, wie eng beieinanderliegende Knoten in einem Netzwerk miteinander verbunden sind. In einem Kleinwelt-Netzwerk ist dieser typischerweise hoch, da Clusterbildung eine starke Rolle spielt.
  • Ein reguläres Netzwerk hat einen hohen Clustering-Koeffizienten, da die Knoten gleichmäßig und in einer regelmäßigen Struktur verbunden sind.
  • Ein Erdős-Rényi Zufallsnetzwerk hat jedoch einen niedrigen Clustering-Koeffizienten, da die Verbindungen zufällig und nicht klumpenartig sind.
  • Das gegebene Netzwerk hat einen mittleren Clustering-Koeffizienten, da es Elemente sowohl eines regulären als auch eines zufälligen Netzwerks aufweist. Dies spricht schon für ein Kleinwelt-Netzwerk, welches durch Rekonfiguration eines regulären Netzwerks mit einer gewissen Wahrscheinlichkeit für zufällige Verbindungen erzeugt wird.
• Durchschnittliche Pfadlänge:
  • Ein Kleinwelt-Netzwerk zeichnet sich durch eine geringe durchschnittliche Pfadlänge aus, ähnlich einem Zufallsnetzwerk, obwohl es einen hohen Clustering-Koeffizienten behält.
  • Ein reguläres Netzwerk hat eine relativ hohe durchschnittliche Pfadlänge, wie bereits berechnet, beträgt diese ca. 5.
  • Ein Erdős-Rényi Zufallsnetzwerk hat eine geringe durchschnittliche Pfadlänge, die in unserem Fall ca. 2 beträgt.
  • Da das Netzwerk sowohl Elemente von regulären als auch zufälligen Netzwerken aufweist, könnte die durchschnittliche Pfadlänge zwischen diesen beiden Extremen liegen, was einem Kleinwelt-Netzwerk entspricht.

Zusammengefasst: Das Netzwerk hat eine mittlere Kantenanzahl von 10 und besteht aus 100 Knoten. Es weist Eigenschaften sowohl von regulären Netzwerken (hoher Clustering-Koeffizient) als auch von zufälligen Netzwerken (geringe durchschnittliche Pfadlänge) auf. Diese Kombination von hochgradiger Clusterbildung und kurzer durchschnittlicher Pfadlänge ist charakteristisch für Kleinwelt-Netzwerke gemäß dem Watts-Strogatz Modell. Es ist daher wahrscheinlich, dass das gegebene Netzwerk die Eigenschaften eines Kleinwelt-Netzwerks aufweist.

c)

Betrachte, ob das untersuchte Netzwerk Merkmale eines skalierbaren Netzwerks (Barabási-Albert Modell) aufweist. Beschreibe die Verteilung der Knotengrade und untersuche, ob eine Power-law Verteilung vorliegt.

Lösung:

Um zu untersuchen, ob das gegebene Netzwerk Merkmale eines skalierbaren Netzwerks (Barabási-Albert Modell) aufweist, müssen wir die Verteilung der Knotengrade analysieren und prüfen, ob diese eine Power-law Verteilung folgt. Das Barabási-Albert Modell beschreibt Netzwerke, die durch das Wachstum und die Bevorzugung von Verbindungen entstehen und eine charakteristische Skalierbarkeit aufweisen.

• Knotengrad-Verteilung:
  • In einem skalierbaren Netzwerk, wie es das Barabási-Albert Modell beschreibt, folgt die Verteilung der Knotengrade einer Power-law Verteilung. Dies bedeutet, dass wenige Knoten (Hubs) eine sehr hohe Anzahl von Verbindungen haben, während die meisten Knoten nur wenige Verbindungen haben.
  • Mathematisch kann die Power-law Verteilung durch die Formel ausgedrückt werden: \( P(k) \sim k^{-\gamma} \) wobei \( P(k) \) die Wahrscheinlichkeit ist, dass ein Knoten \( k \) Verbindungen hat, und \( \gamma \) ein Exponent ist (typischerweise zwischen 2 und 3).
• Analyse der Verteilung:
  • Um zu überprüfen, ob das Netzwerk eine Power-law Verteilung der Knotengrade aufweist, müssen wir die Grade aller Knoten im Netzwerk untersuchen und deren Verteilung plotten (z.B. auf einem log-log Plot).
  • Ein log-log Plot der Knotengrade sollte linear sein, wenn die Verteilung einer Power-law folgt.
  • Da das Netzwerk sowohl reguläre als auch zufällige Elemente enthält und eine mittlere Kantenanzahl pro Knoten von 10 aufweist, müssen wir die tatsächlichen Daten analysieren. Wir würden die Knotengrade für alle 100 Knoten zählen und diese in einem Histogramm darstellen. Wenn das Histogramm auf log-log Achsen eine gerade Linie bildet, liegt eine Power-law Verteilung vor.
• Schritte zur Überprüfung der Power-law Verteilung:
  • Zähle die Verbindungen (Kanten) jedes Knotens im Netzwerk.
  • Erstelle ein Histogramm der Knotengrade.
  • Plotte das Histogramm auf log-log Achsen.
  • Überprüfe, ob der Plot linear ist, was auf eine Power-law Verteilung hinweist.

Basierend auf der gegebenen Netzwerkbeschreibung haben wir keine spezifischen Knotengrad-Daten. Um jedoch festzustellen, ob das Netzwerk Merkmale eines skalierbaren Netzwerks aufweist, müssten wir die oben genannten Schritte zur Knotengrad-Zählung und Analyse durchführen. Sollten sich die Daten als linear auf einem log-log Plot erweisen, würde dies bestätigen, dass das Netzwerk eine Power-law Verteilung aufweist und somit die Merkmale eines Barabási-Albert Netzwerks besitzt.

d)

Modelliere das Netzwerk als hierarchisches Netzwerk und beschreibe, wie sich die Trennbarkeit und die Organisationsebenen auf die Gesamteffizienz des Netzwerks auswirken könnten. Analysiere, welche Rolle Ebenen und Hierarchien in der Struktur spielen könnten, um bestimmte Eigenschaften oder Dynamiken zu erklären.

Lösung:

Um das Netzwerk als hierarchisches Netzwerk zu modellieren und die Auswirkungen auf die Gesamteffizienz sowie die Rolle der Ebenen und Hierarchien zu analysieren, betrachten wir folgende Aspekte:

• Hierarchische Struktur:
  • Ein hierarchisches Netzwerk ist durch eine verschachtelte Struktur von Knoten und Verbindungen charakterisiert. Knoten sind in verschiedenen Ebenen organisiert, wobei jede Ebene Verbindungen innerhalb der Ebene sowie Verbindungen zu übergeordneten und untergeordneten Ebenen aufweist.
  • In einem hierarchischen Netzwerk gibt es wenige zentrale Hubs, die viele Verbindungen zu Knoten in niedrigeren Ebenen haben, und viele Knoten mit wenigen Verbindungen innerhalb derselben Ebene.
• Trennbarkeit und Organisationsebenen:
  • Die Trennbarkeit bezieht sich auf die Fähigkeit, das Netzwerk in unabhängige Subnetze oder Module zu zerlegen. Ein höherer Grad der Trennbarkeit kann die Modularität und Fehlertoleranz des Netzwerks verbessern, jedoch auf Kosten der Gesamteffizienz in Bezug auf Kommunikationswege.
  • Organisationsebenen definieren die Hierarchie und helfen dabei, die Komplexität zu managen. Höhere Ebenen sind oft weniger vernetzt, aber entscheidend für die globale Koordination und Kontrolle des Netzwerks.
  • Ein hierarchisches Netzwerk mit guter Organisation kann durch die Identifizierung und Trennung von Subnetzen (jeweils als Modul oder Cluster) die Effizienz verbessern, indem die Last besser verteilt und die Kommunikation zwischen den Knoten beschleunigt wird.
• Auswirkungen auf die Gesamteffizienz:
  • Ein gut organisiertes hierarchisches Netzwerk kann die Effizienz steigern, indem es kurze Kommunikationspfade innerhalb von Modulen nutzt und zentrale Hubs zur Optimierung globaler Kommunikation verwendet.
  • Die Ebenen und Hierarchien ermöglichen eine bessere Fehlertoleranz: Wenn ein Knoten innerhalb eines Moduls ausfällt, wird die Auswirkung lokalisiert und betrifft nicht die gesamte Netzwerkstruktur. Ebenso können zentrale Hubs Ausfallreserven bereitstellen.
  • Die Modularität und Ebenenstruktur können auch Skalierbarkeit unterstützen, da neue Module leicht hinzugefügt werden können, ohne die gesamte Netzwerkarchitektur drastisch zu verändern.
• Beispiele für Dynamiken und Eigenschaften:
  • In einem sozialen Netzwerk könnte eine hierarchische Struktur bedeuten, dass es ein zentrales Netzwerk von „Influencern“ gibt, die die globale Kommunikation erleichtern, während kleine Communitys innerhalb der Module intensiver interagieren.
  • In einem Unternehmensnetzwerk könnten Hierarchien und Module die Organisation von Abteilungen und Teams widerspiegeln, mit zentralen Managementknoten, die die Verbindungen zwischen den Abteilungen koordinieren.
  • Für ein technisches Netzwerk (z.B. Kommunikations- oder Computernetzwerk) könnten Hierarchien bedeuten, dass lokale Server Cluster bedienen, während zentrale Server für das übergreifende Routing und die Datenverteilung verantwortlich sind.

Zusammengefasst bietet die hierarchische Struktur viele Vorteile für die Effizienz und Fehlertoleranz eines Netzwerks. Indem man Ebenen und Hierarchien zur Organisation nutzt, kann man die Gesamteffizienz erhöhen, die Flexibilität und Fehlertoleranz verbessern und die Skalierbarkeit des Netzwerks unterstützen. In Deinem spezifischen Fall, welches sowohl reguläre als auch zufällige Elemente enthält, könnte die Einführung einer hierarchischen Struktur dazu beitragen, die Effizienz in der Kommunikation und die Robustheit des Netzwerks zu stärken.

Aufgabe 2)

In einem sozialen Netzwerk werden Personen durch Knoten und deren Freundschaften durch Kanten repräsentiert. Angenommen, Du hast ein Netzwerk von fünf Personen (A, B, C, D, E), wobei folgende Beziehungen bestehen:

• A und B sind Freunde.
• B und C sind Freunde.
• C und D sind Freunde.
• D und E sind Freunde.
• E und A sind Freunde.

Die Adjazenzmatrix für dieses Netzwerk ist:

0 1 0 0 11 0 1 0 00 1 0 1 00 0 1 0 11 0 0 1 0

a)

Erstelle den entsprechenden Graphen (zeichne das Netzwerk) und identifiziere dessen Eigenschaften wie Anzahl der Knoten, Anzahl der Kanten und ob es sich um einen zusammenhängenden Graphen handelt.

Lösung:

Lass uns den gegebenen Graphen analysieren und seine Eigenschaften identifizieren.

Schritte zur Lösung:

• Visualisiere den Graphen basierend auf der gegebenen Adjazenzmatrix.
• Bestimme die Anzahl der Knoten.
• Zähle die Anzahl der Kanten.
• Überprüfe, ob der Graph zusammenhängend ist.

Schritt 1: Visualisierung des Graphen

Basierend auf den gegebenen Freundschaften können wir den Graphen wie folgt zeichnen:

Die Knoten A, B, C, D und E sind miteinander verbunden entsprechend den Freundschaften.

Schritt 2: Anzahl der Knoten

Die Anzahl der Knoten ist gleich der Anzahl der Personen im Netzwerk. Es gibt fünf Personen (A, B, C, D, E).

• Anzahl der Knoten: 5

Schritt 3: Anzahl der Kanten

Die Kanten im Graphen sind die Verbindungen zwischen den Freunden:

• A-B
• B-C
• C-D
• D-E
• E-A

Somit gibt es insgesamt fünf Kanten.

• Anzahl der Kanten: 5

Schritt 4: Überprüfen, ob der Graph zusammenhängend ist

Ein Graph gilt als zusammenhängend, wenn es einen Pfad zwischen jedem Paar von Knoten gibt. In diesem Fall ist es offensichtlich, dass jeder Knoten mit mindestens einem anderen Knoten verbunden ist und man von jedem Knoten zu jedem anderen Knoten gelangen kann (z.B. A -> B -> C -> D -> E -> A).

• Zusammenhängender Graph: Ja

Zusammengefasst:

• Anzahl der Knoten: 5
• Anzahl der Kanten: 5
• Zusammenhängender Graph: Ja

b)

Berechne die Anzahl der direkten Verbindungen (Nachbarschaftsbeziehungen) für jeden Knoten unter Verwendung der Adjazenzmatrix. Bestimme anschließend den Grad (Degree) für jeden Knoten.

Lösung:

Lass uns die Anzahl der direkten Verbindungen (Nachbarschaftsbeziehungen) für jeden Knoten berechnen und anschließend den Grad für jeden Knoten bestimmen, basierend auf der gegebenen Adjazenzmatrix.

Schritte zur Lösung:

• Verwende die Adjazenzmatrix, um die Anzahl der direkten Verbindungen für jeden Knoten zu berechnen.
• Bestimme den Grad (Degree) für jeden Knoten.

Die Adjazenzmatrix für das Netzwerk ist:

0 1 0 0 11 0 1 0 00 1 0 1 00 0 1 0 11 0 0 1 0

Schritt 1: Anzahl der direkten Verbindungen (Nachbarschaftsbeziehungen) berechnen

In einer Adjazenzmatrix zeigt eine '1' an Position (i,j) an, dass eine direkte Verbindung (Kante) zwischen Knoten i und Knoten j existiert. Um die Anzahl der direkten Verbindungen für jeden Knoten zu berechnen, summiere die Werte in jeder Zeile der Matrix.

• Knoten A (Zeile 1): 0 + 1 + 0 + 0 + 1 = 2
• Knoten B (Zeile 2): 1 + 0 + 1 + 0 + 0 = 2
• Knoten C (Zeile 3): 0 + 1 + 0 + 1 + 0 = 2
• Knoten D (Zeile 4): 0 + 0 + 1 + 0 + 1 = 2
• Knoten E (Zeile 5): 1 + 0 + 0 + 1 + 0 = 2

Schritt 2: Bestimmen des Grades (Degree) für jeden Knoten

Der Grad eines Knotens ist definiert als die Anzahl der Kanten, die zu diesem Knoten führen. Da wir in Schritt 1 bereits die Anzahl der direkten Verbindungen für jeden Knoten berechnet haben, ist der Grad jedes Knotens gleich der Anzahl dieser Verbindungen.

• Grad von Knoten A: 2
• Grad von Knoten B: 2
• Grad von Knoten C: 2
• Grad von Knoten D: 2
• Grad von Knoten E: 2

Zusammengefasst:

• Anzahl der direkten Verbindungen (Nachbarschaftsbeziehungen) für Knoten A: 2
• Anzahl der direkten Verbindungen (Nachbarschaftsbeziehungen) für Knoten B: 2
• Anzahl der direkten Verbindungen (Nachbarschaftsbeziehungen) für Knoten C: 2
• Anzahl der direkten Verbindungen (Nachbarschaftsbeziehungen) für Knoten D: 2
• Anzahl der direkten Verbindungen (Nachbarschaftsbeziehungen) für Knoten E: 2
• Grad von Knoten A: 2
• Grad von Knoten B: 2
• Grad von Knoten C: 2
• Grad von Knoten D: 2
• Grad von Knoten E: 2

Aufgabe 3)

Betrachte einen gewichteten, ungerichteten Graphen G mit der Knotenmenge V = {A, B, C, D, E} und der Kantenmenge E = {(A, B, 3), (A, C, 1), (B, C, 1), (B, D, 2), (C, D, 4), (C, E, 5), (D, E, 2)}.

a)

Bestimme die Adjazenzmatrix des Graphen G. Stelle sicher, dass die Gewichte der Kanten korrekt berücksichtigt werden.

Lösung:

Um die Adjazenzmatrix für den gegebenen gewichteten, ungerichteten Graphen G zu bestimmen, folgen wir diesen Schritten:

• Identifiziere die Knoten des Graphen: V = {A, B, C, D, E}.
• Erstelle eine 5x5-Matrix, da es fünf Knoten gibt.
• Setze die Diagonaleinträge der Matrix zu 0, weil keine Schleifen (Kanten von einem Knoten zu sich selbst) im Graphen vorhanden sind.
• Fülle die Matrix mit den Gewichten der Kanten gemäß der Kantenliste: E = {(A, B, 3), (A, C, 1), (B, C, 1), (B, D, 2), (C, D, 4), (C, E, 5), (D, E, 2)}.

Die Adjazenzmatrix sieht folgendermaßen aus:

 0  3  1  0  0 

 3  0  1  2  0 

 1  1  0  4  5 

 0  2  4  0  2 

 0  0  5  2  0 

Hier noch ein paar Anmerkungen zur Adjazenzmatrix:

• Die Zeilen und Spalten der Matrix entsprechen den Knoten A, B, C, D und E in dieser Reihenfolge.
• Ein Eintrag in der Zeile i und Spalte j der Matrix repräsentiert das Gewicht der Kante zwischen dem Knoten i und dem Knoten j.
• Da der Graph ungerichtet ist, ist die Adjazenzmatrix symmetrisch (d.h. der Eintrag in der Zeile i und Spalte j ist gleich dem Eintrag in der Zeile j und Spalte i).

b)

Überprüfe, ob der Graph G zusammenhängend ist. Erkläre Deine Vorgehensweise und begründe Deine Antwort.

Lösung:

Um zu überprüfen, ob der gegebene Graph G zusammenhängend ist, starten wir mit der Definition der Zusammenhängigkeit:

• Ein Graph ist zusammenhängend, wenn es in ihm zwischen jedem Paar von Knoten mindestens einen Pfad gibt.

Wir können die Zusammenhängigkeit auf verschiedene Weisen überprüfen, eine der gängigsten Methoden ist die Nutzung der Tiefensuche (DFS, Depth-First Search) oder die Breitensuche (BFS, Breadth-First Search).

Wir verwenden hier den DFS-Algorithmus zur Veranschaulichung. Die Schritte sind wie folgt:

• Wähle einen beliebigen Startknoten (z. B. Knoten A).
• Markiere den Startknoten als besucht.
• Besuche iterativ alle erreichbaren Nachbarknoten des aktuellen Knotens, markiere sie als besucht und wiederhole den Vorgang für jeden dieser Nachbarknoten.
• Am Ende der Suche sollten alle Knoten besucht worden sein, wenn der Graph zusammenhängend ist.

Anwendung des DFS auf unseren Graphen G:

1. Starte bei Knoten A. Besuche und markiere A.
2. Von A aus gibt es Kanten zu B und C. Besuche und markiere B und C.
3. Von B aus gibt es Kanten zu A (bereits besucht), C (bereits besucht) und D. Besuche und markiere D.
4. Von C aus gibt es Kanten zu A (bereits besucht), B (bereits besucht), D (bereits besucht), und E. Besuche und markiere E.
5. Von D aus gibt es Kanten zu B (bereits besucht), C (bereits besucht), und E (bereits besucht).

Alle Knoten (A, B, C, D, E) wurden besucht, und damit haben wir gezeigt, dass es von jedem Knoten zu jedem anderen Knoten einen Pfad gibt.

Daher ist der Graph G zusammenhängend.

c)

Finde einen minimalen Spannbaum (Minimum Spanning Tree) für den Graphen G. Verwende dabei Prim's Algorithmus und erläutere die einzelnen Schritte.

Lösung:

Um einen minimalen Spannbaum (Minimum Spanning Tree, MST) für den Graphen G zu finden, verwenden wir Prim's Algorithmus. Hier sind die Schritte und Erklärungen:

• Initialisierung: Wähle einen Startknoten. Nehmen wir an, wir starten bei Knoten A. Setze die Gewichtssummen-Zählung auf 0.
• Erstellen der Knotenmenge: Markiere Knoten A als Teil des MST und liste alle benachbarten Kanten von A auf: {(A, B, 3), (A, C, 1)}.
• Schritt 1: Wähle die Kante mit dem kleinsten Gewicht aus der aktuellen Liste der benachbarten Kanten. Hier ist das (A, C, 1). Füge C zum MST hinzu und aktualisiere das Gewicht. Jetzt ist die aktuelle Gewichtssumme 1 und die benachbarten Kantenliste ist: {(A, B, 3), (C, B, 1), (C, D, 4), (C, E, 5)}.
• Schritt 2: Wähle die Kante mit dem kleinsten Gewicht aus der benachbarten Kantenliste: (C, B, 1). Füge B zum MST hinzu und aktualisiere das Gewicht. Jetzt ist die aktuelle Gewichtssumme 2 und die benachbarten Kantenliste ist: {(A, B, 3), (C, D, 4), (C, E, 5), (B, D, 2)}.
• Schritt 3: Wähle die Kante mit dem kleinsten Gewicht: (B, D, 2). Füge D zum MST hinzu und aktualisiere das Gewicht. Jetzt ist die aktuelle Gewichtssumme 4 und die benachbarten Kantenliste ist: {(A, B, 3), (C, D, 4), (C, E, 5), (D, E, 2)}.
• Schritt 4: Wähle die Kante mit dem kleinsten Gewicht: (D, E, 2). Füge E zum MST hinzu und aktualisiere das Gewicht. Jetzt ist die aktuelle Gewichtssumme 6 und die benachbarten Kantenliste ist: {(A, B, 3), (C, D, 4), (C, E, 5)}.
• Zusammenfassung: Da alle Knoten (A, B, C, D, E) nun im MST enthalten sind, stoppen wir den Algorithmus.

Der minimale Spannbaum (MST) besteht aus den Kanten:

 {(A, C, 1), (C, B, 1), (B, D, 2), (D, E, 2)} 

Die Gesamtgewichtssumme des minimalen Spannbaums beträgt 6.

Zusammenfassend kann der minimalen Spannbaum gezeichnet werden als:

• A --- 1 --- C
• C --- 1 --- B
• B --- 2 --- D
• D --- 2 --- E

Aufgabe 4)

Gegeben ist der folgende gewichtete gerichtete Graph G = (V, E) mit den Knoten V = {A, B, C, D, E, F} und den Kanten E sowie deren Gewichten:

• (A, B, 4)
• (A, C, 2)
• (B, C, 5)
• (B, D, 10)
• (C, E, 3)
• (E, D, 4)
• (D, F, 11)
• (E, F, 8)

a)

Berechne die Initialisierungswerte der Distanzen und konstruierte die Prioritätswarteschlange (Min-Heap). Zeige die Distanzen der Knoten 'B', 'C', 'D', 'E', und 'F' nach dem Initialisierungsschritt auf.

Lösung:

Teil 1: Initialisierung des Dijkstra-Algorithmus

Um den Dijkstra-Algorithmus zu verwenden, beginnt man mit der Initialisierung der Distanzen. Da der Startknoten 'A' ist, folgt die Initialisierung:

• Setze die Distanz zum Startknoten 'A' auf 0: dist(A) = 0
• Setze die Distanzen zu allen anderen Knoten auf Unendlich: dist(B) = ∞, dist(C) = ∞, dist(D) = ∞, dist(E) = ∞, dist(F) = ∞

Als Prioritätswarteschlange (Min-Heap) setzen wir den Startknoten 'A' mit seiner Distanz:

• Min-Heap = [(0, A)]

Initiale Distanzwerte nach Startknoten 'A':

• dist(B) = ∞
• dist(C) = ∞
• dist(D) = ∞
• dist(E) = ∞
• dist(F) = ∞

b)

Verwende den Dijkstra-Algorithmus, um die Distanzwerte nach jedem Schritt zu aktualisieren. Entferne dabei die Knoten aus der Min-Heap, die die kleinsten momentanen Distanzen besitzen, und aktualisiere die Distanzen der Nachbarknoten. Zeige die Zustand der Distanzwerte sowie der Warteschlange nach jedem Schritt auf.

Lösung:

Teil 2: Anwendung des Dijkstra-Algorithmus

Nun verwenden wir den Dijkstra-Algorithmus, um die Distanzwerte nach jedem Schritt zu aktualisieren. Dabei entfernen wir die Knoten aus der Min-Heap, die die kleinsten momentanen Distanzen besitzen, und aktualisieren die Distanzen der Nachbarknoten.

Schritt 1:

• Min-Heap vor der Entfernung: [(0, A)]
• Entferne Knoten A
• Aktualisiere die Distanzen der Nachbarn von A:
• dist(B) = min(∞, dist(A) + 4) = min(∞, 0 + 4) = 4
• dist(C) = min(∞, dist(A) + 2) = min(∞, 0 + 2) = 2
• Min-Heap nach der Aktualisierung: [(2, C), (4, B)]
• Distanzwerte:
• dist(A) = 0
• dist(B) = 4
• dist(C) = 2
• dist(D) = ∞
• dist(E) = ∞
• dist(F) = ∞

Schritt 2:

• Min-Heap vor der Entfernung: [(2, C), (4, B)]
• Entferne Knoten C
• Aktualisiere die Distanzen der Nachbarn von C:
• dist(E) = min(∞, dist(C) + 3) = min(∞, 2 + 3) = 5
• Min-Heap nach der Aktualisierung: [(4, B), (5, E)]
• Distanzwerte:
• dist(A) = 0
• dist(B) = 4
• dist(C) = 2
• dist(D) = ∞
• dist(E) = 5
• dist(F) = ∞

Schritt 3:

• Min-Heap vor der Entfernung: [(4, B), (5, E)]
• Entferne Knoten B
• Aktualisiere die Distanzen der Nachbarn von B:
• dist(C) = min(2, dist(B) + 5) = min(2, 4 + 5) = 2 (keine Änderung)
• dist(D) = min(∞, dist(B) + 10) = min(∞, 4 + 10) = 14
• Min-Heap nach der Aktualisierung: [(5, E), (14, D)]
• Distanzwerte:
• dist(A) = 0
• dist(B) = 4
• dist(C) = 2
• dist(D) = 14
• dist(E) = 5
• dist(F) = ∞

Schritt 4:

• Min-Heap vor der Entfernung: [(5, E), (14, D)]
• Entferne Knoten E
• Aktualisiere die Distanzen der Nachbarn von E:
• dist(D) = min(14, dist(E) + 4) = min(14, 5 + 4) = 9
• dist(F) = min(∞, dist(E) + 8) = min(∞, 5 + 8) = 13
• Min-Heap nach der Aktualisierung: [(9, D), (14, D), (13, F)]
• Distanzwerte:
• dist(A) = 0
• dist(B) = 4
• dist(C) = 2
• dist(D) = 9
• dist(E) = 5
• dist(F) = 13

Schritt 5:

• Min-Heap vor der Entfernung: [(9, D), (14, D), (13, F)]
• Entferne Knoten D
• Aktualisiere die Distanzen der Nachbarn von D:
• dist(F) = min(13, dist(D) + 11) = min(13, 9 + 11) = 13 (keine Änderung)
• Min-Heap nach der Aktualisierung: [(13, F), (14, D)]
• Distanzwerte:
• dist(A) = 0
• dist(B) = 4
• dist(C) = 2
• dist(D) = 9
• dist(E) = 5
• dist(F) = 13

Schritt 6:

• Min-Heap vor der Entfernung: [(13, F), (14, D)]
• Entferne Knoten F
• Keine weiteren Nachbaraktualisierungen möglich
• Min-Heap nach der Aktualisierung: [(14, D)]
• Distanzwerte:
• dist(A) = 0
• dist(B) = 4
• dist(C) = 2
• dist(D) = 9
• dist(E) = 5
• dist(F) = 13

Alle Knoten wurden nun entfernt, und die kürzesten Distanzen von 'A' zu allen anderen Knoten wurden erfolgreich berechnet.

c)

Gib die kürzesten Wege und deren dazugehörigen Distanzen vom Startknoten 'A' zu allen anderen Knoten 'B', 'C', 'D', 'E', 'F' an. Zeige die resultierenden kürzesten Wege in Form von Pfaden (z.B. A -> C -> E -> D) und deren Gesamtdistanzen. Erkläre, wie Du zu dieser Lösung gekommen bist.

Lösung:

Kürzeste Wege und deren Distanzen vom Knoten 'A'

Um die kürzesten Pfade und deren Gesamtdistanzen zu bestimmen, analysieren wir die resultierenden Distanzwerte und rekonstruieren die Pfade basierend auf den Aktualisierungen der Distanzen während des Dijkstra-Algorithmus.

1. Kürzester Weg zu Knoten 'B'

• Pfad: A -> B
• Gesamtdistanz: 4
• Begründung: Nach dem ersten Schritt des Algorithmus wurde die Distanz von A nach B auf 4 gesetzt, da dies die direkte Verbindung ist.

2. Kürzester Weg zu Knoten 'C'

• Pfad: A -> C
• Gesamtdistanz: 2
• Begründung: Nach dem ersten Schritt des Algorithmus wurde die Distanz von A nach C auf 2 gesetzt, da dies die direkte Verbindung ist.

3. Kürzester Weg zu Knoten 'D'

• Pfad: A -> C -> E -> D
• Gesamtdistanz: 9
• Begründung: Die kürzeste Distanz zu D wurde durch folgende Schritte erreicht:
  • Distanz von A -> C = 2
  • Hinzu kommt C -> E = 3, sodass A -> C -> E = 5 ergibt
  • Zuletzt von E -> D = 4, sodass A -> C -> E -> D = 5 + 4 = 9 ergibt

4. Kürzester Weg zu Knoten 'E'

• Pfad: A -> C -> E
• Gesamtdistanz: 5
• Begründung: Die kürzeste Distanz zu E wurde durch folgende Schritte erreicht:
  • Distanz von A -> C = 2
  • Hinzu kommt C -> E = 3, sodass A -> C -> E = 2 + 3 = 5 ergibt

5. Kürzester Weg zu Knoten 'F'

• Pfad: A -> C -> E -> F
• Gesamtdistanz: 13
• Begründung: Die kürzeste Distanz zu F wurde durch folgende Schritte erreicht:
  • Distanz von A -> C = 2
  • Hinzu kommt C -> E = 3, sodass A -> C -> E = 2 + 3 = 5 ergibt
  • Zuletzt von E -> F = 8, sodass A -> C -> E -> F = 5 + 8 = 13 ergibt

Zusammenfassung:

• A -> B: 4
• A -> C: 2
• A -> C -> E -> D: 9
• A -> C -> E: 5
• A -> C -> E -> F: 13

Mit diesen Schritten und Berechnungen haben wir die kürzesten Wege und deren Gesamtdistanzen vom Startknoten 'A' zu allen anderen Knoten 'B', 'C', 'D', 'E' und 'F' ermittelt.