Beweisen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegeben:
Menschen n > 1. Für je 2 Menschen [mm] m_1 [/mm] , [mm] m_2 [/mm] trifft Mensch [mm] 1m_1 [/mm] den Menschen [mm] m_2 [/mm] oder umgedreht. Dieses "Treffen" realisiert eine gerichtete [mm] Kante(m_1 [/mm] , [mm] m_2) [/mm] , von [mm] m_1 [/mm] nach [mm] m_2 [/mm] oder umgekehrt.
Beweise: Im Graphen , der gerichtet ist, gibt es einen Weg, der gerichtet ist und der jeden Menschen genau einmal enthält. |
Hallo,
ich soll die Aufgabe mit vollst. Ind. lösen.
Für n= 2 ist es klar.
Habe 2 Knoten [mm] m_1 [/mm] und [mm] m_2 [/mm] gezeichnet, verbunden durch eine Kante.
Wie mache ich im IS weiter ? Kann mir jemand bitte einen Tipp geben?
Vielen Dank im Voraus.
|
|
| |
|
Hallo,
> Gegeben:
> Menschen n > 1. Für je 2 Menschen [mm]m_1[/mm] , [mm]m_2[/mm] trifft Mensch
> [mm]1m_1[/mm] den Menschen [mm]m_2[/mm] oder umgedreht. Dieses "Treffen"
> realisiert eine gerichtete [mm]Kante(m_1[/mm] , [mm]m_2)[/mm] , von [mm]m_1[/mm] nach
> [mm]m_2[/mm] oder umgekehrt.
> Beweise: Im Graphen , der gerichtet ist, gibt es einen
> Weg, der gerichtet ist und der jeden Menschen genau einmal
> enthält.
Das Problem nennt sich: Finde einen Hamilton-Pfad in einem "Tournament"-Graphen.
> ich soll die Aufgabe mit vollst. Ind. lösen.
> Für n= 2 ist es klar.
> Habe 2 Knoten [mm]m_1[/mm] und [mm]m_2[/mm] gezeichnet, verbunden durch eine
> Kante.
>
> Wie mache ich im IS weiter ? Kann mir jemand bitte einen
> Tipp geben?
Du hast nun (n+1) Menschen gegeben, und je zwei unter diesen sind mit einer gerichteten Kante verbunden.
Wenn du aus diesen (n+1) Menschen $k [mm] \le [/mm] n$ beliebig heraussuchst, kannst du laut Induktionsvoraussetzung einen gerichteten Weg finden, der jeden der k Menschen genau einmal enthält.
Wähle nun einen beliebigen Knoten v.
Betrachte
$S = [mm] \{w \mbox{Knoten}: (v,w) \mbox{Kante}\}$ [/mm] (von v weg)
$T = [mm] \{w \mbox{Knoten}: (w,v) \mbox{Kante}\}$ [/mm] (zu v hin)
Beide Mengen S,T haben weniger als (n+1) Knoten und daher jeweils so einen gerichteten Weg.
Wie kannst du nun den gesuchten gerichteten Weg durch alle (n+1) Menschen finden?
Viele Grüße,
Stefan
|
|
|
| |
|
Hallo,
vielen Dank für die Antwort.
Ich habe lange darüber nachgedacht und komme auf keinen richtigen Ansatz.
Ich verstehe das Problem,aber ich komme njcht auf n+1. Ein weiterer Denanstoß wäre nett, sodass ich die IV benutzen kann bezüglich der n+1
MfG
|
|
|
| |
|
Hallo,
Wie beschrieben gehe bei (n+1) Menschen wie folgt vor:
Fixiere einen beliebigen Menschen $v$.
Dieser Mensch hat eine Verbindung zu jedem anderen Menschen im Graphen. Entweder geht sie von v weg, oder sie geht zu v hin.
Sammle in einer Menge S alle Menschen, deren Verbindung zu v von v weggeht.
Sammle in einer Menge T alle Menschen, deren Verbindung zu v zu v hingeht.
Wende die Induktionsvoraussetzung auf S und T an.
Wir haben jetzt in S einen gerichteten Pfad, der alle Menschen in S genau einmal durchläuft. Wir bezeichnen den Startmensch dieses Pfades mit [mm] $s_a$ [/mm] und den letzten Mensch in diesem Pfad mit [mm] $s_{e}$.
[/mm]
Dasselbe machen wir mit T:
Wir haben jetzt in T einen gerichteten Pfad, der alle Menschen in T genau einmal durchläuft. Wir bezeichnen den Startmensch dieses Pfades mit [mm] $t_a$ [/mm] und den letzten Mensch in diesem Pfad mit [mm] $t_{e}$.
[/mm]
Ein Pfad durch alle (n+1) Menschen ist jetzt wie folgt gegeben:
[mm] t_a [/mm] --> ...Pfad in T... --> [mm] t_e [/mm] -->v --> [mm] s_a [/mm] --> ...Pfad in S... --> [mm] s_e
[/mm]
------
Der Trick beim Beweis ist zu nutzen, dass man von den Menschen aus T garantiert eine Verbindung zu v hinbekommt, und v dann garantiert eine Verbindung zu den Menschen aus S.
Viele Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:52 So 02.02.2014 | | Autor: | pc_doctor |
Alles klar, vielen lieben Dank für deine Antwort. Habs jetzt kapiert.
MfG
|
|
|
|
