Graphentheorie: Anzahl von Knoten beweisen
-
Hallo,
ich habe hier eine Hausaufgabe, bei der ich absolut nicht weiterkomme. Wollte mal fragen, ob mir jemand einen Tipp geben möchte, wie ich am besten an die Aufgabe ran gehen soll?
Aufgabe schrieb:
für den ungerichteten Graphen G = (V, E) gilt: ∀ x ∈ V : d(x) ≥ a und der kürzeste Kreis (der Länge /= 0) hat Länge 5. Beweisen Sie, dass G mindestens a² + 1 Knoten besitzt.
Ich hab schon versucht mir das graphisch irgendwie herzuleiten. Da bin ich aber nicht sehr weit gekommen, da das ganze zu schnell unübersichtlich wurde. Jetzt bin ich am überlegen ob das überhaupt Sinn macht sich das vorzustellen oder ob es besser ist nur eine Formel zu finden, die man induktiv beweisen kann. Vorschläge?
-
Was heißt "der kürzeste Kreis (der Länge = 0) hat Länge 5"? Ist d bei dir die Zahl adjazenter Knoten oder die Zahl inzidenter Kanten?
-
d gibt die Zahl der adjazenten Knoten an.
-
Sieht nach Induktion aus. 5 = 2² + 1
-
Soweit war ich auch schon. Das reicht aber bei weitem nicht aus, weil keine Aussage über die Kanten und schon gar nicht über einen minimalen Zyklus von 5 getroffen werden kann.
-
Michael E. schrieb:
Was heißt "der kürzeste Kreis (der Länge = 0) hat Länge 5"?
-
Oh, tut mir Leid, da meine ich nicht = sondern . Sonst macht das natürlich keinen Sinn. Der kürzeste Kreis soll also mindestens fünf Knoten umfassen.
-
Dann ist die Aussage ziemlich leicht zu zeigen. Denk nicht zu kompliziert. Eine Induktion wird schwierig, weil du sie über a und n machen müsstest. Schau dir einfach mal einen beliebigen Knoten an, seine Nachbarn und deren Nachbarn und zähle diese.
-
Jetzt bin ich total verwirrt. Ich meine gerade herausgefunden zu haben, dass man den geforderten Graphen auch nur mit 5a Knoten darstellen kann, was laut Aufgabenstellung nicht funktioniert.
Ich hab am Anfang dazu einen Petersen Graphen genommen. Was a=3 darstellt. a=2 wären nur die inneren fünf Knoten des Petersen Graphen. Für alle a>3 hab ich jetzt wie bei a=2 fünf neue Knoten ergänzt, diese intern wieder so wie beim Petersen Graphen verbunden und dann mit den restlichen bereits vorhandenen Knoten.
Hab ich da einen Denkfehler?
Was anderes ist mir jetzt nicht aufgefallen. Einen Weg wie man einen Graphen durch a²+1 Knoten mit je a Kanten darstellen kann hab ich nicht gefunden.
-
Antoras schrieb:
Was anderes ist mir jetzt nicht aufgefallen. Einen Weg wie man einen Graphen durch a²+1 Knoten mit je a Kanten darstellen kann hab ich nicht gefunden.
Mal vorweg: Das sollst Du ja auch gar nicht. Du sollst zeigen: Wenn Du einen Graphen wie in der Aufgabenstellung (also mit einem bestimmten Mindestgrad und ohne Kreise der Länge 3 oder 4) hast, dann besitzt er mindestens a²+1 Knoten.
Antoras schrieb:
Ich hab am Anfang dazu einen Petersen Graphen genommen. Was a=3 darstellt. a=2 wären nur die inneren fünf Knoten des Petersen Graphen.
Ok, das sind jetzt 2 Beispiele, die die Forderung erfüllen.
Für alle a>3 hab ich jetzt wie bei a=2 fünf neue Knoten ergänzt, diese intern wieder so wie beim Petersen Graphen verbunden und dann mit den restlichen bereits vorhandenen Knoten.
Das müsstest Du nochmal genauer beschreiben. Aber ich vermute mal, dass Du da irgendwo 'nen kleinen Kreis erzeugst.
-
SG1 schrieb:
Antoras schrieb:
Was anderes ist mir jetzt nicht aufgefallen. Einen Weg wie man einen Graphen durch a²+1 Knoten mit je a Kanten darstellen kann hab ich nicht gefunden.
Mal vorweg: Das sollst Du ja auch gar nicht. Du sollst zeigen: Wenn Du einen Graphen wie in der Aufgabenstellung (also mit einem bestimmten Mindestgrad und ohne Kreise der Länge 3 oder 4) hast, dann besitzt er mindestens a²+1 Knoten.
Ok, ich soll nicht zeigen wie der Graph aussieht, sondern dass einer existiert. Aber wenn ich mir einen Graphen graphisch herleiten kann, dann fällt mir vermutlich auch ein Weg ein wie ich zeigen kann, dass er existiert.
SG1 schrieb:
Für alle a>3 hab ich jetzt wie bei a=2 fünf neue Knoten ergänzt, diese intern wieder so wie beim Petersen Graphen verbunden und dann mit den restlichen bereits vorhandenen Knoten.
Das müsstest Du nochmal genauer beschreiben. Aber ich vermute mal, dass Du da irgendwo 'nen kleinen Kreis erzeugst.
Du hast recht, ich hab jetzt einen kürzeren Zyklus gefunden. Jetzt weiß ich wieder nicht weiter.
-
SG1 schrieb:
Das müsstest Du nochmal genauer beschreiben. Aber ich vermute mal, dass Du da irgendwo 'nen kleinen Kreis erzeugst.
Jo, einen Kreis der Länge 4, wenn man sich zwei Nachbarn in einem Ring anschaut und dann denn Ring drüber mit reinnimmt.
-
Antoras schrieb:
SG1 schrieb:
Antoras schrieb:
Was anderes ist mir jetzt nicht aufgefallen. Einen Weg wie man einen Graphen durch a²+1 Knoten mit je a Kanten darstellen kann hab ich nicht gefunden.
Mal vorweg: Das sollst Du ja auch gar nicht. Du sollst zeigen: Wenn Du einen Graphen wie in der Aufgabenstellung (also mit einem bestimmten Mindestgrad und ohne Kreise der Länge 3 oder 4) hast, dann besitzt er mindestens a²+1 Knoten.
Ok, ich soll nicht zeigen wie der Graph aussieht, sondern dass einer existiert. Aber wenn ich mir einen Graphen graphisch herleiten kann, dann fällt mir vermutlich auch ein Weg ein wie ich zeigen kann, dass er existiert.
Wenn Du einen Graphen beschreiben kannst, ist das ein Existenzbeweis. Aber auch der ist nicht gefragt, sondern eine Aussage über ALLE Graphen mit den Eigentschaften aus der Aufgabenstellung.
-
Antoras schrieb:
Ok, ich soll nicht zeigen wie der Graph aussieht, sondern dass einer existiert.
Nein, du sollst zeigen, dass alle Graphen, die die erste Eigenschaft erfüllen, die zweite Eigenschaft ebenfalls erfüllen (also mindestens a^2 + 1 Knoten haben). Wie viele Graphen das letztendlich sind (und ob es überhaupt solche Graphen gibt), ist egal.
-
Ok, ich glaube ich hab jetzt verstanden was gemacht werden soll. Trotzdem hab ich noch nicht verstanden wie ich die Aufgabe angehen soll. Die erste Eigenschaft ∀ x ∈ V : d(x) ≥ a bekomme ich graphisch für einfach a>3 nicht gelöst. Und sonst fällt mir nichts ein wie ich die Aufgabe noch angehen könnte.
-
Antoras schrieb:
Die erste Eigenschaft ∀ x ∈ V : d(x) ≥ a bekomme ich graphisch für einfach a>3 nicht gelöst.
Wo liegt das Problem? Jeder Knoten hat einfach a Nachbarn. Du brauchst auch keinen keinen Graphen zu zeichnen. Nimm doch einfach an, dass die Aussage gilt.
Edit: Spoiler: Ich hab die Lösung hier aufgeschrieben: http://ideone.com/kK37s
-
Also, darauf wäre ich jetzt nie gekommen. Das ist so einfach, ich kann gar nicht glauben, dass das als Beweis zählt.
In der Uni wird einem immer nur beigebracht abstrakt und strukturiert zu denken, das einfache Denken lässt sich da nicht blicken.
-
Uni KA 1. Semester Info?
