Verkehrsnetz/Erreichbarkeit/Graph/Beispiel

Ein Verkehrsnetz, beispielsweise ein ${}U$-Bahnnetz, kann man in verschiedener Weise als einen Graphen interpretieren. Die Knotenmenge ist die Menge der Haltestellen. Man kann nun zwei Haltestellen miteinander durch eine Kante verbinden, wenn sie direkt durch eine Linie unmittelbar benachbart sind (wenn es eine direkte Tunnelverbindung ohne Zwischenstation gibt). Dies ist der Graph (Netzgraph), der üblicherweise als Netzplan aushängt (wenn verschiedene Linien eine Strecke lang parallel fahren, ist dies für den Graphen unerheblich, ist aber im Netzplan sichtbar). Man kann aber auch zwei Haltestellen miteinander durch eine Kante verbinden, wenn sie an einer gemeinsamen Linie liegen, also ohne Umsteigen erreichbar sind. Im eben erwähnten Netzplan ist dies durch die verschiedenen Farben der Linien einfach erkennbar. Würde man aber all diese Kanten hinmalen, ergäbe sich schnell eine unübersichtliche Darstellung der Netzsituation. Die volle Erreichbarkeit (also mit Umsteigen) wird typischerweise durch den vollständigen Graphen der Haltestellen dargestellt, es sei den, das Liniennetz zerfällt in zueinander disjunkte Teilnetze (das gilt zur Zeit in Berlin).