📚Graphentheorie¶

🚀 Artikulationspunkte & Brücken in Graphen¶

Wir starten jetzt mit dem Thema Artikulationspunkte (Cut Vertices) und Brücken (Bridges) in Graphen. Diese Konzepte sind besonders wichtig für die Analyse von Netzwerken und Verbindungsstrukturen.

📚 1️⃣ Was sind Artikulationspunkte und Brücken?¶

✅ Artikulationspunkt (Cut Vertex):¶

✅ Artikulationspunkt (Cut Vertex): Trennung durch Entfernen eines Knotens.
Ein Artikulationspunkt ist ein Knoten in einem zusammenhängenden ungerichteten Graphen, dessen Entfernung den Graphen in zwei oder mehr separate Teilgraphen aufteilt.
Bedeutung: Wenn ein Artikulationspunkt ausfällt, kann das Netzwerk auseinanderbrechen.

✅ Brücke (Bridge oder Cut Edge):¶

✅ Brücke (Cut Edge): Trennung durch Entfernen einer Kante.
Eine Brücke ist eine Kante, deren Entfernung den Graphen ebenfalls in zwei oder mehr Teilgraphen zerlegt.
Bedeutung: Wenn eine Brücke ausfällt, reißt das Netzwerk an dieser Stelle ab.

🚀 3️⃣ Algorithmus zur Erkennung von Artikulationspunkten¶

Wir verwenden eine modifizierte Tiefensuche (DFS) mit zwei wichtigen Konzepten:

Entdeckungszeit (Discovery Time, disc[]):
Zeitpunkt, an dem ein Knoten während der DFS erstmals besucht wird.
Low-Wert (low[]):
Der niedrigste Discovery-Wert, den ein Knoten erreichen kann, indem er Rückkanten (Back Edges) verwendet.

✅ Kriterien für Artikulationspunkte:¶

Für die Wurzel des DFS-Baumes:
- Artikulationspunkt, wenn sie mehr als ein Kind hat.
Für alle anderen Knoten v:
- v ist ein Artikulationspunkt, wenn es ein Kind u gibt, sodass:
- \[low[u]≥disc[v]\]
- Das bedeutet: Es gibt keinen anderen Weg zurück nach oben, außer durch v.

🔍 Pseudo-Code Artikulationspunkte

FUNKTION findArticulationPoints(G):
    INITIALISIERE:
        disc[] = -1   // Discovery-Zeit für jeden Knoten
        low[] = -1    // Low-Wert für jeden Knoten
        parent[] = -1
        ap[] = false  // Artikulationspunkte markieren
        time = 0

    FÜR jeden Knoten v in G:
        WENN v nicht besucht:
            DFS(v)

FUNKTION DFS(v):
    disc[v] = low[v] = time
    time += 1
    kind = 0  // Anzahl der Kinder im DFS-Baum

    FÜR jeden Nachbarn u von v:
        WENN u nicht besucht:
            parent[u] = v
            kind += 1
            DFS(u)

            low[v] = min(low[v], low[u])

            // Artikulationspunkt-Bedingung (Nicht-Wurzel)
            WENN parent[v] ≠ -1 UND low[u] ≥ disc[v]:
                ap[v] = true

        ANDERNFALLS WENN u ≠ parent[v]:
            low[v] = min(low[v], disc[u])

    // Wurzel-Bedingung
    WENN parent[v] == -1 UND kind > 1:
        ap[v] = true

🚀 7️⃣ Brücken (Bridges) – Erkennung¶

Der Algorithmus ist fast identisch zu Artikulationspunkten, aber mit einer anderen Bedingung:

✅ Bedingung für Brücken:¶

Eine Kante (u, v) ist eine Brücke, wenn:
\[low[v]>disc[u]\]
Das bedeutet, dass v keine Rückkante zu einem früher besuchten Knoten außer über u hat.

⏱️ 8️⃣ Komplexität¶

Laufzeit: \(O(V+E)\)
Platzbedarf: \(O(V)\)

Effizient für große, zusammenhängende Netzwerke.

🎯 9️⃣ Fazit¶

✅ Artikulationspunkte: Knoten, deren Entfernung den Graphen in Teile zerlegt.
✅ Brücken: Kanten, deren Entfernung den Graphen trennt.
✅ DFS-basiert: Effizient und weit verbreitet in Netzwerkanalysen.