Turniergraph < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:24 Mi 18.01.2006 | | Autor: | dump_0 |
Hallo.
Es gibt ja solche sogenannten turniergraphen wo entweder (u,v) [mm] \in [/mm] A oder (v,u) [mm] \in [/mm] A (wobei A ein gerichteter Weg ist und (u,v) u schlägt v bedeuten soll).
Jetzt soll ich beweisen das es in jedem solchen Turniergraphen einen längsten Pfad gibt der alle Knoten des Graphen enthält.
Als Hilfe wurde folgende Bemerkung gegeben: Überlegen Sie wie Sie einen Pfad, der weniger als |V| Knoten enthält verlängern können.
Ich habe leider nicht viel Ahnung wie ich das beweisen soll :(
Über Hilfe würd ich mich freuen.
Mfg
[mm] dump_0
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:17 Mi 18.01.2006 | | Autor: | piet.t |
Hallo,
Hier mal meine Beweisidee. Da ist eigentlich schon alles wesentliche drin, Du musst nur noch vervollständigen und formal sauber aufschreiben.
Wir nehmen also an, wir hätten einen Pfad mit n < |V| Knoten, d.h. es gibt einen Knoten u, der nicht auf dem Pfad liegt. Unser Ziel ist es jetzt, u in den gegebenen Pfad zu integrieren.
Ist [mm] v_n [/mm] der Endknoten des Pfads und [mm] (v_n,u) \in [/mm] A, dann hängt man u einfach als neues letztes Element an den Pfad.
Ist aber [mm] (u,v_n) \in [/mm] A betrachten wir den Vorgänger [mm] v_{n-1} [/mm] von [mm] v_n. [/mm] Ist [mm] (v_{n-1},u) \in [/mm] A, dann können wir u zwischen [mm] v_{n-1} [/mm] und [mm] v_n [/mm] "einhängen" [mm] (v_{n-1}->u->v_n [/mm] ist ja dann ein Pfad im Graphen). gilt hier wieder die andere Richtung müssen wir noch ein Element weiter zurück und nochmal prüfen usw. bis hin zu [mm] v_1 [/mm] (dem Anfang des Pfads). Was können wir tun, wenn dann immer noch [mm] (v_0,u) \notin [/mm] A (also [mm] (u,v_0 \in [/mm] A) gilt?
Gruß
piet
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:46 Mi 18.01.2006 | | Autor: | dump_0 |
Erstmal vielen dank für deine Mühe und für den Beweis, klingt sehr einleuchtend, konnte mir darunter nicht wirklich was vorstellen *schäm*
Ich weiß nicht genau aber wenn [mm] [latex](v_0,u) \notin [/mm] A[/latex] ist aber umgekehrt schon, dann kann man u doch als neues erstes Element vorn an den Pfad dranhängen und die restlichen [mm] v_i [/mm] werden zu [mm] v_{i+1} [/mm] oder ?
Mfg
[mm] dump_0
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:48 Mi 18.01.2006 | | Autor: | piet.t |
> Erstmal vielen dank für deine Mühe und für den Beweis,
> klingt sehr einleuchtend, konnte mir darunter nicht
> wirklich was vorstellen *schäm*
>
> Ich weiß nicht genau aber wenn [mm][latex](v_0,u) \notin[/mm]
> A[/latex] ist aber umgekehrt schon, dann kann man u doch
> als neues erstes Element vorn an den Pfad dranhängen und
> die restlichen [mm]v_i[/mm] werden zu [mm]v_{i+1}[/mm] oder ?
>
Ganz genau. Kurz zusammengefasst:
- gibt's eine Kante vom Ende des Pfads zu u wird u dort angehängt
- gibt's keine Kante von irgendeinem Pfadelement zu u (sondern nur umgekehrt) wird u zum neuen Anfang
- gibts sowohl Kanten von u zu Pfadelementen als auch umgekehrt, dann wird u zwischen zwei Pfadelemente mit passenden Kanten eingefügt.
|
|
|
|
