Graphen zeichnen (Eulerweg)

Question

Zeichne einen einfachen, zusammenhängenden Graphen mit n = 8 Knoten und m = 10
Kanten, sodass dieser einen Eulerweg, aber keine Eulertour und keinen Hamiltonpfad bzw.
Hamiltonkreis besitzt.

Habe schon so viel rumprobiert, aber entweder hat durchläuft er eine Kante zweimal oder hat nur 7 Knoten, damit es passt. Kann mir jemand helfen.

Answer 1

Ein ungerichteter zusammenhängender Graph enthält genau dann einen Eulerweg,
wenn zwei oder keiner seiner Knoten von ungeradem Grad sind. Hat kein Knoten
ungeraden Grad, handelt es sich bei dem Eulerweg um einen Eulerkreis.

Wie man den Hamiltonpfad abschafft ohne auch den Euler zu treffen? - Vielleicht schaust Du mal bei https://mathematikalpha.de/ vorbei, da hat es unter Planimetrie auch ein Kapitel Graphentheorie - evtl. ist in den Beispielen (auch https://graphonline.ru/en/graphs_examples) was dabei.

https://graphonline.ru/en/

Graph has Eulerian path: \( 2 \Rightarrow 1 \Rightarrow 0 \Rightarrow 2 \Rightarrow 7 \Rightarrow 3 \Rightarrow 6 \Rightarrow 5 \Rightarrow 4 \Rightarrow 3 \Rightarrow 1 \)
Graph has not Eulerian cycle
Graph has Hamiltonian path: \( 0 \Rightarrow 1 \Rightarrow 2 \Rightarrow 7 \Rightarrow 3 \Rightarrow 4 \Rightarrow 5 \Rightarrow 6 \)
Graph has not Hamiltonian cycle

Comments

Vielen Dank, habe schon einen anderen gefunden.

---

in der Aufgabe steht "kein Hamiltonpfad". Ist bei deinem Graphen aber enthalten

---

Du willst ja auch noch was zu tun haben ;-)....

Wenn Du eine Lösung hast, dann her damit?

---

Bitte sag mir, dass das richtig ist. Startknoten ist die 3

---

Hm,

du hast einen gerichteten Graphen, davon war nicht die Rede?

BTW. Mathematik alpha 2021 sucht alle Euler-/Hamiltonstrukturen...

Ich steck nicht so dick drin im Thema - Oder es gibt einen ganz verschwurbelten Graphen....

---

Ja aber in Kombination mit dem Eulerweg ist es ja dann kein Hamiltonpfad mehr.

Und ob der graph gerichtet ist oder nicht spielt glaube ich keine rolle

---

Versteh ich jetzt nicht, aber Deinen Kontext für die Aufgabe kann ich nicht einschätzen.

> einfachen, zusammenhängenden Graphen<

klingt für mich nicht nach einem gerichteten Graph.

Außerdem ist bei Start 0 ein Hamiltonpfad offen...

---

Ich versuche gerade GeoGebra mit Graphen bekannt zu machen

 

Das wäre wohl auch ein zusammenhängender Graph mit Eulerweg und ohne Eulerkreis und ohne Hamiltondingens

---

Okay danke, dass du dir nochmal die Mühe gemacht hast. Leider kann ich nur einmal die beste Antwort vergeben. :D