Euler-Zyklen in zweifach verbundenen Komponenten

9

Wenn ein Graph einen Euler-Zyklus hat, haben die doppelt verbundenen Komponenten auch Euler-Zyklen?

graph-theory eulerian-paths
quelle
1
Wenn dies ein Hausaufgabenproblem ist, ist es vielleicht am besten, wenn Sie es selbst ausprobieren? Ein Graph kann einen Euler-Zyklus haben, aber es scheint nicht natürlich zu folgen, dass eine Teilmenge (sogar eine zweifach verbundene) sollte. Haben Sie versucht, ein Gegenbeispiel zu finden?

Antworten:

9

Ja. Wenn Sie mit einem Euler-Zyklus für das Diagramm beginnen und sich auf eine zweifach verbundene Komponente beschränken, haben Sie immer noch einen Zyklus für die zweifach verbundene Komponente (wenn der Euler-Zyklus den Scheitelpunkt v in der zweifach verbundenen Komponente verlässt, wissen Sie, dass er zurückkehren muss auf die zweifach verbundene Komponente durch v, sonst könnten wir unsere zweifach verbundene Komponente vergrößern - im Widerspruch zu ihrer Maximalität).


quelle