Dominanzrelation < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo!
Ich soll diesmal folgenden Satz beweisen, habe aber keinen wirklichen Ansatz und kann deshalb auch keinen Gedankengang dazu beitragen. Ich weiß gerade mal die Definition einer Dominanzrelation und dass dieser Satz verwandt mit dem Thema von Cliquen ist.
Sei R eine Dominanzrelation auf X und sei $x [mm] \in [/mm] X$ ein Element mit maximaler 2-Mächtigkeit. Dann gibt es von x zu jedem $y [mm] \in [/mm] X$ mit $y [mm] \not= [/mm] x$ mindestens eine ein- oder zweistufige Verbindung.
Danke für eure Hilfe,
Christian.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:27 Fr 08.04.2005 | | Autor: | MrElgusive |
Hallo!
Sei R eine Relation auf X mit Adjazenzmatrix A und sei $k [mm] \in \IN$. [/mm] Die k-Mächtigkeit eines $x [mm] \in [/mm] X$ ist die Anzahl aller $ [mm] \le [/mm] (k-1)$ -stufigen Verbindungen von x zu einem $y [mm] \in [/mm] X,$ also die k-Mächtigkeit = Zeilensumme (von x) in $A + [mm] A^{2} [/mm] + ... + [mm] A^{k}.$
[/mm]
Und eine Dominanzrelation auf X ist nun eine Relation R, für die alle $x,y [mm] \in [/mm] X, y [mm] \not= [/mm] x,$ entweder $xRy$ oder $yRx$ (aber nicht beides) gilt.
Und für den Fall $K=2$ soll man nun den Satz in meinem ersten Posting beweisen.
Das mit den Adjazenzmatrizen und den Relationen ist mir ja alles klar, aber ich habe nur keinen Schimmer, wie ich den Satz beweisen soll.
Grüße,
Christian.
|
|
|
| |
|
Grüße!
Also, nach einer kurzen Diskussion mit meinem Mitbewohner, der in Graphentheorie etwas fitter ist als ich, haben wir eine Lösung gefunden. 
Ich habe das Problem erstmal umformuliert: die Menge $X$ habe ich als Eckenmenge eines Graphen gesehen - je zwei Ecken sind duch eine (gerichtete) Kante verbunden. Das reflektiert die Relation, die zwischen je zwei Punkten $x$ und $y$ besteht.
Einen solchen Graphen nennt man meinem Mitbewohner zufolge "Turniergraph". Die Anschauung ist, dass ein Turnier zugrunde liegt, in dem jeder gegen jeden spielt und die Richtung der Kante gibt an, wer gewonnen hat.
Also, zum formalen Beweis. Unterschlagen hast Du die Bedingung, dass $X$ endlich ist (ist aber eigentlich klar, wenn Du eine Matrix aufstellst). Ich führe zunächst etwas Notation ein: zu $x [mm] \in [/mm] X$ sei [mm] $m_1(x)$ [/mm] die 1-Mächtigkeit von $x$, also die Mächtigkeit der Menge
[mm] $I_1(x) [/mm] = [mm] \{ y \in X : x R y \}$
[/mm]
Entsprechend sei [mm] $m_2(x)$ [/mm] die 2-Mächtigkeit von $x$, also die Mächtigkeit der Menge
[mm] $I_2(x) [/mm] = [mm] \{ y \in X : x R y \mbox{ oder } x R z \wedge z R y \mbox{ für ein } z \in X \}$
[/mm]
Sei nun $x [mm] \in [/mm] X$ beliebig mit [mm] $m_2(x)$ [/mm] maximal. Wir müssen zeigen: [mm] $I_2(x) [/mm] = X$ also jedes Element von $X$ ist in höchstens 2 Schritten erreichbar.
Nehmen wir an, dass dies nicht so ist, also angenommen es gibt ein $y [mm] \notin I_2(x)$. [/mm] Dann gilt $y R x$ (da $xRy$ nicht gelten kann) und auch $yRx'$ für alle $x' [mm] \in I_1(x)$. [/mm] Damit ist aber [mm] $m_1(y) \geq m_1(x) [/mm] + 1$ und da [mm] $I_1(x) \subseteq I_1(y)$ [/mm] folgt: [mm] $m_2(y) [/mm] > [mm] m_2(x)$ [/mm] im Widerspruch zur Maximalität.
In Worten: es kann nicht sein, dass es so ein $y$ gibt, denn das hieße dann, dass ich von $y$ aus das $x$ erreiche und außerdem jeden Punkt, den ich von $x$ aus in einem Schritt erreiche - sonst könnte ich $y$ ja in zwei Schritten von $x$ erreichen. Aber dadurch ist die 2-Mächtigkeit von $y$ echt größer als die von $x$.
Interessant ist das, wenn man das auf ein Turnier anwendet: in jedem Turnier "Jeder gegen Jeden" gibt es mindestens eine Person, für die gilt: jeder, der von dieser Person nicht besiegt wurde, wurde von jemandem besiegt, der wiederum der Person unterlag.
Alles klar? Wenn nicht, frag einfach nach.
Lars
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:17 So 10.04.2005 | | Autor: | MrElgusive |
Hallo Lars!
Danke für deine Antwort zur späten Stunde, mir ist eigentlich alles soweit klar, aber selber wäre ich wohl nie darauf gekommen.
Danke euch beiden!
Grüße,
Christian.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:25 So 10.04.2005 | | Autor: | Reaper |
Hallo ahb mir auch mal das Beispiel angesehen und hab da doch ein paar Fragen
Du schreibst:
Nehmen wir an, dass dies nicht so ist, also angenommen es gibt ein $ y [mm] \notin I_2(x) [/mm] $. //Also es gibt ein y was man beispielsweise auch in 3 Schritten erreichen kann
Dann gilt $ y R x $ (da $ xRy $ nicht gelten kann) und auch $ yRx' $ für alle $ x' [mm] \in I_1(x) [/mm] $.
//Hier kann ich dir nicht mehr folgen. Wieso gilt dann $ y R x $?
Damit ist aber $ [mm] m_1(y) \geq m_1(x) [/mm] + 1 $ und da $ [mm] I_1(x) \subseteq I_1(y) [/mm] $ folgt: $ [mm] m_2(y) [/mm] > [mm] m_2(x) [/mm] $ im Widerspruch zur Maximalität.
|
|
|
| |
|
Hallo Reaper!
Das habe ich der Definition einer Dominanzrelation entnommen... zu jedem Paar $(x,y)$ mit $x [mm] \not= [/mm] y$ gilt immer entweder $xRy$ oder $yRx$.
In unserem Fall ist $x$ fest und das $y$ nach Annahme nicht in 2 Schritten erreichbar - insbesondere gilt nicht $xRy$. Also muß die andere Alternative gelten.
Wieder die Anschauung: bei einem Turnier "Jeder gegen Jeden" wird zu jeder Paarung ein eindeutiger Sieger ermittelt. Wenn $x$ nicht gegen $y$ gewonnen hat, dann aber $y$ gegen $x$.
Alles klar?
Lars
|
|
|
|
), aber von einer Dominanzrelation habe ich noch nicht gehört.
