Graphentheorie < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:54 Mo 26.09.2005 | | Autor: | mx2002 |
Hallo,
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Am Freitag muss ich diesen Beweis (ganz oder teilweise) in einer Klausur bearbeiten. Ich habe aber noch relativ wenig Ahnung wie das konkret ablaufen kann.
Schlingen und Mehrfachkanten sind bei den folgenden Betrachtungen ausgenommen.
G=(V,E) sei ein Graph, Die folg. Behauptungen sind äquvalent:
(1) G ist ein Baum
(2) G ist kreisfrei, aber das Hinzufügen einer beliebiger neuer Kante erzeugt einen eindeutig bestimmten Kreis
(3) Je zwei Ecken von G sind durch genau einen Weg verbunden
(4) G ist zusammenhängend und jede Kante ist eine Brücke
Bis jetzt habe ich mir folgendes überlegt:
(1)-->(2): Per Definition ist ein Baum ja kreisfrei und zusammenhängend d.h. |V| = n; |E| = n - 1;
Durch hinzufügen einer weiteren Kante, also |E| = n entsteht ja dann zwangsläufig ein Kreis, oder nicht?
(2)-->(3): "[...] das Hinzufügen einer beliebiger neuer Kante erzeugt einen eindeutig bestimmten Kreis" dies Bedeutet doch, das je zwei Ecken durch einen Weg verbunden sind. Die Definition von zusammenhängend ist doch genau, das je zwei Ecken durch einen Weg verbunden sein müssen.
(3)-->(4): Das G zusammenhängend sein muss ist trivial, da die Vorraussetzung genau der Definition entspricht. Das jede Kante jedoch eine Brücke ist, d.h. der Graph durch Weglassen dieser Kante in zwei Zusammenhangskomponenten zerfällt, ist mir nicht klar.
Das waren bis jetzt meine Ideen, vielleicht könnt Ihr mir sagen ob diese vom Ansatz her korrekt sind. Bei der formalen Umsetzung habe ich jedoch die größten Probleme, kann mir da bitte jemand helfen?
Gruß,
mx2002
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:34 Mo 26.09.2005 | | Autor: | bazzzty |
> Schlingen und Mehrfachkanten sind bei den folgenden
> Betrachtungen ausgenommen.
>
> G=(V,E) sei ein Graph, Die folg. Behauptungen sind
> äquvalent:
>
> (1) G ist ein Baum
> (2) G ist kreisfrei, aber das Hinzufügen einer beliebiger
> neuer Kante erzeugt einen eindeutig bestimmten Kreis
> (3) Je zwei Ecken von G sind durch genau einen Weg
> verbunden
> (4) G ist zusammenhängend und jede Kante ist eine Brücke
Da Du ja schon gut vorgearbeitet hast, hangle ich mich an Deinem Ringschluß entlang, ich halte das auch für die beste Idee.
> (1)-->(2): Per Definition ist ein Baum ja kreisfrei und
> zusammenhängend d.h. |V| = n; |E| = n - 1;
> Durch hinzufügen einer weiteren Kante, also |E| = n
> entsteht ja dann zwangsläufig ein Kreis, oder nicht?
Genau. Bloß formal muß das klar werden.
Also: (1)->(2) Kreisfreiheit ist in der Definition des Baumes enthalten. Zu zeigen bleibt: Jede neue Kante schließt einen Kreis. Sei [mm]\{u,v\}[/mm] eine neue Kante. Da ein Baum zusammenhängend ist, gab es schon einen Pfad von [mm]v[/mm] zu [mm]u[/mm] vor dem Einfügen, der zusammen mit der neuen Kante einen eindeutigen Kreis ergibt. (Eindeutig deshalb, weil jeder Kreis die neue Kante enthalten muß, da G vorher kreisfrei war)
> (2)-->(3): "[...] das Hinzufügen einer beliebiger neuer
> Kante erzeugt einen eindeutig bestimmten Kreis" dies
> Bedeutet doch, das je zwei Ecken durch einen Weg verbunden
> sind. Die Definition von zusammenhängend ist doch genau,
> das je zwei Ecken durch einen Weg verbunden sein müssen.
Ich würde hier zeigen, daß in G alle Paare von Knoten weder durch keinen noch durch 2 (oder mehr) Wege verbunden sind:
(i) sind zwei Knoten durch keinen Weg verbunden, läßt sich zwischen den beiden einen Kante einfügen, die keinen Kreis schließt im Widerspruch zur Annahme von (2)
(ii) Ist ein Paar von Knoten schon durch zwei Wege verbunden, dann enthält der Graph bereits einen Kreis (nicht notwendigerweise mit den beiden Knoten darauf!!) wieder in Widerspruch zur Annahme von (2).
> (3)-->(4): Das G zusammenhängend sein muss ist trivial, da
> die Vorraussetzung genau der Definition entspricht. Das
> jede Kante jedoch eine Brücke ist, d.h. der Graph durch
> Weglassen dieser Kante in zwei Zusammenhangskomponenten
> zerfällt, ist mir nicht klar.
Vorsicht erstmal beim Zusammenhang: Das entspricht der Definition von Baum (1), die Du im Ringschluß aber nicht verwenden darfst. Alles, was Du voraussetzen darfst, ist (3).
Aber das reicht natürlich: Zwischen je zwei Knoten ist ein Weg, also ist der Graph zusammenhängend. Entfernt man nun eine beliebige Kante [mm]\{u,v\}[/mm], dann gibt es einen Weg weniger von [mm]u[/mm] nach [mm]v[/mm]. Also unter Voraussetzung (3) gar keinen mehr. Der Graph ist also nicht mehr zusammenhängend, [mm]\{u,v\}[/mm] war eine Brücke
Was jetzt noch fehlt, ist (4)->(1):
Zusammenhang ist klar, ist ja in (4) explizit enthalten. Kreisfreiheit ist auch nicht schwer: Wäre G nicht kreisfrei, dann ist jede Kante auf einem solchen Kreis keine Brücke, denn sie kann entfernt werden, ohne den Zusammenhang zu zerstören.
> Das waren bis jetzt meine Ideen, vielleicht könnt Ihr mir
> sagen ob diese vom Ansatz her korrekt sind. Bei der
> formalen Umsetzung habe ich jedoch die größten Probleme,
> kann mir da bitte jemand helfen?
ich hoffe, ich bin auf alles eingegangen, frag ruhig nach, wenn es unklar ist!
HTH, Bastian
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:55 Mo 26.09.2005 | | Autor: | mx2002 |
Hallo,
Danke, ich denke das hilft mir schon recht viel. Nur mit den formalen Schreibweisen bin ich mir noch nicht so sicher.
Gruß,
mx2002
|
|
|
|
