Graphentheorie: Anzahl von Knoten beweisen
-
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?
