Aufgabe 4 Übung 3

Moderator: Effiziente Graphenalgorithmen

erna
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 9. Dez 2009 15:05

Aufgabe 4 Übung 3

Beitrag von erna »

Hallo,

folgendes Szenario: G=(V,E)=({1,2,3,4},{(1,2),(2,3),(3,4),(3,1)}) und der MST von G ist T=(V_T,E_T)=({1,2,3,4},{(1,2),(3,1),(2,4)}). Der induzierte Teilgraph soll H=(V_H,E_H)=({2,3,4},{(2,4),(3,4)}) sein, dann wäre der Schnitt T mit H = ({2,3,4},{(3,4)}) richtig? Der Schnitt ist aber keine MST von H mehr :( , weil der Knoten 3 nicht verbunden ist. Vielleicht kann mir einer weiterhelfen und mir sagen wo mein Denkfehler liegt?

Vielen Dank.

tobiasp
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 5. Okt 2008 23:08

Re: Aufgabe 4 Übung 3

Beitrag von tobiasp »

Man soll nur zeigen, dass \(T \cap H\) in irgendeinem MST von H enthalten ist, d.h. dass\(T \cap H\) ein Teilgraph von mindestens einem MST von H ist. \(T \cap H\) selbst braucht damit kein MST von H sein.

erna
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 9. Dez 2009 15:05

Re: Aufgabe 4 Übung 3

Beitrag von erna »

ich danke dir :). Enthalten ist ja nicht gleich MST von H ;). Das macht die Sache natürlich einfacher :D

Antworten

Zurück zu „Effiziente Graphenalgorithmen“