Kann mir das jemand ganz einfach erklären?
Jede Straße in Sikinia ist eine Einbahnstraße. Jedes Städtepaar ist genau durch eine direkte Straße verbunden. Zeigen Sie, dass es eine Stadt gibt, die von jeder Stadt aus direkt oder über höchstens eine andere Stadt erreicht werden kann.
1 Antwort
Das ist ein Problem aus der Graphentheorie, jede Kante im Graphen ist gerichtet und zwischen zwei Knoten gibt es nur eine Kante.
Gefragt wird nun nach der Existenz eines Knoten (ich nenne ihn "Zielknoten" K), der von jedem anderen Knoten erreicht werden kann, entweder direkt (Entfernung 1) oder über maximal einen anderen Knoten (Entfernung 2).
Ein direkter Beweis fällt mir nicht ein, nur Induktion scheint mir gelegen: Bei einem, zwei und drei Knoten ist es offensichtlich. Sei es also für n = 1, 2 oder 3 bewiesen.
Wir untersuchen den Fall n+1, sei der bisherige Zielknoten k: Wir bauen einen Knoten N an. Folgendes ist möglich: Auch dieser Knoten zeigt direkt oder über eine andere Stadt auf K, dann bleibt es dabei, dass es einen solchen Zielknoten gibt. Dieser Fall ist einfach.
Sei dies nun nicht der Fall. Das kann nur dann sein, wenn K sowie alle Knoten, welche über Entfernung 1 auf K zeigen, nunmehr auf N zeigen. Denn ansonsten würde N mit Entfernung 2 auf K zeigen und K bliebe Zielknoten. Dadurch wird N potentieller neuer Zielknoten. Sie M1 die Menge der Knoten, welche von K die Entfernung 1 haben. Noch nicht untersucht haben wir diejenigen Knoten, welche mit Entfernung 2 auf K zeigen. Auf diese könnte N zeigen, N hätte insoweit Entfernung 3 auf K, K verliert die Eigenschaft als Zielknoten. Sei diese Knotenmenge, welche von K die Entfernung 2 haben, die Menge M2.
Damit N nun nicht zum Zielknoten wird, darf K nicht mit Entfernung 1 auf einen Knoten aus M2 zeigen, sei dieser M2A. Auch darf, wegen der Einbahnstraßeneigenschaft, nicht derselbe Knoten sowohl auf dem Hin- als auch auf dem Rückweg mitteln, es gibt also zwei Vermittler, Hinweg von K zu M2A (VH) und Rückweg M2A zu K (VR). Demnach untersuchen ein Geflecht aus vier Knoten K, M2A, VH und VR. Dabei muss gelten, dass Entfernung K zu M2A zwei beträgt, auf Hin- und Rückweg. Das ist unmöglich, weil M2A und K ein Städtepaar sind und es somit eine Einbahnstraße geben muss. Widerspruch. Demnach wird N neuer Zielknoten oder K bleibt alter Zielknoten.
Beweisidee hier: vollständige Induktion, innerhalb des Induktionsschrittes Reduktion des Problems auf vier Knoten. Müsste aber wohl auch deutlich kürzer gehen ...
Kürzere Fassung des letzten Absatzes: Damit N nun nicht zum Zielknoten wird, darf K nicht mit Entfernung 1 auf einen Knoten aus M2 zeigen. Da aber K und sämtliche Knoten aus M2 jedoch Städtepaare sind M2 nicht direkt auf K zeigt, muss K direkt auf sämtliche Knoten aus M2 zeigen. Damit zeigt K mit Entfernung 2 auf N, N wird neuer Zielknoten. Geht aber vielleicht noch kürzer ...