 |
 |
 |
 |
 |
 |
Startseite » Forum » Weg im Graphen
Weg im Graphen
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie
 
|
  |
|---|
|
Hi, es geht um folgende Aufgabe: "Beweisen oder widerlegen Sie, dass in jedem zusammenhängenden Graphen ein Weg existiert, der jede Kante genau zweimal durchläuft." Ich würde sagen nein und einen ungerichteten Graphen mit beliebig vielen Knoten welcher keinen Kreis enthält nehmen. Jetzt tritt allerdings das Problem auf, dass ich keine schlüssige Definition des Begriffs "Weg" finde. Man könnte nämlich auch bei dem von mir gewählten Graphen sagen, dass er den "Weg" {A,B,A} enthält für einen Graphen G=(V,E) mit V={A,B} und E={AB}. Würde mich freuen wenn mir jemand sagen könnte was gilt. Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo Die Aussage ist wahr. Hier der Ansatz: Wenn alle Knotenordnungen gerade sind, hast du immer einen geschlossenen Kantenzug. Du müsstest diesen Kantenzug dann zweimal durchlaufen. Wenn es genau zwei ungerade Knotenordnungen gibt, hast du immer einen offenen Knotenzug. Du müsstest diesen Zug einmal hin und einmal zurück durchlaufen. Wenn du eine, drei oder mehr ungerade Knotenordnungen hast, kannst du diesen Graphen durch das Hinzufügen doppelter Kanten immer auf einen graphen mit nur geraden oder genau zwei ungeraden Knotenordnungen zurückführen. bzw. wenn du jede kante verdoppelst, hast du immer einen Graphen mit nur geraden Knotenordnungen, weil sich ja die Knotenordnungen verdoppeln und das doppelte einer ungeraden Zahl ist immer eine gerade Zahl. Damit existiert immer ein geschlossener kantenzug bei dem du jede Kante genau zweimal durchläufst. |
 |
|
Ähm, ist dies nicht schon der Beweis und nicht nur der Ansatz? Aber egal, vielen Dank für die Hilfe. |
|
|
|
Ich weiß nicht wie mathematiknah deine Vorlesung ist Ich hatte nie Graphentheorie, weshalb ich nicht weiß, wie man es formulieren muss damit ein Mathematiker zufrieden wäre. Der Grundgedanke wird aber wohl immer der gleiche sein. |
 |
|
Achso okay, dann vielen Dank. MfG baxbear |
1081849
1081300