a)
reflexiv: klar, gibt ja Pfad der Länge 0
symmetrisch: ergibt sich aus Definition
transitiv: klar, man kann ja die 2 Pfade hintereinander hängen
Kann man das irgendwie anders machen? Also klingt für mich logisch so, kommt mir aber zu einfach vor.
b)
Beweis gibts hier: Lemma 4.6
c) hab ich noch nicht
Algorithmen[10] #2
Re: Algorithmen[10] #2
hab a)und b) gleich gelöst, bei der c) bin ich auch noch am überlegen...
hatte mir spontan gedacht, da alle kürzesten wege eindeutig sind hat jeder knoten auser dem startknoten eingangsgrad 1, wodurch es also n-1 kanten gibt. Zusammengenommen mit der Tatsache, dass der Graph ja Zusammenhängend ist, kann man daraus wohl schliessen, dass es sich um einen Baum handelt (steht zumindest so in wikipedia).
Das is der problempunkt ^^ kann ich das so machen? haben wir andere charakterisierungen für bäume?
Hier der Artikel naja..
http://de.wikipedia.org/wiki/Baum_(Graphentheorie)
hatte mir spontan gedacht, da alle kürzesten wege eindeutig sind hat jeder knoten auser dem startknoten eingangsgrad 1, wodurch es also n-1 kanten gibt. Zusammengenommen mit der Tatsache, dass der Graph ja Zusammenhängend ist, kann man daraus wohl schliessen, dass es sich um einen Baum handelt (steht zumindest so in wikipedia).
Das is der problempunkt ^^ kann ich das so machen? haben wir andere charakterisierungen für bäume?
Hier der Artikel naja..
http://de.wikipedia.org/wiki/Baum_(Graphentheorie)