0 Daumen
1,6k Aufrufe

Ich habe einen eulerschen Graphen gegeben, der ungerichtet ist, so wie man es auf dem Bild sehen kann und nummeriert mit den Zahlen 1,2,3,4.

Ich soll bestimmen, ob dieser eulersch ist und welche Eigenschaften er besitzt. Ich bin mir da aber total unsicher.

Ich glaube:

- Besicht einen Eulerweg

- Ist nicht eulersch

Stimmt das?

Die Matrix habe ich auch dazu entworfen, die wäre:

1 1 0 0

1 0 1 1

0 1 0 1

0 1 1 0

Hier noch das Foto :)

Avatar von
Das e neben der 1 soll heissen, dass 1 mit 1 verbunden ist? So lese ich jedenfalls deine Matrix, in der du jede Kante an 2 Orten eigetragen hast.
Also die eine kante zeigt eine schleife auf die 1. eig zeigen nur die 2,3,4 jeweils auf zwei knoten. Stimmt es mit den eigenschaften die ich genannt habe.

1 Antwort

+1 Daumen

Ein ungerichteter Graph G ist genau dann ein eulerscher Graph, wenn G zusammenhängend ist (wenn also je zwei seiner Knoten durch eine Kantenfolge des Graphen verbunden werden können) und jeder Knoten geraden Grad hat (wenn also die Anzahl der an den Knoten angeschlossenen Kanten gerade ist, wobei eine Schleife doppelt gezählt wird, weil sie zweimal an den betroffenen Knoten angeschlossen ist).

Der vorliegende Graph ist zusammenhängend, enthält jedoch zwei Knoten mit ungeradem Grad (Knoten 1 und 2) und ist daher nicht eulersch.

 

Ein Eulerweg ist eine Folge von Kanten eines Graphen G, der jede Kante von G genau einmal enthält.
Ein Eulerkreis ist ein Eulerweg, dessen Anfangknoten gleich seinem Endknoten ist.

Es gilt:

Ein ungerichteter, zusammenhängender Graph G enthält genau dann einen Eulerweg, wenn G keinen oder genau zwei Knoten mit ungeradem Grad enthält. Enthält G keinen Knoten mit ungeradem Grad, dann ist der Eulerweg sogar ein Eulerkreis.

Der vorliegende Graph enthält genau zwei Knoten mit ungeradem Grad. Er enthält also einen Eulerweg, der aber kein Eulerkreis ist. 

Avatar von 32 k
Also, wenn eine Schleife auf einen Knoten zeigt, dann wird die doppelt gezähl? In diesem Beispiel, wäre dann der Knoten 1 vom ungeraden Grad 3? Habe ich das richtig verstanden?

-----------------

Wäre der Graph weiterhin ein Eulerweg, wenn bei dem Knoten 1 keine Schleife vorhanden wären? Dann hätten wir ja weiterhin den Knoten 1 und 2 vom ungeraden Grad, nämlich 1 oder? Also zwei Knoten vom ungeraden Weg = Eulerweg.

--------------

Und kann man die gleichen Eigenschaften bei den gerichteten Graphen einsetzen? Also gibt es auch in gerichteten Graphen einen Eulerweg bzw. Eulerkreis.

Und noch zum Schluß, wenn ich sage, dass ein G einen Eulerkreis besitzt, dann kann ich auch sagen, dass dieser eulersch ist oder?


lg

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community