Bäume < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo Zusammen,
| Aufgabe | Ein Baum ist ein zusammenhängender kreisfreier Graph. Zeige:
Ist [mm] $v_0$ [/mm] die Wurzel, so gibt es [mm] $\forall [/mm] v [mm] \in [/mm] V$ genau einen wiederholungsfreien kürzesten Weg von [mm] $v_0$ [/mm] nach [mm] $v\!$. [/mm] |
Für ungerichtete Bäume ist mir die Aussage klar, denn gäbe es mehr als einen Weg, so könnte ich den ersten Weg nehmen, um zu [mm] $v\!$ [/mm] zu kommen, und den zweiten Weg könnte ich als Rückweg benutzen, um von [mm] $v\!$ [/mm] zu [mm] $v_0$ [/mm] zu kommen. Dann wäre ich aber im Kreis gegangen, was im Widerspruch zur Kreisfreiheit eines Baumes steht. Daher kann es auch keinen längeren Weg von [mm] $v_0$ [/mm] nach [mm] $v\!$ [/mm] geben. [mm] $\square$
[/mm]
Für gerichtete Bäume ist mir die Sache aber nicht mehr so klar. Man betrachte z.B. folgenden gerichteten Baum:
[Dateianhang nicht öffentlich]
Dieser Baum ist meiner Ansicht nach kreisfrei, da ich nicht zur Wurzel zurückkehren kann. Allerdings gibt es hier zwei Wege, um zu [mm] $v\!$ [/mm] zu kommen.
Vielen Dank!
Viele Grüße
Karl
P.S. Ich habe diese Frage auch ![[]](/images/popup.gif) im Usenet gestellt.
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:09 Sa 16.07.2005 | | Autor: | Marc |
Hallo Karl,
dann verbessere ich mal die durchschnittlichen Antwortzeiten im Info-Forum 
Hast du denn mal die Definition von kreisfei zur Hand?
Wenn kreisfrei einfach bedeutet, dass es keinen geschlossenen Weg (ohne Mehrfachdurchlaufung eines Knotens) gibt, dann ist dein Graph kreisfrei und damit ein Baum.
Die Ausgangsbehauptung, dass es zu jedem v einen kürzesten Weg gibt, gilt auch für deinen Baum.
Allerdings gilt sie nicht mehr, wenn man noch einen Knoten einfügt, und zwar auf der rechten Kante des unteren Dreiecks (das mit der roten Kante).
Dann gäbe es doch zwei kürzeste Wege.
Meine Vermutung ist, dass deine Defintion für Bäume nur für ungerichtete Graphen gilt.
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:59 Sa 16.07.2005 | | Autor: | Karl_Pech |
Hallo Marc,
> Meine Vermutung ist, dass deine Defintion für Bäume nur für ungerichtete Graphen gilt.
Im Usenet hat Mathias ja auch schon so etwas nachgefragt und mittlerweile hege ich die gleiche Vermutung wie ihr Beiden. Ich denke, ich warte jetzt erstmal wie sich die Diskussion dort entwickelt.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:17 Mi 20.07.2005 | | Autor: | Lizard |
Also ich weiß ja nicht, ob ihr "kürzeste" Pfade bei euch über Kantengewichte oder über Anzahl der Knoten auf dem Pfad definiert habt, aber bei letzterer Definition (welche ich auch vorziehen würde) sehe ich da tatsächlich nur einen kürzesten Pfad :)
BTW, hast du das Bild "von Hand" erstellt, oder gibt es dafür nette Tools? Würd mich nur mal so interessieren.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:00 Do 21.07.2005 | | Autor: | Lizard |
Also von Hand... schade, weil eine komfortable Möglichkeit, Bäume oder Graphen zu erstellen, schon interessant wäre. Momentan kenne ich nur pst-node für LaTeX, was nett ist, aber noch nicht wirklich ideal. Naja, macht nichts, das beantwortet zumindest meine Frage - danke :)
|
|
|
|
![[user]](/images/smileys/user.gif "[user]"){kind=small}
