Kürzester Kreis - Graphentheorie

Erste Frage Aufrufe: 71     Aktiv: 25.10.2021 um 11:04

0

Ich habe mich nun eine ganze Weile schon mit diesem Beweis beschäftigt, komme aber zu einem Widerspruch, da ich nur einen einzigen Graphen finde, bei dem die Formel gilt, bei allen anderen entsteht ein unendlich langer Graph. Ich glaube, ich habe eine Denkfehler. Kann mir irgendjemand seinen Ansatz nennen? 

Diese Frage melden
gefragt

Schüler, Punkte: 14

 
Kommentar schreiben
2 Antworten
0
Einen richtigen Ansatz habe ich nicht. Aber für d=3 habe ich einen Graphen zeichnen können.
Zeichne erst ein Fünfeck. Dann gilt d=2, |V|=2²+1=5. Da gilt es schonmal. Kleiner geht nicht.

Ich versuche mal zu beschreiben, wie Du für d=3 an den Graphen kommst, den ich gefunden habe.

Wenn jetzt d=3 sein soll, dann muss jede Ecke eine zusätzliche Kante bekommen. Mit den vorhandenen Ecken darf diese nicht verbunden werden (Kreis wäre zu klein). Die vorhandenen Ecken haben ja maximal einen Abstand zueinander von 2. Wenn mal also zwei nicht benachbarte Ecken nimmt, dann müssen mindestens zwei weitere Ecken dazukommen, damit der Kreis mindestens eine Länge von 5 hat.
Damit haben die beiden neuen Ecken aber auch nur Grad 2 und brauchen noch eine dritte Kante...
Die beiden neuen Ecken haben zu den beiden noch nicht verwendeten Ecken des ursprünglichen Fünfecks jeweils den Abstand 3, also brauchst Du hier noch jeweils eine Zwischenecke. Damit sind es bisher 9 Ecken.
Die zehnte neue Ecke wird mit den beiden Zwischenecken von gerade verbunden und mit der Ecke vom ursprünglichen Fünfeck, die im ersten Kreis liegt und noch keine dritte Kante hat.

Wenn ich nichts übersehen habe, hat dann dieser Graph 3²+1=10 Ecken und kein Kreis ist kleiner als 5.

Ich habe in mein altes Graphentheorie-Skript aus Uni-Zeiten geguckt, da wurde diese Behauptung nicht bewiesen.
Mein Gefühl sagt mir einerseits, dass Du mit diesem maximalen Abstand von 2 arbeiten musst um die Anzahl neuer Ecken zu begründen, und es riecht nach vollständiger Induktion. Außerdem müsste es in der Vorlesung oder Übung vorher vielleicht bewiesene Sätze geben, die weiterhelfen.

Andererseits habe ich in meinem Skript einen Beweis entdeckt, der auf Wahrscheinlichkeiten basierte - es kann also auch eine ganz andere Beweisidee zum Ziel führen.

Nachbemerkung:
Ich weiß nicht, ob mein beschriebenes Vorgehen auf größere Grade so einfach erweiterbar ist. Der Satz von Cayley (Bestimmung der Anzahl der benannten Bäume mit n Ecken) heißt so, weil der Namensgeber die Behauptung aufstellte, zwei Schritte vorrechnete und dann schrieb "Rest durch Induktion" - das war aber lange nicht so einfach wie er sich das dachte. Die gültigen Beweise kamen erst später bzw. von anderen in anderen Zusammenhängen.
Insofern ist Vorsicht geboten.
Diese Antwort melden
geantwortet

Punkte: 1.72K

 

Erst einmal danke für die ausführliche Antwort. Tatsächlich bin ich fast genauso vorgegangen. Nur bin ich nach einer Weile zu dem Schluss gekommen, wenn ich meinen minimalen Grad erhöhen will, brauche ich zuviele neue Ecke, was wiederum zu einem unendlichen Graphen geführt hatte, wodurch ich auch nur auf einen möglichen kam, für den der Satz gilt. Allerdings weis ich nicht, ob das als Beweis ausreicht.   ─   gunnar0815 24.10.2021 um 22:29

Naja, ich hatte ja schon mal zwei gefunden... der Trick besteht ja darin, dass man eben nicht unbegrenzt neue Ecken erzeugt, sondern die "noch offenen" Ecken in cleverer Weise nutzt. Denn nur so kann die untere Grenze gezeigt werden.   ─   joergwausw 24.10.2021 um 23:44

Kommentar schreiben

0
Dieses Resultat ist in https://www.math.uni-hamburg.de/home/bruhn/papers/GTKap0.pdf
auf S.7, Mitte erwähnt, denn $n_0(d,5)=1+d^2$. Dort ist auch eine Beweisidee erwähnt, mit der man das "leicht" nachweisen kann (mit Distanzklassen).
Mehr weiß ich nicht dazu, ich bin in dem Thema nicht mehr wirklich drin, aber im Internet suchen kann ich schon noch.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 18.7K

 

Dann war ich mit meiner Abstands-Idee ja gar nicht so weit weg... und "leicht" - wie oben mit dem Satz von Cayley erwähnt - ist immer so eine Sache.   ─   joergwausw 24.10.2021 um 23:47

Deshalb die Anführungszeichen, das war ein Zitat aus dem Skript, das ich mir aufgrund Ahnungslosigkeit nicht zu eigen mache.   ─   mikn 25.10.2021 um 00:03

hatte ich schon so verstanden, wie Du es geschrieben hast - mir ging es im wesentlichen darum, dass selbst namensgebende Personen etwas als leicht empfanden - ohne den konkreten Beweis selbst ausprobiert zu haben - der mit dem von ihnen skizzierten "leichten" Ansatz letztlich nicht einmal funktioniert...   ─   joergwausw 25.10.2021 um 11:04

Kommentar schreiben