[Graphentheorie] Zeige: Jede Stadt hat 2 Nachbarn
-
Man zeige mit Hilfe eines geeigneten graphentheoretischen Modells, dass es in jeder Stadt mindestens zwei Bewohner mit der gleichen Anzahl von Nachbarn gibt.
Das habe ich mathematisch so formuliert:
LaTeX hat irgendwas, setzt euch einfach folgendes: \exists a, b \in V(G), a \neq b : d(a) = d(b)
Das dem so ist, ist mir klar. Existiert ein Zyklus, haben zwei innere Knoten den selben Grad, sind an dem Zyklus andere Gebilde angehängt, haben zwei äußere Quasi-Wurzeln jeweils einen Nachbar - dem im Zyklus. Das sollte zumindest für endliche Graphen gelten.
Aber wie beweise ich das? Da fehlt mir nun leider der Ansatz
MfG SideWinder
-
Textueller Beweis - aber wie math. formulieren: Der erste Knoten hat einen Nachbar, der nächste daraufhin zwei, bei diesen beiden muss einer drei, der nächste vier haben, das müssen immer mehr werden, da der Graph aber irgendwann stoppen muss um endlich zu sein, ist es nur mit Hilfe von Zyklen abbrechbar. In Zyklen haben aber immer zwei Knoten den selben Grad bzw. es geht von jedem Knoten wieder ein solches unendliches Gebilde aus.
MfG SideWinder
-
Hmm, ich glaub, mit Deinem Zyklus-Argument kommst Du nicht weiter. Können ja noch grössere Konstrukte an dem Kreis dran hängen, als nur einzelne Knoten.
Versuchs mal anders: Sei n die Anzahl der Knoten. Welche Knotengrade sind überhaupt möglich? Kannst Du jetzt schon mit dem Schubfachprinzip argumentieren? (Nein, aber...)
-
Ein anderer möglicher Weg, wäre ein minimales Gegenbeispiel zu betrachten. Also einen kleinstmöglichen Graphen bei dem alle Knoten unterschiedlichen Grad haben... wenn man nun geeignete Knoten entfernt bekommt man ein kleineres Gegenbeispiel.
-
Jester schrieb:
Ein anderer möglicher Weg, wäre ein minimales Gegenbeispiel zu betrachten. Also einen kleinstmöglichen Graphen bei dem alle Knoten unterschiedlichen Grad haben... wenn man nun geeignete Knoten entfernt bekommt man ein kleineres Gegenbeispiel.
Kannst du einen Tipp geben, welche? Ich würde z.B. gern einen Knoten entfernen, der nur mit Knoten von minimalem Grad verbunden ist. Aber so einen muss es ja nicht geben...
-
Heinzelmännchen33 schrieb:
Jester schrieb:
Ein anderer möglicher Weg, wäre ein minimales Gegenbeispiel zu betrachten. Also einen kleinstmöglichen Graphen bei dem alle Knoten unterschiedlichen Grad haben... wenn man nun geeignete Knoten entfernt bekommt man ein kleineres Gegenbeispiel.
Kannst du einen Tipp geben, welche? Ich würde z.B. gern einen Knoten entfernen, der nur mit Knoten von minimalem Grad verbunden ist. Aber so einen muss es ja nicht geben...
anfangen würd ich mal mit dem der den größten Grad hat. Der Rest ist nur noch Reparatur.
-
SG1 schrieb:
Versuchs mal anders: Sei n die Anzahl der Knoten. Welche Knotengrade sind überhaupt möglich? Kannst Du jetzt schon mit dem Schubfachprinzip argumentieren? (Nein, aber...)
Cool, danke. Es gibt n Knoten, von denen alle maximal n-1 Nachbarn haben können. Da eine Stadt zusammenhängt müssen sie mindestens einen Nachbarn haben. Macht also |{1,...,n-1}| Möglichkeiten. Da ich aber n verschiedene benötige, existiert mindestens ein Knoten mit demselben Grad.
MfG SideWinder
-
Jester schrieb:
Heinzelmännchen33 schrieb:
Jester schrieb:
Ein anderer möglicher Weg, wäre ein minimales Gegenbeispiel zu betrachten. Also einen kleinstmöglichen Graphen bei dem alle Knoten unterschiedlichen Grad haben... wenn man nun geeignete Knoten entfernt bekommt man ein kleineres Gegenbeispiel.
Kannst du einen Tipp geben, welche? Ich würde z.B. gern einen Knoten entfernen, der nur mit Knoten von minimalem Grad verbunden ist. Aber so einen muss es ja nicht geben...
anfangen würd ich mal mit dem der den größten Grad hat. Der Rest ist nur noch Reparatur.
Wir entfernen den mit größtem Grad d, nennen wir ihn x. Es ist jedenfalls d <= #vert(G).
a) Ist d < #vert(G), dann haben die restlichen #vert(G)-1 Knoten Grade in [0, #vert(G)-2], also kommt jeder dieser Grade genau 1-mal vor. Wenn wir also den Knoten, der mit keinem anderen verbunden ist, rausnehmen, ändern sich die anderen Knotenzahlen nicht, und wir sind fertig.
b) Ist d = #vert(G), dann ist x mit jedem Knoten genau 1-mal verbunden (inkl. sich selbst). Wenn wir ihn entfernen, verringert sich also die Gradzahl bei jedem der anderen Knoten genau um 1, also sind auch noch alle verschieden. Widerspruch zu minimalem Gegenbeispiel.Geht das noch einfacher mit diesem Ansatz?
Welches Buch für Graphentheorie kannst du empfehlen?
-
Übungsaufgabe: zeige, es gibt auch dann noch zwei Knoten mit gleichem Grad, wenn Grad-0-Knoten erlaubt sind.
-
Jester schrieb:
Übungsaufgabe: zeige, es gibt auch dann noch zwei Knoten mit gleichem Grad, wenn Grad-0-Knoten erlaubt sind.
Das ist imho dasselbe Beispiel, nur dass ich noch einen zusätzlichen Knoten irgendwo platziere. Für den restlichen (zusammenhängenden) Graphen gibt es weiterhin nur die Möglichkeit n-1 und nochmal -1 für den alleinestehenden Knoten mögliche Nachbarn.
MfG SideWinder
-
Jester schrieb:
Übungsaufgabe: zeige, es gibt auch dann noch zwei Knoten mit gleichem Grad, wenn Grad-0-Knoten erlaubt sind.
das war jetzt aber auf sidewinder bezogen, oder? Bei mir wird das ja erlaubt
-
Heinzelmännchen33 schrieb:
Geht das noch einfacher mit diesem Ansatz?
ne, denke nicht. ist ja auch einfach genug nun.
Welches Buch für Graphentheorie kannst du empfehlen?
hm, gute Frage. Der Diestel ist denke ich recht gut als allgemeine Einführung und er behandelt recht viel. Für speziellere Themen gibt's natürlich auch speziellere Bücher.
@Sidewinder: ja, ist im prinzip dasselbe. Aber du mußt keinen Zusammenhang des Graphen ausnutzen, die Aussage gilt auch ohne diese Voraussetzung.
-
Jester schrieb:
Heinzelmännchen33 schrieb:
Geht das noch einfacher mit diesem Ansatz?
ne, denke nicht. ist ja auch einfach genug nun.
Aber falsch, da Heinzelmännchen (ungerichtete) Selbstkanten erlaubt. Damit ergibt sich nämlich z.B. folgendes Gegenbeispiel:
G = (V = {u,v}, E = { {u,v}, {v,v} }
-
Ja, Schlingen darf der Graph natürlich nicht haben. Insbesondere kann man sonst jeden Knoten nur oft genug mit sich selbst verbinden.
edit: Multikanten dürfen auch nicht da sein.