Stammtisch & Kaffeekranzerl

    Zitat von Hohli

    Na super, du solltest doch zeigen, dass es keinen gibt und wenn doch, dann solltest du zeigen, wie er aussieht ;) Dennoch ist deine Aussage nicht korrekt, es existiert kein Hamiltonkreis. Das kriegt man allein durch ein paar mal rumprobieren raus (Haus vom Nikolaus halt). Man sieht auch sehr schnell, dass die zwei disjunkten Knotenmengen einmal das Pentagon, und einmal das Pentagram ist - und die sind nun mal ungerade, was also deiner Aussage widerspricht. Dann wiederum....


    Und jetzt lasst uns mal bitte aufhören so zu tun, als hätten wir von Graphentheorie Ahnung, ich nämlich absolut nicht :P

    Dann zeig es halt konkret 😅 Bzw. den Beweis, und wiederlege, was ich geschrieben habe, ich will doch was lernen🥴

    Zitat von JonnyBadFox

    Dann zeig es halt konkret 😅 Bzw. den Beweis, und wiederlege, was ich geschrieben habe.

    Siehe Verlinkung von mir:


    Zitat

    To see that the Petersen graph has no Hamiltonian cycle C, consider the edges in the cut disconnecting the inner 5-cycle from the outer one. If there is a Hamiltonian cycle, an even number of these edges must be chosen. If only two of them are chosen, their end-vertices must be adjacent in the two 5-cycles, which is not possible. Hence 4 of them are chosen. Assume that the top edge of the cut is not chosen (all the other cases are the same by symmetry). Of the 5 edges in the outer cycle, the two top edges must be chosen, the two side edges must not be chosen, and hence the bottom edge must be chosen. The top two edges in the inner cycle must be chosen, but this completes a non-spanning cycle, which cannot be part of a Hamiltonian cycle. Alternatively, we can also describe the ten-vertex 3-regular graphs that do have a Hamiltonian cycle and show that none of them is the Petersen graph, by finding a cycle in each of them that is shorter than any cycle in the Petersen graph. Any ten-vertex Hamiltonian 3-regular graph consists of a ten-vertex cycle C plus five chords. If any chord connects two vertices at distance two or three along C from each other, the graph has a 3-cycle or 4-cycle, and therefore cannot be the Petersen graph. If two chords connect opposite vertices of C to vertices at distance four along C, there is again a 4-cycle. The only remaining case is a Möbius ladder formed by connecting each pair of opposite vertices by a chord, which again has a 4-cycle. Since the Petersen graph has girth five, it cannot be formed in this way and has no Hamiltonian cycle.

    Ich maße mir nicht an die reichhaltigen und in sich komplexen Definitionen in der Graphentheorie zu kennen. Die Erklärung ist aber dennoch durchaus nachvollziehbar, wenn man einen bisschen Erfahrung mit dem ein oder anderen mathematischen Bereich hat (Gruppentheorie und Symmetrieoperationen aus der Kristallographie haben mir hier geholfen).


    Alles nicht so leicht, aber durchaus interessant wenn es darum geht einen effizienten Hamiltonian Cycle zu programmieren, wenn man DHL liefrant ist und jede Kante auch noch eine andere Gewichtung hat. Da heißt es dann nicht finde “einen“ sonder n “den Weg mit der geringsten Gewichtung“. Bei über 500 Knoten schon gar nicht so easy, das mit der Hand nachzuzeichnen ;)

    Zitat von Hohli

    Siehe Verlinkung von mir:


    Ich maße mir nicht an die reichhaltigen und in sich komplexen Definitionen in der Graphentheorie zu kennen. Die Erklärung ist aber dennoch durchaus nachvollziehbar, wenn man einen bisschen Erfahrung mit dem ein oder anderen mathematischen Bereich hat (Gruppentheorie und Symmetrieoperationen aus der Kristallographie haben mir hier geholfen).


    Alles nicht so leicht, aber durchaus interessant wenn es darum geht einen effizienten Hamiltonian Cycle zu programmieren, wenn man DHL liefrant ist und jede Kante auch noch eine andere Gewichtung hat. Da heißt es dann nicht finde “einen“ sonder n “den Weg mit der geringsten Gewichtung“. Bei über 500 Knoten schon gar nicht so easy, das mit der Hand nachzuzeichnen ;)

    Ja ok. Bipartit aber die disjunken Mengen sind ungerade (die Anzahl). Ok, das reicht auch schon als Beweis, das es keinen gibt. Thx 👍 Aber wenigstens hab ich nicht abgeschaut nä nä nä;) Wär cooler, wenn du es mir mit deinen eigenen Ideen erklärt hättest. Wir sind ja alle schon so gewöhnt, alles im Internet zu finden. Aber egal.

    Zitat von Marner

    Hab mich nur kurz eingelesen, wäre das Haus nicht ein Eulerkreis, mit der Vorgabe jede Kante genau einmal zu durchlaufen, während beim Hamiltonkreis nicht jede Kante aber jeder Knoten einmal (Anfangsknoten am ende wieder) angelaufen wird?

    Das ist schon richtig, allerdings ging's mir in dem Punkt nur darum, wie ich das Problem zunächst lösen wollte - und das ist bei mir zuerst halt immerzu wild drauflosprobieren.

    Zitat von JonnyBadFox

    Ja ok. Bipartit aber die disjunken Mengen sind ungerade (die Anzahl). Ok, das reicht auch schon als Beweis, das es keinen gibt. Thx 👍 Aber wenigstens hab ich nicht abgeschaut nä nä nä;) Wär cooler, wenn du es mir mit deinen eigenen Ideen erklärt hättest. Wir sind ja alle schon so gewöhnt, alles im Internet zu finden. Aber egal.

    Ja, bei mir war's halt 'ne starke Vermutung nach mehr oder weniger viel Trial and Error. Da es sich da auch um 'ne sehr symmetrische Angelegenheit handelt kannst du dir ja im Prinzip auch direkt viele mögliche Startansätze sparen (jeder äußerer und jeder innerer Knoten ist jeweils identisch). Wir kennen ja aus der Kindheit ja auch alle das Problem mit E-Werk, Gaswerk und Wasserwerk, die alle mit drei Häusern verknüpft werden müssen. Da hat dir nach stundenlangem ausprobieren als Kind schon dein gesunder Menschenverstand gesagt “geht nicht“, aber hier eine mathematische Beweisführung zu vollziehen ist dann ungleich schwieriger. Nichtsdestotrotz lässt sich das Problem mit den drei Häusern und den drei Werken ja in Ansätzen auf unser Problem hier übertragen. Aber wie gesagt, die Mathematik dahinter ist mit dem Ende des 19. Jahrhunderts noch relativ jung - und die (wirklich vorwiegend) Jungs waren schon lange davor ziemlich abgespaced drauf, was so etwas anbetrifft. Siehe auch Beweisführung zur Unmöglichkeit der Quadratur des Kreises ||


    https://twitter.com/DLFNachric…tatus/1368111348656259077


    Zitat von Marner

    Hab mich nur kurz eingelesen, wäre das Haus nicht ein Eulerkreis, mit der Vorgabe jede Kante genau einmal zu durchlaufen, während beim Hamiltonkreis nicht jede Kante aber jeder Knoten einmal (Anfangsknoten am ende wieder) angelaufen wird?

    Für Normies ist es dasselbe.

    Dachte nach der Recherche, dass dieses eulerische Brückenproblem ganz nett ist eig.

    Zitat von JckProtoRogge1.1

    https://twitter.com/DLFNachric…tatus/1368111348656259077

    Der VT-affine (no pun intended) Teil in mir fragt sich, ob es dabei nur um den Schutz der Tiere geht, wenn eigentlich weltweit noch Versorgungslücken bei den Human-Impfstoffen existieren. Andererseits ist da natürlich auch Max Uthoff mit dem Katzenfutter.

    🕊 Lumpenpazifisten und Friedensschwurbler aller Länder, vereinigt euch! 🕊

    https://twitter.com/OlafStorbeck/status/1367940096952000517

    Erst dachte ich auch- geht's nich?

    Sollte man nicht erstmal alle Menschen geimpft haben?

    Aber es ist ja von den Menschen unabhängige Imoferei- und vermutlich ziemlich klug das zu machen- damit das Virus nicht hin-und her-spaziermutiert.

    Zitat von Hohli

    Ja, bei mir war's halt 'ne starke Vermutung nach mehr oder weniger viel Trial and Error. Da es sich da auch um 'ne sehr symmetrische Angelegenheit handelt kannst du dir ja im Prinzip auch direkt viele mögliche Startansätze sparen (jeder äußerer und jeder innerer Knoten ist jeweils identisch). Wir kennen ja aus der Kindheit ja auch alle das Problem mit E-Werk, Gaswerk und Wasserwerk, die alle mit drei Häusern verknüpft werden müssen. Da hat dir nach stundenlangem ausprobieren als Kind schon dein gesunder Menschenverstand gesagt “geht nicht“, aber hier eine mathematische Beweisführung zu vollziehen ist dann ungleich schwieriger. Nichtsdestotrotz lässt sich das Problem mit den drei Häusern und den drei Werken ja in Ansätzen auf unser Problem hier übertragen. Aber wie gesagt, die Mathematik dahinter ist mit dem Ende des 19. Jahrhunderts noch relativ jung - und die (wirklich vorwiegend) Jungs waren schon lange davor ziemlich abgespaced drauf, was so etwas anbetrifft. Siehe auch Beweisführung zur Unmöglichkeit der Quadratur des Kreises ||


    Bei diesen mathematischen Aufgaben (oder Beweisen) ist es oft so, dass sie auf den ersten Blick kompliziert aussehen oder die Lösung nicht offensichtlich ist, meistens ist es dann aber so, dass es Theoreme gibt,

    die allgemeine Aussagen über das Problem in der Aufgabe machen. Ich würde immer erst versuchen, an irgendwelche einfachen und eleganten Lösungen zu denken. Mein erster Gedanke war eigentlich mehr soziologisch 😅: Ich hab vermutet, dass der Aufwand, das Problem per Hand zu lösen, wahrscheinlich sehr groß ist und es sehr wahrscheinlich eine viel einfachere Lösung gibt. Dann hab ich versucht Theoreme der Graphentheorie zu finden, die über sowas allgemeine Aussagen machen. Eine weitere Vermutung von mir, war, dass kein Hamiltonkreis existiert, weil das Zeigen der Nichtexistenz wahrscheinlich viel einfacher ist als den konkreten Kreis zu finden.


    Den Beweis hast du ja aber schon geliefert: Der Graph lässt sich in zwei disjunkte Mengen, einmal die Knotenpunkte des Pentagrams und einmal des Pentagons, aufteilen und als bipartiter Graph zeichnen. Da die Elemente beider disjunkter Mengen ungerade sind, existiert kein Hamiltonkreis (bei bipartiten Graphen). Ein erster Blick auf das Bild hätte ausgereicht, um das Problem zu lösen (wenn man keinen Fehler dabei macht 🥴). Also ist der Lösungsweg sehr viel einfacher. (Man hätte auch ein Programm schreiben können, um über den Deph First Transveral Algorithmus (brute force) den Kreis zu finden, oder eben nicht.)

    Und ich denke, dass ist bei den meisten Problemen in der Mathematik so (das sie eher "leicht" zu lösen sind).


    Mathematiker sind faul ;) Sie haben keine Lust jeden Graph nachzumalen, daher versucht man allgemeine Theoreme zu finden. Das deckt sich auch mit dem verbreiteten Denken in der Mathematik und Physik: Einfachheit und Eleganz, oder "Schönheit" werden bevorzugt und absichtlich konstruiert. Eben weil in der Vergangenheit immer die "schönsten" Lösungen auch zu Fortschritt geführt haben und auch physikalische Theorien, die als schön gelten, zufällig oder nicht, den meisten Erfolg haben. Auf zum nächsten Problem ;)


    Jack hat noch ein Problem zu Homotopiegruppen und Kategorientheorie gepostet, ein harter Brocken ;D aber nichts ist unmöglich und ich denke auch, dass die Lösung dazu sehr "einfach" im Sinne von elegant ist. Bei der Aufgabe mit den Reihen war es ja auch so, in der Formelsammlung schauen hat gereicht. Das ist ja auch das tolle an Mathematik und Physik, man muss outside the box denken.

Jetzt mitmachen!

Du hast noch kein Benutzerkonto auf unserer Seite? Registriere dich kostenlos und nimm an unserer Community teil!

Benutzerkonto erstellen Anmelden