Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » 4-regulärer Streichholzgraph mit 88 Kanten und 44 Knoten
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich 4-regulärer Streichholzgraph mit 88 Kanten und 44 Knoten
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7923
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2013-05-04


Hallo Leute,

ich glaube einen 4-regulären Streichholzgraphen gefunden zu haben, der mit weniger Kanten und Knoten als der bekannte Harborth-Graph (104 Kanten, 52 Knoten) auskommt. Er besitzt 88 Kanten und 44 Knoten.

Ich dachte, wenn es einen kleineren solchen Graphen gibt, dann muss er unsymmetrisch sein. Also habe ich mir ein Graphen-Konstruktions-System aus Metallschrauben und Schnellhefter-Streifen überlegt, dass sich auf einer Tischplatte leicht verschieben lässt (Materialkosten unter 7 Euro). Ich habe dann aus Grundelementen, die aus vier gleichseitigen Dreiecken bestehen einen Kreis gebildet, den Kreis aufgebrochen und so lange und mit neuen Elementen kombiniert und verschoben, bis es passte. Das Ganze hat keine Stunde gedauert.

Ich habe die Geometrie des Graphen allerdings noch nicht schriftlich bewiesen, sollte aber wohl stimmen. Das erste Bild zeigt mein Original, das zweite die graphische Darstellung mit gefärbten gleichseitigen Dreiecken.

Winkler-Graph Original
Winkler-Graph Zeichnung

Gute Nacht und viele Grüße,

Slash



-----------------
Bound to be disappointing so why wait?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3571
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2013-05-04


Hallo Slash,
meine Vermutung lautet, dass die beiden innersten Punkte zusammenfallen müssen, wenn der Aufbau mit wirklich gleichlangen Kanten ohne Toleranzen an den Knotenpunkten erfolgt.

Viele Grüße,
  Stefan



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7923
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2013-05-06


Hallo Stefan,

du hast Recht, eine Überprüfung mit einem CAD-Programm hat genau dies ergeben. Da ist mein System doch nicht starr genug. Zumal ich oben rechts einen dummen Fehler gemacht habe. (Bild roter Kreis) Das kann natürlich nicht funktionieren mit einem 180 Grad Winkel.

Bildbeschreibung

Gruß, Slash



-----------------
Bound to be disappointing so why wait?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7923
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2013-05-10


Hallo,

ich schreibe gerade an einem Artikel über reguläre Streichholzgraphen. Darin soll gezeigt werden, dass der Harborth-Graph der minimalste 4-reguläre ist. Ich postuliere darin vor allem die Symmetrie einer minimalen Lösung, doch bei der Konstruktion eines unsymmetrischen Gegenbeispiels bin ich auf das hier gestoßen.

Bildbeschreibung

Das Interessante ist, dass mein Graph alle Minimalitätskriterien aufweist, die auch der Harborth-Graph besitzt, allem voran einen inneren Kreis aus acht Kanten, nur ist er eben nicht symmetrisch.

Was haltet Ihr davon?

Gruß, Slash



-----------------
Bound to be disappointing so why wait?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
chryso
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.02.2009
Mitteilungen: 10529
Aus: Österreich
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2013-05-10


Hallo Slash!

Nimm einmal das südwestliche Trapez (an das dein rosa Vieleck stößt.)
Dieses wird von zwei weißen Vierecken begrenzt.
Das müssten Rauten sein.

Rein optisch schaut es aber nicht so aus.

LG chryso



-----------------
Die deutsche Rechtschreibung ist Freeware, sprich, du kannst sie kostenlos nutzen.
Allerdings ist sie nicht Open Source, d.h. du darfst sie nicht verändern oder in veränderter Form veröffentlichen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7923
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2013-05-12


Hallo Chryso,

nach langen Stunden zeichnen und basteln zeigt mein CAD-Papier-Stecknadelmodell genau an dieser Stelle (roter Kreis) den Fehler. Man kann den Fehler aber auch im Umfeld verschieben. Letzten Endes passt es nie.

Bildbeschreibung


Der Graph besitzt übrigens drei große "starre" Untergraphen, was mir erst später aufgefallen ist.

Bildbeschreibung

Gruß, Slash


[ Nachricht wurde editiert von Slash am 12.05.2013 20:38:50 ]


-----------------
Bound to be disappointing so why wait?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7923
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2014-03-21


Hi,

ich habe heute mal wieder mit 4-regulären Streichholzgraphen gespielt und möchte an dieser Stelle meine Ergebnisse präsentieren.

Ob alle diese Graphen wirklich geometrisch existieren sei hier zur Diskussion gestellt. Meine Modelle sind leider nicht starr genug.

Drei Graphen mit 108 Kanten und 54 Knoten.


Graph mit 106 Kanten und 53 Knoten.


Graph mit 104 Kanten und 52 Knoten. Dieser Graph könnte ein langgesuchter Bruder des Harborth-Graphen sein.


Graph mit 102 Kanten und 51 Knoten. Dieser unsymmetrische Graph ist sogar minimaler als der Harborth-Graph, allerdings sehe ich seine Existenz selbst sehr kritisch.


Gruß, Slash


-----------------
Bound to be disappointing so why wait?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7923
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2014-03-21


Vielleicht könnte einer der Graphen mit 108 Kanten existieren. Bei den anderen bin ich jetzt sehr skeptisch, zumal bei den kleineren Graphen nur ein Winkel die gesamte Geometrie zu bestimmen scheint, da die Seiten wegen der Symmetrie im rechten Winkel bzw. gegenüberliegende Seiten parallel zueinander stehen müssen.


Gruß, Slash


-----------------
Bound to be disappointing so why wait?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7923
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2014-03-22


So, habe jetzt die Winkel berechnet und mit CAD gezeichnet.

Ergebnis: unmögliche Geometrie

Genau eine Kante ist zu kurz bei möglichen Winkeln. Wegen der zweifachen Achssymmetrie sind es natürlich insgesamt vier Kanten.

Wenn alle Winkel und Längen stimmen, dann überschneiden sich die mittleren Dreiecke, da der seitliche Winkel nur noch ca. 1 Grad beträgt.


Der Graph mit 106 Kanten ist dann wohl auch nicht möglich.

Gruß, Slash


-----------------
Bound to be disappointing so why wait?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3571
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2014-03-22


fed-Code einblenden


   




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7923
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2014-03-22


Hi Stefan,

danke fürs Nachrechnen. Ich hätte statt "Winkel berechnet" besser "mit Winkelbeziehungen grob abgeschätzt" sagen müssen. So kommen die Unterschiede zu stande.

Ich wußte nicht, wie ich das einzelne gleichseitige Dreieck mit einbeziehen sollte.

Gruß, Slash


-----------------
Bound to be disappointing so why wait?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3571
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2014-03-23


fed-Code einblenden



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3571
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2014-10-04


Hallo Slash, ich habe jetzt die Graphen aus Beitrag No.6 näherungsweise ausgerechnent. Es sind leider keine brauchbaren Ergebnisse dabei. Als ideales Fachwerk betrachtet muss der Graph die notwendige Bedingung 2k=s+3 (k=Anzahl Knoten, s=Anzahl Stäbe) erfüllen, um statisch bestimmt zu sein. Nur dann gibt es keine beweglichen Bestandteile und es treten auch keine Verformungen auf, wenn Teile wegen geringfügiger Längenabweichung nicht richtig zusammenpassen. Für den Harborth-Graph gilt aber stets 2k=s. Deshalb habe ich versucht, je drei Stäbe (rot gezeichnet) so herauszunehmen, dass ein statisch bestimmter Graph übrigbleibt. Wenn ich noch weitere Stäbe entferne (grün gezeichnet), zerfällt der Graph in zueinander bewegliche Teile. Diese Bewegungsmöglichkeit sind als blaue Winkel dargestellt. Die blauen Winkel habe ich dann mit einem Gleichungssystem so bestimmt, dass die Abstände für die grünen Stäbe passen und diese eingesetzt werden können. Für die roten Stäbe bleibt schließlich keine Variationsmöglichkeit mehr übrig und man muss die Abstände nehmen so wie sie sind. Das habe ich für alle Graphen aus Beitrag No.6 ausgeführt und es ist kein Graph dabei, wo die roten Abstände wenigstens annähernd passen. Falls sich doch noch eine Lösung findet, wo auch die roten Stäbe fast die geforderte Länge haben, muss natürlich ein anderes Verfahren für den Beweis verwendet werden. Leider ist das Programm zu unhandlich, um damit schnell neue Varianten zu finden. Für eine systematische Suche könnte man auch verwenden, dass vermutlich der Harbortgraph immer von Trapezen aus starr miteinander verbundenen Dreiecken eingerahmt ist, zum Beispiel im Themenstart 5+3+3+3+3+3+3 Dreiecke. Dann könnte man verschiedene solche Zerlegungen nach der Summe der Dreiecke sortieren und der Reihe nach untersuchen, ob sie im Inneren zu einem Harborth-Graph fortgesetzt weren können. Aber erstmal die jetzigen Ergebnisse:

fed-Code einblenden



fed-Code einblenden




fed-Code einblenden


fed-Code einblenden




fed-Code einblenden



fed-Code einblenden



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7923
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2014-10-05


Wow! Erstmal danke für diese arbeitsintensiven Überlegungen. Ich habe mich die letzte Zeit nicht mehr damit beschäftigt, obwohl ich noch einen Artikel zum Thema in Arbeit habe. Ich habe u.a. einen Algorithmus in Planung, der von einem "äußeren Kreis oder Hülle" ausgehend die Innenfläche füllt. Es gibt nämlich nur eine Handvoll solcher Kreishüllenkonstruktionen die für einen kleineren als den Harborth-Graphen in Frage kommen.

Gruß, Slash


-----------------
Bound to be disappointing so why wait?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]