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.
Kommentare (3)