Artikel

6.3: Euler-Schaltungen


Leonhard Euler diskutierte und verwendete erstmals Euler-Pfade und -Schaltungen im Jahr 1736. Anstatt einen minimalen Spannbaum zu finden, der jeden Knoten eines Graphen besucht, kann ein Euler-Pfad oder eine Euler-Schaltung verwendet werden, um eine Möglichkeit zu finden, jede Kante eines Graphen nur einmal zu besuchen visit Einmal. Dies wäre nützlich, um Parkuhren entlang der Straßen einer Stadt zu überprüfen, die Straßen einer Stadt zu patrouillieren oder Post zuzustellen.

Definition: Euler-Pfad

Ein Pfad, der jede Kante eines zusammenhängenden Graphen einmal und nur einmal durchquert und an verschiedenen Ecken beginnt und endet

Beispiel (PageIndex{1}): Euler-Pfad

Ein Euler-Pfad für den obigen Graphen ist F, A, B, C, F, E, C, D, E, wie unten gezeigt.

Dieser Euler-Pfad durchläuft jede Kante einmal und nur einmal und beginnt und endet an verschiedenen Scheitelpunkten. Dieser Graph kann keinen Euler-Kreis haben, da kein Euler-Pfad an derselben Ecke beginnen und enden kann, ohne mindestens eine Kante mehr als einmal zu überqueren.

Definition: Euler-Schaltung

Ein Euler-Pfad, der am selben Knoten beginnt und endet

Beispiel (PageIndex{2}): Euler-Schaltung

Eine Euler-Schaltung für den obigen Graphen ist E, A, B, F, E, F, D, C, E, wie unten gezeigt.

Dieser Euler-Pfad durchläuft jede Kante einmal und nur einmal und beginnt und endet am selben Scheitelpunkt. Daher handelt es sich auch um eine Euler-Schaltung.

Satz von Euler (PageIndex{1}): Wenn ein Graph Knoten ungeraden Grades hat, kann er keinen Euler-Kreis haben.

Wenn ein Graph zusammenhängend ist und jede Ecke einen geraden Grad hat, dann hat er mindestens einen Eulerkreis (normalerweise mehr).

Satz von Euler (PageIndex{2}): Wenn ein Graph mehr als zwei Ecken ungeraden Grades hat, kann er keinen Euler-Pfad haben.

Wenn ein Graph zusammenhängend ist und genau zwei Knoten ungeraden Grades hat, dann hat er mindestens einen Euler-Pfad (normalerweise mehr). Jeder dieser Pfade muss an einem der Knoten ungeraden Grades beginnen und an dem anderen enden.

Satz von Euler (PageIndex{3}): Die Summe der Grade aller Ecken eines Graphen ist gleich der doppelten Anzahl der Kanten (und muss daher eine gerade Zahl sein).

Daher muss die Anzahl der Ecken ungeraden Grades gerade sein.

Finden von Euler-Schaltungen

  1. Stellen Sie sicher, dass jeder Knoten im Netzwerk einen geraden Grad hat.
  2. Beginnen Sie die Euler-Schaltung an einem beliebigen Knoten im Netzwerk.
  3. Verwenden Sie bei der Auswahl von Kanten niemals eine Kante, die die einzige Verbindung zu einem Teil des Netzwerks ist, den Sie noch nicht besucht haben.
  4. Beschriften Sie die Kanten in der Reihenfolge, in der Sie sie durchlaufen, und fahren Sie so fort, bis Sie jede Kante genau einmal durchlaufen haben und am Anfangsscheitelpunkt landen.

Beispiel (PageIndex{3}): Finden eines Eulerkreises

Der oben gezeigte Graph hat einen Euler-Kreis, da jeder Knoten im gesamten Graphen geraden Grades hat. Beginnen Sie also an einem geraden Scheitelpunkt, überqueren Sie jeden Scheitelpunkt einmal und nur einmal und enden Sie am Startpunkt. Ein Beispiel für einen Euler-Kreis für diesen Graphen ist A, E, A, B, C, B, E, C, D, E, F, D, F, A. Dies ist ein Kreis, der jede Kante einmal und nur überquert einmal und beginnt und endet an der gleichen Stelle. Es gibt andere Euler-Schaltungen für diesen Graphen. Dies ist nur ein Beispiel.

Der Grad jedes Scheitelpunkts ist rot markiert. Die Reihenfolge der Kanten des Stromkreises ist blau markiert und die Richtung des Stromkreises wird mit den blauen Pfeilen angezeigt.


Schau das Video: , Forward Euler: Discretizing continuous time models (Oktober 2021).