azyklische und zyklische Graph < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | G sei ein gerichteter Graph; u und v seien zwei verschiedene Knoten in G. Beweisen oder widerlegen Sie folgende Aussagen:
1. Wenn G azyklisch ist, kann man zumindest eine der Kanten (u,v) oder (v,u) dem Graph hinzufügen, ohne einen Zyklus zu erzeugen.
2. Wenn es unmöglich ist weder die Kante (u,v) noch die Kante (v,u) in G aufzunehmen ohne einen Zyklus zu erzeugen, dann ist G schon zyklisch.
|
Hallo, habe leider kein Beweis für die obige Aufgabe, ich bin aber der Meinung, dass wenn man zumindest eine der Kanten (u,v) oder (v,u) dem Graph hinzufügt, dann wird ein Zyklus erzeugt. Stimmt das?
gruß
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:50 Di 06.07.2010 | | Autor: | felixf |
Moin
> G sei ein gerichteter Graph; u und v seien zwei
> verschiedene Knoten in G. Beweisen oder widerlegen Sie
> folgende Aussagen:
>
> 1. Wenn G azyklisch ist, kann man zumindest eine der Kanten
> (u,v) oder (v,u) dem Graph hinzufügen, ohne einen Zyklus
> zu erzeugen.
> 2. Wenn es unmöglich ist weder die Kante (u,v) noch
> die Kante (v,u) in G aufzunehmen ohne einen Zyklus zu
> erzeugen, dann ist G schon zyklisch.
>
> Hallo, habe leider kein Beweis für die obige Aufgabe, ich
> bin aber der Meinung, dass wenn man zumindest eine der
> Kanten (u,v) oder (v,u) dem Graph hinzufügt, dann wird ein
> Zyklus erzeugt. Stimmt das?
Versuch doch mal azyklische Graphen mit moeglichst vielen Kanten zu zeichnen. Und dann denk nochmal ueber die Aussagen oben nach.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:47 Mi 07.07.2010 | | Autor: | capablanca |
Danke für den Tipp, also hatte ich Recht 
gruß
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:01 Mi 07.07.2010 | | Autor: | felixf |
Moin,
> Danke für den Tipp, also hatte ich Recht
ja, fast zumindest: es gibt natuerlich auch zykelfreie Graphen und Paare $(u, v)$, wo das Hinzufuegen keinen Zykel erzeugt. Aber es kann halt schon welche erzeugen :)
LG Felix
|
|
|
|
