Ein soziales Netzwerk hat 2019 Nutzer, von denen einige paarweise befreundet sind. Immer wenn der Nutzer A mit dem Nutzer B befreundet ist, dann ist auch der Nutzer B mit dem Nutzer A befreundet. Ereignisse der folgenden Art können wiederholt nacheinander stattfinden:
Drei Nutzer A, B und C, von denen A mit B und C befreundet ist, aber B und C nicht befreundet sind, wechseln den Status ihrer Freundschaften so, dass jetzt B und C befreundet sind, aber A nicht mehr mit B befreundet ist und auch nicht mehr mit C befreundet ist. Der Status aller anderen Freundschaften bleibt unverändert.Anfangs sind 1010 Nutzer mit jeweils genau 1009 Nutzern befreundet und 1009 Nutzer mit jeweils genau 1010 Nutzern befreundet. Man beweise, dass es eine Folge solcher Ereignisse gibt, nach der jeder Nutzer höchstens mit einem anderen Nutzer befreundet ist.
Über diese Aufgabe von der Internationalen Mathematikolympiade war hier die letzten Tage diskutiert worden.
Mathematisch gesehen hat man hier einen ungerichteten Graphen mit 2019 Knoten, von denen 1010 den Grad 1009 und 1009 den Grad 1010 haben. Die einzige erlaubte Operation ist
Bei dieser Operation wird die Anzahl der Kanten um 1 reduziert. Insbesondere wird man nach einer endlichen Anzahl von Schritten „fertig“ sein, also mit dem Verfahren nicht mehr weiter machen können, entweder weil es nur noch eine Kante gibt oder weil es nur noch Dreiecke gibt, auf die sich die Operation ja nicht anwenden läßt.
Außerdem wird bei der Operation der Grad (die Anzahl der ausgehenden Kanten9 eines Knotens um 2 reduziert, während die Grade der anderen Knoten sich nicht ändern. Die Parität (gerade oder ungerade) der Knoten ändert sich also nicht.
Am Schluß will man eine Menge isolierter Kanten haben, graphentheoretisch formuliert: alle Knoten sollen Grad 0 oder 1 haben. Dabei muß dann eine gerade Anzahl von Knoten Grad 1 haben.
Weil sich die Parität der Grade einzelner Knoten während des Verfahrens nicht ändert, muß auch zum Beginn eine gerade Anzahl von Knoten ungeraden Grad gehabt haben. (Man kann damit auch die Anzahl der zum Schluß übrigbleibenden Kanten berechnen: sie ist genau halb so groß wie die Anzahl der Knoten von ungeraden Grad, also 505.)
Man sieht also, dass die Zahlen 1010 und 1009 nicht völlig beliebig sind. Es ist wichtig, dass 1010 gerade und 1009 ungerade ist, damit eine gerade Anzahl von Knoten ungeraden Grad hat.
Wenn man etwas herumprobiert, von welchen Graphen man zum gewünschten Ende kommen kann, dann stößt man zunächst auf Bäume. Tatsächlich kann man sich leicht überlegen, dass man einen Baum immer wie im Bild unten zu einer Menge isolierter Kanten reduzieren kann.
Dagegen kann man Dreiecke nicht weiter reduzieren, wenn es keine mit ihnen verbundenen Knoten mehr gibt. Und auch von einem isolierten n-Eck kann man nicht zur gewünschten Lösung kommen, weil man wie im Bild unten durch Anwenden der Operationen letztlich immer isolierte Dreiecke bekommen wird. Das läßt sich leicht erklären: im n-Eck hat man 0 Ecken von ungeraden Grad, durch die Operation bleibt die Anzahl der Knoten von ungeradem erhalten, am Ende muß man aber mindestens 2 Knoten von ungeraden Grad haben.
Die naheliegende Strategie ist nun, den gegebenen Graphen durch die Operation in einen Baum umzuwandeln. Man beachte, dass der Ausgangsgraph zusammenhängend ist, denn zwei nicht benachbarte Knoten haben zusammen 2019 Nachbarn, also mindestens zwei gemeinsame Nachbarn.
Ein Baum ist ein zusammenhängender Graph ohne Kreise. Es läge also nahe, in jedem Schritt die Anzahl der Kreise reduzieren zu wollen wie im Bild unten, den Graphen gleichzeitig aber zusammenhängend zu halten.
Das ist wie im Bild oben immer dann möglich, wenn es neben dem Kreis noch einen weiteren Knoten gibt, der mit einem, aber nicht allen Knoten des Kreises verbunden ist. Wenn sich diese Operation in jedem weiteren Schritt so wiederholen läßt, dann muß man irgendwann zu einem Graph ohne Kreise kommen. (Es wird ja in jedem Schritt die Anzahl der Kanten um 1 reduziert, man kann sie also nicht unendlich oft fortführen.) Man muß also beweisen, dass man nach jedem Schritt entweder einen Baum ohne Kreise oder eben einen Kreis nebst einem weiteren mit einem, aber nicht mit den zu diesem benachbarten Knoten des Kreises verbundenen Knoten hat.
Angenommen also, wir haben keinen Baum, dann gibt es einen minimalen Kreis. Dieser minimale Kreis kann nicht durch alle Ecken gehen, denn sonst hätten wir ein n-Eck, was wie oben gesagt, nicht möglich ist. Also gibt es (weil der Graph i, er noch zusammenhängend ist) mindestens einen weiteren mit dem Kreis verbundenen Knoten. Wenn dieser nicht mit den benachbarten Knoten des Kreises verbunden ist, dann sind wir fertig. Wenn doch, dann haben wir zwei Dreiecke. Weil wir von einem minimalen Kreis ausgegangen sind, muß dieser auch ein Dreieck gewesen sein. Man kann jetzt wie folgt argumentieren: die verschiedeneren Dreiecke können sich zu einem größeren vollständigen Graphen zusammensetzen, dieser kann aber nicht der vollständige Graph auf 2019 Ecken sein, weil der Ausgangsgraph nicht vollständig war und im Laufe des Prozesses die Kantenzahl reduziert wurde. Man betrachtet also einen maximalen vollständigen Teilgraphen (ggf. nur ein Dreieck), dazu findet man wegen der Maximalität einen benachbarten Knoten, der mit einem anderen Knoten des vollständigen Teilgraphen nicht benachbart ist. Durch die Knoten des vollständigen Teilgraphen kann man dann einen Kreis legen, der die am Ende des vorigen Abschnitts formulierte Bedingung erfüllt, also zu dem man einen weiteren verbundenen Knoten findet, der mit einem Knoten des Kreises, aber nicht dessen einem Nachbarn verbunden ist.
Man kann also, solange es noch Kreise gibt, auf jeden Fall den Prozeß fortführen und die Anzahl der Kanten reduzieren (und den Graphen zusammenhängend halten) bis man nach endlich vielen Schritten keine Kreise und damit einen Baum hat, von dem man dann auf den gewünschten Graphen aus 505 isolierten Kanten kommt.
Das war die zweite Lösung der Musterlösungen, die erste ist aufwändiger, weil sie mehr Fallunterscheidungen benötigt.
Man kann das Problem auch noch in einen allgemeineren Kontext stellen, indem man für jeden beliebigen Graphen beweist, dass er sich durch Anwenden dieser Operation entweder in einen Baum oder in ein n-Eck verwandeln läßt. Da, wie oben gesagt,aus dem Graphen in der Aufgabenstellung (weil es Knoten ungeraden Grades gibt) kein n-Eck erzeugt werden kann, muß man diesen Graphen also in einen Baum verwandeln können. Diesen allgemeinen Beweis führt Presh Talwalkar RedPig (Retired Contestants of Math Olympiads) im folgenden Video vor:
Kommentare (3)