Graphen — Netzwerke modellieren
Definition · Graph
Ein Graph G = (V, E) besteht aus einer Knotenmenge V und einer Kantenmenge E ⊆ V × V.
Beispiele aus der echten Welt
- Soziale Netzwerke: Knoten = Menschen, Kanten = Freundschaften.
- Routenplanung: Knoten = Städte, Kanten = Straßen mit Distanz-Gewicht.
- Internet: Knoten = Webseiten, Kanten = Hyperlinks.
- Schaltungen: Knoten = Bauteile, Kanten = Drähte.
- Aufgaben-Reihenfolge: DAG (gerichteter azyklischer Graph) für Projektplanung.
Wichtige Begriffe
| Begriff | Bedeutung |
|---|---|
| Grad | Anzahl Kanten an einem Knoten |
| Pfad | Folge von Kanten ohne Wiederholung |
| Zyklus | geschlossener Pfad (Anfang = Ende) |
| Vollständig | jeder Knoten mit jedem verbunden |
| Bipartit | Knoten in 2 Gruppen, Kanten nur dazwischen |
| Baum | zusammenhängend, kein Zyklus |
Wichtige Algorithmen
Dijkstra: kürzester Weg zwischen zwei Knoten
BFS: Breadth-First Search (alle Knoten ebenenweise)
DFS: Depth-First Search (in die Tiefe)
Kruskal/Prim: minimaler Spannbaum
Topological Sort: Reihenfolge in DAGEulers Knotengrad-FormelSumme aller Knotengrade = 2 · |E|. Jede Kante zählt 2× — einmal pro Endpunkt.