300000
Spinnennetz©
Gesamtzahl der Siege: 156965
| (6 – 20): | Kreis Pfad Zufällig Herausforderung |
Definitionen + Inwiefern ist das immer noch ein "Mathe"-Spiel?
Die Diagramme in diesem Spiel basieren auf einem Gebiet der Mathematik, das als Graphentheorie bekannt ist!
Was ist ein Graph?
Graph: Ein Graph besteht aus Knoten und Kanten.
Knoten: Die "Objekte", die ein Graph verbindet, werden als Knoten bezeichnet. In Spinnennetz-Spiel sind Knoten die Kreise.
Kante: Eine Kante ist eine Verbindung im Graphen zwischen zwei Knoten. In Spinnennetz-Spiel sind die Kanten Linien.
Erweitern eines Pfads
Pfad: Ein Pfad ist eine Sequenz verbundener Kanten mit einem Start- und einem Endknoten.
Eulerscher Pfad: Dies ist ein Pfad, der jede Kante im Graphen genau einmal verwendet.
Das Ziel in diesem Spiel ist es, einen Eulerschen Pfad zu finden.
Was sind Eulersche Pfade im Alltag?
Ein Schneepflug, ein Straßenreinigungswagen und ein Postbote sind Beispiele für Autos und Menschen, die durch jede Straße fahren müssen, aber vermeiden wollen, zweimal durch eine Straße zu fahren.
Kommt dir der Name "Euler" bekannt vor?
Die Graphentheorie entstand, als der Mathematiker Leonhard Euler an solchen Pfaden arbeitete.
Euler schrieb eine Abhandlung über die Sieben Brücken von Königsberg, in der er bewies, dass es unmöglich sei, durch die Stadt zu gehen, indem man jede Brücke genau einmal überquerte.
Klicke auf die Karte des Problems unten, um mehr darüber zu erfahren.
Zyklus: Ein Zyklus ist ein Pfad, der auf dem Knoten endet, auf dem er begonnen hat.
Eulerscher Zyklus: Dies ist ein Eulerscher Pfad, der auch ein Zyklus ist. Wähle "Zyklus" in unserem Spiel oben und die Lösung wird immer ein Eulerischer Zyklus sein!
Anweisungen zu den Spieleinstellungen
In das Textfeld neben Knoten können Sie eine beliebige Zahl zwischen 6 und 20 eingeben. Diese Zahl ist die Anzahl der Knoten, die im Diagramm angezeigt werden. Je größer die Zahl, desto anspruchsvoller wird die Lösung!
Wählen Sie als Nächstes einen Diagrammtyp aus
Zyklus: Gewinnpfade enden immer auf dem Knoten, auf dem sie begonnen haben.
Pfad: Gewinnpfade enden nicht auf dem Knoten, auf dem sie begonnen haben.
Zufällig: Graphen, die einen Eulerschen Zyklus oder einen Eulerschen Pfad zulassen können. Gewinnpfade können auf dem Knoten enden, auf dem sie begonnen haben, müssen es aber nicht.
Herausforderung: Handgefertigte Diagramme, bei denen sich Kanten kreuzen und daher Brücken nicht offensichtlich zu erkennen sind.
Klicken Sie abschließend auf "Neues Web erstellen", um Ihre Änderungen an den Diagrammeinstellungen zu sehen!
Welchen Knoten sollte ich zuerst auswählen?
Grad: Der Grad ist eine Eigenschaft eines Knotens. Es ist die Anzahl der Kanten, die damit verbunden sind. Wir unterscheiden zwischen Knoten mit ungeradem Grad und Knoten mit geradem Grad, abhängig von ihrem Grad.
Verbundener Graph: Ein Diagramm, in dem jedes Knotenpaar über einen Pfad verbunden werden kann.
Brücke: Eine Kante ist eine Brücke, wenn die beiden Enden der Kante nicht anders verbunden werden können. So gelangt man nach dem Überqueren einer Brücke nicht mehr auf die vorherige Seite zurück. Durch das Entfernen einer Brücke wird der Graph in zwei getrennte Komponenten aufgeteilt.
Ungerichteter Graph : Ein Graph, bei dem die Kanten keine Richtung haben. Wir berücksichtigen nur diese in diesem Spiel.
Gerichteter Graph : Ein Graph, in dem jede Kante eine Richtung hat, die wie eine Einbahnstraße angelegt ist.
Ein ungerichteter Graph enthält einen Eulerschen Zyklus, wenn alle Knoten einen geraden Grad haben (Grad 0, 2, 4, 6...) . Für diese Sie können einen beliebigen Knoten als Startknoten auswählen und trotzdem gewinnen. Denken Sie nur daran, dass Sie an dem Knoten enden müssen, von dem aus Sie gestartet sind.
Ein Graph enthält einen Eulerschen Pfad, aber nicht einen Eulerschen Zyklus, wenn genau zwei Knoten einen ungeraden Grad haben (Grad 1, 3, 5, 7...) und alle anderen Knoten haben einen gleichmäßigen Grad. In diesem Fall müssen Sie einen Knoten mit einem ungeraden Grad als Startknoten auswählen oder Sie können den Eulerschen Pfad nicht abschließen.
Warum genau zwei Knoten?
Stellen Sie sich jede Bewegung als "out" des Knotenpunkts vor, von dem Sie gekommen sind, und "rein" zu dem Knoten, zu dem Sie reisen. Die meisten Knoten folgen diesem Kopplungsmuster, sodass sie einen gleichmäßigen Grad haben.
Wenn du das Spiel startest, ist die erste Kante, die du markierst, ein Zug "heraus" aus dem Startknoten. Diese bleibt während des Spiels nicht gekoppelt.
Um einen Eulerschen Zyklus zu erstellen, ist die letzte Kante, die Sie markieren, eine Bewegung "in" zum Startknoten. Dadurch entsteht mit dem ersten Zug ein Paar, d.h. der Startknoten hat einen geraden Grad.
Wenn der Eulersche Pfad des Graphen kein Zyklus ist, ist die letzte Kante, die Sie markieren, eine ungepaarte Bewegung "in" zu einem Knoten, der nicht der Startknoten ist. Der Startknoten verbleibt mit einem ungeraden Grad, und der Endknoten hat ebenfalls einen ungeraden Grad.
Machen Sie sich keine Sorgen um andere Fälle. Wenn die Anzahl der Knoten mit einem ungeraden Grad nicht genau 0 oder 2 wäre, gäbe es keine Eulerschen Pfade und keine Eulerschen Zyklen, was bedeutet, dass es keine Möglichkeit gibt, zu gewinnen. Solche Diagramme sollten in diesem Spiel nicht vorkommen.
Einleitende Fragen
Kann es eine ungerade Anzahl von Knoten mit einem ungeraden Grad geben?
Nein.
Warum?
Beweis:
Das Zählen aller Enden aller Kanten ergibt die gleiche Zahl wie das Addieren aller Grade aller Knoten, einverstanden?
Da jede Kante 2 Enden hat, muss die Gesamtzahl der Enden aller Kanten gerade sein. (Das Addieren von geraden Zahlen ergibt eine gerade Zahl.)
Um die Grade aller Knoten zu addieren, würde man die geraden Grade addieren, was eine gerade Zahl ergibt, und die ungeraden Grade addieren.
Wenn es eine ungerade Anzahl von Knoten mit ungeraden Graden gäbe, wäre diese Summe ungerade und dann gerade + ungerade = ungerade, so dass die Gesamtzahl der Grade ungerade wäre. Aber es ist gleich der Gesamtzahl aller Enden aller Kanten, und das ist gerade. Daher kann die Anzahl der Knoten ungeraden Grades nicht ungerade, sondern gerade sein.
1 ist z. B. eine ungerade Zahl, d. h., es gibt keinen Graphen mit nur 1 Knoten ungeraden Grades.
Wann gibt es einen Eulerschen Pfad oder Zyklus?
Wenn ein Knoten einen geraden Grad hat, d.h. 2, 4, 6,... Kanten werden an den Knoten angehängt, und wenn man dann an diesem Knoten ankommt, bleibt eine ungerade Anzahl ungenutzter Kanten übrig, die größer als Null ist, so dass man diesen Knoten verlassen und weitermachen kann. Wenn der Grad ungerade ist, d.h. 1, 3, 5,.. Kanten angehängt werden, dann muss man entweder den Pfad an diesem Knoten beginnen oder der Pfad endet an diesem Knoten. Da ein Pfad nur 2 Enden hat, kann es nur 2 Knoten mit ungeradem Grad geben. Deshalb:
Um einen Eulerschen Zyklus zu haben, muss ein Graph nur Knoten mit geradem Grad haben, und um einen Eulerschen Pfad zu haben, muss er 2 Knoten ungeraden Grades haben, ein Knoten ist der Anfang und einer ist das Ende des Pfades.
Wie findet man einen Eulerschen Pfad oder Zyklus?
Wie oben gezeigt, kann man, wenn es keine Knoten mit ungeradem Grad gibt, an einem beliebigen Knoten beginnen und wird am selben Knoten enden. Wenn es genau 2 Knoten mit ungeradem Grad gibt, dann muss einer an einem dieser 2 Knoten beginnen und endet automatisch am anderen.
Kann beim Verlängern des Weges etwas schief gehen?
Ja, irgendetwas kann schief gehen. Beispiel:
2 4 / \ / \ 1---3---5
Der Grad aller Knoten ist 2, mit Ausnahme von Knoten 3, der den Grad 4 hat. So sind alle Abschlüsse gerade und wir können überall anfangen. Beginnen wir mit Knoten 1 und gehen wir zu Knoten 3 und lassen wir alle Kanten fallen, die durchlaufen wurden.
2 4 / \ / \ 1 3---5
Die Kante 3-2 wird zur Brücke. Wenn Sie diese Kante 3-2 kreuzen und entfernen, entsteht ein getrennter Graph
2 4 / / \ 1 3---5
die nicht mehr vollständig durchquert werden können. Daher sollte man von 3 auf 4 oder 5 fortfahren, um den Eulerschen Zyklus zu vervollständigen.
Wie kann man das Überqueren einer Brücke verhindern?
Um zu überprüfen, ob es sich bei einer Kante um eine Brücke handelt, würde man an einem Ende der Kante beginnen und alle Nachbarknoten und alle Nachbarn besuchen und so weiter. Wenn man nicht auf die andere Seite der Kante kommt, dann ist die Kante eine Brücke. Eine solche vollständige Suche nach allen Nachbarn ist nicht sehr teuer. Aber wenn man es tun muss, bevor man jede Kante überquert, dann ist der Gesamtaufwand groß. Der vollständige Algorithmus wird als Fleury-Algorithmus bezeichnet und stammt aus dem Jahr 1883.
Gibt es einen effizienteren Algorithmus?
Ein effizienterer Algorithmus ist der von Hierholzer (1873).
Wenn der Graph 2 Knoten ungeraden Grades hat, dann findet man einen Pfad oder einen Zyklus, in beiden Fällen sehr schnell, ohne auf Brücken zu prüfen.
1) Nach dem Entfernen aller verwendeten Kanten ist der Grad der verbleibenden unbenutzten Kanten für alle Knoten gerade.
Warum?
Wenn der Grad eines Knotens gerade war, dann wurde er genauso oft angefahren, wie er verlassen wurde, also ist er immer noch gerade. Wenn der Grad ungerade war, dann ist es entweder der Startknoten oder der Endknoten des ersten Pfades und dann wurde er insgesamt eine ungerade Anzahl von Malen belassen + angefahren, so dass der verbleibende Grad ungerade ist − ungerade = gerade.
2) Es muss mindestens ein Knoten mit verwendeten und unbenutzten angrenzenden Kanten vorhanden sein.
Warum?
Weil der ursprüngliche Graph verbunden war.
Wegen 1) kann man einen Zyklus von unbenutzten Kanten finden, der an diesem Knoten beginnt und endet. Aufgrund von 2) kann dieser Zyklus in den ersten Pfad/Zyklus aufgenommen werden, wenn er diesen Knoten erreicht. Dieses Einbetten von Zyklen bisher ungenutzter Kanten wird so lange wiederholt, bis alle Kanten aufgebraucht sind und man somit einen Eulerschen Pfad oder Eulerschen Zyklus hat, der alle Kanten nutzt.
Wie hoch ist der Preis für diese schnellere Version?
Man muss sich an den vorherigen Pfad/Zyklus erinnern, damit man den zusätzlichen Zyklus einbeziehen kann.
Beispiel:
2 4 / \ / \ 1---3---5
Der erste Zyklus sei 1-3-2-1. Knoten 3 tritt in diesem Zyklus und im ungenutzten Zyklus 3-4-5-3 auf. Wir fügen es in den ersten Zyklus ein und erhalten den Zyklus 1-3-4-5-3-2-1. Es gibt keine unbenutzten Kanten mehr, also endet der Algorithmus hier, wir haben den Eulerschen Zyklus gefunden.
Wie kann ein Zyklus über unsere Schnittstelle eingefügt werden?
Man kann auf "Rückgängig" klicken, bis man den letzten Knoten erreicht hat, der benutzte und ungenutzte Kanten hat, wie Knoten 3 oben, und dann den Zyklus 3-4-5-3 durchlaufen und dann mit den unerledigten Kanten fortfahren.
Wenn es einen Knoten mit ungeradem Grad gibt, muss man dann beide finden, um einen ersten Pfad von einem zum anderen zu zeichnen?
Nein. Wenn man nur einen findet, dann kann man den Pfad an diesem Knoten beginnen und man landet automatisch am anderen Knoten ungeraden Grades, egal ob man alle Kanten nutzt oder nicht.
Warum?
Denn wenn man auf einem Knoten mit geradem Grad ankommt, dann wurde eine ungerade Anzahl von angehängten Kanten verwendet.
Warum?
Jedes Mal, wenn man an einem Knoten ankam, verließ man auch den Knoten, so dass eine gerade Anzahl von Kanten verwendet wird. Jetzt kommt man an und verwendet eine Kante auf einem Knoten mit geradem Grad. Man hat also insgesamt eine ungerade Anzahl von Kanten auf dem Knoten des geraden Grades verwendet.
Gerade − ungerade = ungerade, es bleibt also eine ungerade Anzahl ungenutzter Kanten übrig. Eine ungerade Zahl ist immer ungleich Null, d. h., es gibt mindestens eine ungenutzte Kante, die zum Verlassen dieses Knotens verwendet werden kann. Daher endet man automatisch am Knoten mit ungeradem Grad, unabhängig davon, ob alle Kanten verwendet wurden oder nicht.
Haben Sie einen Vorschlag, wie man einen Knoten mit ungeradem Grad finden kann?
Man könnte natürlich den Grad jedes Knotens überprüfen, bis man einen Knoten mit ungeradem Grad findet. Hier ist ein Weg ohne Zählen.
Man kann sich einen beliebigen Knoten aussuchen. Wenn sein Grad ungerade ist, dann hat man einen gefunden. Wenn nicht, dann beginnt man an diesem Knoten, um einen Zyklus zu zeichnen. Er endet entweder an einem ungeraden Gradknoten, dann hat man einen ungeraden Gradknoten gefunden, oder man endet am Startknoten. Wenn ja, dann ignoriert man alle verwendeten Kanten und macht das erneut, d.h. einen Knoten auswählen und einen Pfad oder Zyklus zeichnen. Das geht so lange, bis man entweder einen Knoten mit ungeradem Grad findet oder keine unbenutzten Kanten mehr vorhanden sind. Dann haben alle Knoten einen geraden Grad.
Was ist, wenn der Graph wie eine Stadt mit Einbahnstraßen ist?
Ein Graph mit Kanten, die nur in eine Richtung durchlaufen werden können, wird als gerichteter Graph bezeichnet. Nach der obigen Argumentation sind die folgenden 2 Aussagen plausibel.
Ein gerichteter Graph ermöglicht einen Eulerschen Zyklus, wenn für jeden Knoten die Anzahl der ausgehenden Kanten gleich der Anzahl der eingehenden Kanten ist.
Ein gerichteter Graph erlaubt einen Eulerschen Pfad, wenn und nur wenn
• ein Knoten hat eine ausgehende Kante mehr als eingehende Kanten,
• ein Knoten eine eingehende Kante mehr hat als ausgehende Kanten und
• Alle anderen Kanten haben die gleiche Anzahl von ausgehenden und eingehenden Kanten.
Folgen oder abonnieren für Updates: