TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 30

Aus VoWi
Zur Navigation springen Zur Suche springen

(a) Gegeben sei der folgende ungerichtete Graph

G = (V,E) mit V = {1,2,3,4,5,6} und

E = {(1,2),(1,3),(2,3),(4,5),(5,6)}

Zeichnen Sie den Graphen. Ist der Graph ein Baum oder ein Wald (Wald: kreisfreier Graph; Baum: zusammenhängender kreisfreier Graph)? Wieviele Kanten müssen Sie mindestens hinzufügen bzw entfernen um aus dem Graphen einen Baum bzw. einen Wald zu machen?


(b) Erstellen Sie einen ungerichteten Graphen mit 7 Knoten, bei dem jeder Knoten den Grad 3 hat, oder beweisen Sie, dass das nicht möglich ist.


(c) Beweisen oder widerlegen Sie: In jedem Graphen mit mindestens 2 Knoten existieren zwei Knoten u,v mit und d(u) = d(v).

Lösung[Bearbeiten | Quelltext bearbeiten]

Teil A[Bearbeiten | Quelltext bearbeiten]

Erster Teil[Bearbeiten | Quelltext bearbeiten]

Die Graphen ist weder Wald noch Baum.

Zweiter Teil[Bearbeiten | Quelltext bearbeiten]

Durch entfernen einer Kante im Graphen mit dem Kreis, entstehen 2 kreisfreie Graphen. Jeder für sich ein Baum, demnach insgesamt ein Wald.

Dritter Teil[Bearbeiten | Quelltext bearbeiten]

Durch hinzufügen einer Kante vom Knoten 3 zum Knoten 4 entsteht ein zusammenhängender, kreisfreier Graph. Auch Baum genannt.

Teil B[Bearbeiten | Quelltext bearbeiten]

d(v) v = 3

d(v) = Anzahl der Knoten mal der Knotengrade. Demnach: 7 3 = 21

da aber 2 (pro Kante zwei Knoten) kein echter Teiler von 21 ist, ist dies nicht möglich.

Teil C[Bearbeiten | Quelltext bearbeiten]

Wir konstruieren einen Graphen G für den folgendes gelten soll: Es existieren 2 Knoten v und w für die gilt d(v) = d(w)

  • n = Anzahl der Knoten (V).
  • alle v aus V haben andere Knotengrade , d.h. O-(n-1)

=> es existiert ein v aus V für das gilt d(v) = (n-1) => es existiert ein w aus V für das gild d(v) = 0 => v ist mit allen Knoten verbunden. => Widerspruch zur Behauptung es gibt einen Knoten mit d(w) = 0