webentwicklung-frage-antwort-db.com.de

Unterschied zwischen Hamilton-Pfad und Euler-Pfad

Kann mir jemand den Unterschied zwischen Hamilton-Pfad und Euler-Pfad erklären? Sie scheinen ähnlich zu sein!

51
mousey

Ein Euler-Pfad ist ein Pfad, der jede Kante genau einmal durchquert, ohne sich zu wiederholen. Wenn er am ersten Scheitelpunkt endet, handelt es sich um einen Euler-Zyklus.

Ein Hamilton-Pfad durchläuft jeden Scheitelpunkt (notiere nicht jede Kante) genau einmal, wenn er am anfänglichen Scheitelpunkt endet, dann ist es ein Hamilton-Zyklus.

In einem Euler-Pfad können Sie einen Scheitelpunkt mehr als einmal durchlaufen.

Auf einem Hamilton-Pfad können Sie möglicherweise nicht alle Kanten durchlaufen.

105
Chris Diver

Graphentheoretische Definitionen

(In absteigender Reihenfolge der Allgemeinheit)

  • Gehen : Eine Folge von Kanten, bei der das Ende einer Kante den Anfang der nächsten Kante markiert

  • Trail : ein Spaziergang, der keine Kanten wiederholt. Alle Wege sind Spaziergänge.

  • Pfad : Ein Spaziergang, bei dem jeder Scheitelpunkt genau einmal durchlaufen wird. (Pfade, die für offene Pfade verwendet wurden, die Definition wurde jetzt geändert.) Die Eigenschaft, Scheitelpunkte nur einmal zu überqueren, bedeutet, dass Kanten auch nur einmal gekreuzt werden. Daher sind alle Pfade Pfade.

Hamilton-Pfade und Euler-Pfade

  • Hamilton-Pfad : Besuche jeden Scheitelpunkt in der Grafik (genau einmal, weil es ein Pfad ist)

  • Eulersche Spur : Besuche jede Kante in der Grafik genau einmal (da es sich um eine Spur handelt, können Scheitelpunkte durchaus mehr als gekreuzt werden Einmal.)

9
Will

Der Euler-Pfad muss jeden Rand genau einmal besuchen, während der Hamilton-Pfad jeden Scheitelpunkt genau einmal besuchen muss.

9
Roman Cheplyaka

Ein Hamilton-Pfad besucht jeden Knoten (oder Scheitelpunkt) genau einmal und ein Euler-Pfad durchläuft jede Kante genau einmal.

3
burningstar4

Sie sind verwandt, aber weder abhängig noch schließen sie sich gegenseitig aus. Wenn ein Graph einen Eurler-Zyklus hat, kann er auch einen Hamilton-Zyklus haben oder nicht und umgekehrt.


Euler-Zyklen besuche jeden Kante in der Grafik genau einmal. Wenn das Diagramm Scheitelpunkte mit mehr als zwei Kanten enthält, durchläuft der Zyklus diese Scheitelpunkte definitionsgemäß mehr als einmal. Infolgedessen können Scheitelpunkte wiederholt werden, Kanten jedoch nicht.

Hamiltonsche Zyklen besuche jeden scheitel in der Grafik genau einmal (ähnlich dem Problem des Handlungsreisenden). Infolgedessen können weder Kanten noch Scheitelpunkte wiederholt werden.

3
advait

Ich werde ein allgemeines Beispiel in der Biologie verwenden; Rekonstruktion eines Genoms durch Herstellung von DNA-Proben.

De-novo-Versammlung

Um ein Genom aus kurzen Lesevorgängen zu konstruieren, muss ein Diagramm dieser Lesevorgänge erstellt werden. Dazu teilen wir die gelesenen Werte in K-Meter auf und setzen sie zu einem Diagramm zusammen.

enter image description here

Wir können das Genom rekonstruieren, indem wir jeden Knoten einmal wie im Diagramm besuchen. Dies ist als Hamilton-Pfad bekannt.

Leider ist die Konstruktion eines solchen Weges NP-schwer. Es ist nicht möglich, einen effizienten Algorithmus zum Lösen abzuleiten. Stattdessen konstruieren wir in der Bioinformatik einen Eulerschen Zyklus, bei dem eine Kante eine Überlappung darstellt.

enter image description here

2
SmallChess

Ein Euler-Pfad ist ein Pfad, der jede Kante eines Diagramms genau einmal verwendet und genau zwei ungerade Scheitelpunkte haben muss. Der Pfad beginnt und endet an einem anderen Scheitelpunkt. Ein Hamilton-Zyklus ist ein Zyklus, der jeden Scheitelpunkt des Diagramms enthält. Daher können Sie nicht alle Kanten des Diagramms verwenden.

1
Mibei nicholas

Der Euler-Pfad ist ein Diagramm, in dem jede Kante (HINWEIS) des Diagramms verwendet wird genau einmal. Euler-Schaltung ist ein Euler-Pfad, der zu seinem Ausgangspunkt zurückkehrt nachdem alle Kanten abgedeckt wurden.

Während Hamilton-Pfad ein Diagramm ist, das alle Scheitelpunkte (HINWEIS) genau einmal abdeckt. Wenn dieser Pfad zu seinem Ausgangspunkt zurückkehrt, wird dieser Pfad Hamilton-Schaltung genannt.

0
Rajan Chauha n