U-Bahn/Stadtteil/Umsteigefreie Verbindung/Beispiel

Wir betrachten den durch eine U-Bahn in einer Stadt gegebenen Graphen, der aus der Menge der Haltestellen gegeben ist, und bei dem zwei Haltestellen durch eine Kante verbunden werden, wenn sie ohne Umsteigen verbunden sind, also an einer Linie liegen (siehe Beispiel). Es ist nicht zu erwarten, dass jede Haltestelle mit jeder anderen Haltestelle durch eine direkte Linie verbunden ist. Die Steuereinnahmen sprudeln kräftig und so möchte man wissen, ob zumindest jeder Stadtteil mit jedem Stadtteil ohne Umsteigen erreichbar ist. Dazu stellt man einen neuen Graphen auf, bei dem die Knotenpunkte die Stadtteile repräsentieren und bei dem zwei Stadtteile genau dann miteinander durch eine Kante zu verbinden sind, wenn es eine Haltestelle im einen und eine Haltestelle im andern Stadtteil gibt, die durch eine U-Bahnlinie verbunden sind.