WikiDer > Turnieranzahl

Ein starkes Turnier mit vier Teilnehmern.

EIN Turniergrafik, oder alleine Turnier, in dem Graphentheorie ist ein vollständige Zählung, in dem man jeder Seite eine Richtung zuweist, so dass sie zu einem gerichteten Graphen wird.

Der Name "Turnierzählung" kommt von der Interpretation einer solchen Zählung als Ergebnis von Wettbewerbsformular, bei dem jeder Spieler einmal gegen jeden anderen Spieler spielt und bei dem kein Unentschieden möglich ist. Eine Seite ab in einer solchen Zählung stellt ein Gewinnspiel dar und richtet sich nach dem Gewinner ein zum Verlierer b. Es heißt dann einbdominiert und schreibe das als ${displaystyle aightarrow b}$. Punktzahl des Spielers ein ist die Anzahl der Male, die ein hat gewonnen, das ist die Anzahl der ausgehenden Seiten von ein an andere Spieler gerichtet, d. h. die Anzahl der anderen Spieler, die ein dominiert.

Turniere sind vielleicht die am besten untersuchte Klasse von gerichteten Graphen.^[1]

Formale Definition

Eine Turnierzählung ist eine gerichtete Zählung ${Anzeigestil (V,E)}$, für die:

• ${Anzeigestil V}$ hat mindestens zwei Elemente ${Anzeigestil x}$ und ${Anzeigestil y}$,
• für alle ${Anzeigestil x,yin V}$ mit ${displaystyle xot=y}$ gilt ${Anzeigestil (x,y)in E}$ oder ${Anzeigestil (y,x)in E}$,
• für alle ${Anzeigestil x,yin V}$ mit ${displaystyle xot=y}$ gilt ${displaystyle (x,y)ot in E}$ oder ${displaystyle (y,x)ot in E}$,
• für alle ${Anzeigestil xin V}$ gilt ${displaystyle (x,x)ot in E}$.

Man kann ein Turnier auch definieren als a Doppelbeziehung${Anzeigestil R}$ auf einer Sammlung ${Anzeigestil E}$ Das unflexibel, antisymmetrisch und total. Das heißt, für jedes Paar ${Anzeigestil(x,y)}$ Elemente aus ${Anzeigestil E}$ gilt: entweder ${Anzeigestil x=y}$, oder ${Anzeigestil x R y}$, oder ${displaystyle yRx}$.

Eigenschaften

Jedes endliche Turnier zählt mit ${displaystyle n}$ Knoten enthält eine ungerade Zahl Hamilton-Pfade. Ein Hamilton-Pfad ist ein gerichteter Pfad entlang aller ${displaystyle n}$ Knoten.

Das bedeutet, dass es in jedem Turniergraphen mindestens einen Hamilton-Pfad geben wird. Letzteres geht mit volle Einweisung nach der Anzahl der Knoten ${displaystyle n}$ der Turnierzahl nachgewiesen.

• Der Induktionsstart, nur für den Fall ${Anzeigestil n=2}$, ist selbsterklärend. ${Anzeigestil x}$ hat entweder gewonnen oder verloren gegen ${Anzeigestil y}$, zeigt der Hamilton-Pfad vom Gewinner zum Verlierer.
• Die Induktionsannahme ist, dass der Satz für einen Turniergraphen mit . gilt ${displaystyle n}$ Knoten.
• Der Induktionsschritt läuft wie folgt ab. Angenommen, in einem Turnier wurden alle Matches gespielt und es gibt einen Hamilton-Pfad im Turniergraphen. Das ist gegeben. Wenn ein neuer Spieler einmal gegen alle vorherigen Spieler spielt, nimmt dieser neue Spieler seinen Platz zwischen dem Hamilton-Pfad des anderen, der ersten Spieler ein.

Betrachten Sie die Turniergrafik ${Anzeigestil T}$ mit ${displaystyle n1}$ Knoten. Wählen Sie eine Schaltfläche ${displaystyle v_{0}}$ im ${Anzeigestil T}$ und betrachten einen gerichteten Weg ${displaystyle v_{1},v_{2},ldots ,v_{n}}$ im ${displaystyle Tsetminus {v_{0}}}$. Paar ${displaystyle iin {0,ldots,n}}$ der größte Index, so dass für jeden ${displaystyle jleq i}$ es gibt eine gerichtete Seite von ${displaystyle v_{j}}$ zu ${displaystyle v_{0}}$.

wenn ${Anzeigestil i=n}$, dann ist ${displaystyle v_{1},v_{2},ldots,v_{n},v_{0}}$ ein Hamilton-Pfad von ${Anzeigestil T}$.

wenn ${displaystyle i$, dann ist ${displaystyle v_{1},ldots ,v_{i},v_{0},v_{i 1},ldots ,v_{n}}$ ein Hamilton-Pfad von ${Anzeigestil T}$.

Die Tatsache, dass es eine fokussierte Seite von ${displaystyle v_{0}}$ zu ${displaystyle v_{i 1}}$ folgt daraus, dass ${Anzeigestil i}$ ist der größte Index, so dass für jeden ${displaystyle jleq i}$ eine Seite von ${displaystyle v_{j}}$ zu ${displaystyle v_{0}}$ geht.

Starkes Turnier

Ein Turnier ist stark oder stark verbunden, wenn zwischen jedem Knotenpaar X und ja ein Pfad existiert, der in beginnt X und endet in ja. Ein Satz von Paul Camion von 1959 besagt, dass ein Turnier stark verbunden verbonden ist dann und nur dann, wenn das Turnier hat einen Hamilton-Zyklus, einen geschlossenen Hamilton-Pfad. Wann ein von b gewinnt und b von c gewinnt, in einem starken Turnier ist das nicht sicher ein auch von c Gewinnt. Mit nur drei Spielern ist es nur ein starkes Turnier, wenn c von ein Gewinnt.

Die Knoten in einem starken Turnier werden panzyklisch genannt: jeder Knoten ${Anzeigestil v}$ eines starken Turniers gehört zu einem Zyklus, einem geschlossenen Weg, der Länge ${displaystyle k}$ vor dem ${Anzeigestil k=3,4,Punkte,n}$, mit ${displaystyle ngeq 3}$ die Anzahl der Knoten im Diagramm.

S(n), die Anzahl der unterschiedlich starken Turniere mit nein Knoten, mit nein = 3, 4, 5, 6, 7, 8, ... ist 2, 24, 544, 22320, 1677488, 236522496, ... ,^[2] Warteschlange A054946 im OEIS.

Transitive Turnier

Ein transitives Turnier mit 8 Teilnehmern. ${displaystyle v_{a}Eightarrow v_{b}Linksrightarrow a$

Ein Turnier, für das immer gilt, wenn ein von b gewinnt und b von c Gewinnt, ein auch von c wins ist ein transitives Turnier. Im Turnier gibt es ein Gesamtbestellung. Die Abbildung rechts ist ein Beispiel für ein transitives Turnier.

Formal ist ein transitives Turnier definiert als

Turnier ${Anzeigestil T=(V,E)}$ ist transitiv, wenn

${Displaystyle forall (a,b,c)in V^{3},(Aightarrow b{ ext{ and }}bightarrow c)Rightarrow aightarrow c}$

In einem transitiven Turnier tritt genau ein Hamilton-Pfad auf. Ein transitives Turnier enthält keine Zyklen. Es ist das Gegenteil eines starken Turniers.

Die Punktzahlen der Teilnehmer eines transitiven Turniers, geordnet vom kleinsten zum größten, sind die Menge {0,1,2,...,nein − 1}.

Paradoxes Turnier

In einem transitiven Turnier gibt es einen Teilnehmer, der alle seine Matches gewinnt. Das ist bei echten Wettkämpfen selten. Das Beispiel in der Abbildung oben mit 4 Teilnehmern ist beispielsweise kein transitives Turnier. Ein Turnier, bei dem jeder Spieler mindestens einmal verliert, wird als 1-paradoxes Turnier bezeichnet.

Im Allgemeinen ein Turnier k-paradox wie für jede Teilmenge so mit k Elemente aus V für alle Knöpfe da v im so Dort k andere Knoten ${displaystyle v_{i}}$ im ${displaystyle Vsetminus S}$ sein, damit ${displaystyle v_{i}Eightarrow v}$ .

Sogar Turnier

Ein Turnier ist gerade dann, wenn jeder Knoten die gleiche Anzahl an eingehenden und ausgehenden Seiten hat, dies sind Graphen mit Eulerscher Orientierung. Ein gerades Turnier hat per Definition eine ungerade Anzahl von Teilnehmern oder Knoten, die alle die gleiche Punktzahl haben. Die Anzahl der verschiedenen geraden Turniere mit 3, 5, 7, 9, 11... Teilnehmern beträgt: 1, 1, 3, 15, 1223... Reihe A096368 im OEIS.

Alle geraden Turniere mit der gleichen Teilnehmerzahl haben die gleiche Anzahl von Dreiecken und die gleiche Anzahl von transitiven Dreiergruppen. Ein Dreieck ist eine Reihe von drei Seiten (x,y), (y, z), (z,x), die einen Kreis bilden, ein transitives Tripel besteht aus drei Seiten der Form (x,y), (y, z), (x,z).

Die Anzahl der transitiven Triples in einem geraden Turnier mit nein knoten ist ${displaystyle {frac {n(n-1)(n-3)}{8}}}$. Die Anzahl der Dreiecke ist ${displaystyle {frac {n(n^{2}-1)}{24}}}$.^[3]

Beispiel

Dies ist ein Beispiel für ein gerades Turnier mit 7 Teilnehmern, jeder Knoten hat drei Innen- und drei Außenseiten. Es gibt 21 Seiten, das sind die Pfeile in der Grafik, zum Beispiel 14 Dreiecke AF-FC-CA, und 21 transitive Tripel, zum Beispiel CE-ED-CD.

Reduzierbares Turnier

Ein Turnier gilt als reduzierbar, wenn der Satz V der Knoten können in zwei getrennte Turniergraphen aufgeteilt werden so und t, wobei jeder Knoten ist so jeder Knoten aus t dominiert. V = sot, mit ${displaystyle-Sichtpfeil T}$. Ist dies nicht möglich, ist das Turnier nicht reduzierbar.

Ein Turnier ist genau dann nicht reduzierbar, wenn es hochgradig verbunden ist. Ein transitives Turnier ist reduzierbar. Zum Beispiel kann das obige Beispiel mit 8 Knoten in zwei Turniere mit den Knotensätzen {1,2,3} und {4,5,6,7,8} oder {1,2,3,4} aufgeteilt werden. und { 5,6,7,8} und so weiter. Jedes Turnier kann als Summe eines oder mehrerer nicht reduzierbarer Turniere geschrieben werden. Die Teilnehmer können dann in ungefähr gleich gute Spielergruppen aufgeteilt werden. Es gibt deutliche Unterschiede zwischen den verschiedenen Spielergruppen.

Punktesammlungen und Punktereihen

Die Punktzahl eines Teilnehmers an einem Turnier ist die Anzahl der Spiele, die er gewonnen hat. Dies ist die Anzahl der ausgehenden Seiten eines Knotens im Turniergraphen.

Der Punktesatz ist der Sammlung der Anzahl der ausgehenden Seiten aller Knoten. Es ist einfach, den Punktesatz eines Turniers zu bestimmen, aber ein Turnier aus einem gegebenen Punktesatz zu konstruieren, ist ein schwieriges Problem. Die Wertungsreihe oder der Wertungsvektor ist die geordnete Reihe von Wertungen oder die Anzahl der ausgehenden Seiten, geordnet von der kleinsten zur größten.

Satz von Landau^[4] sagt eine Reihe ${displaystyle s_{1},s_{2},cdots ,s_{n}}$ von nicht-negativen ganzen Zahlen ist genau dann eine Wertungssequenz, wenn:

1. ${displaystyle 0leq s_{1}leq s_{2}leq cdots leq s_{n}}$
2. ${displaystyle s_{1} s_{2} cdots s_{i}geq C_{i}^{2},{mbox{for }}i=1,2,cdots ,n-1}$
3. ${displaystyle s_{1} s_{2} cdots s_{n}=C_{n}^{2}}$

${displaystyle C_{n}^{2}}$entspricht der Gesamtzahl der Seiten in der Turnieranzahl.

Mehrere Turniere können dieselbe Punktereihe haben. Peter M. Gibson leitete 1983 einen Ausdruck für die obere Grenze der Anzahl von Turnieren mit einer gegebenen Punktereihe oder einen Punktevektor ab.^[5]

Die Anzahl der möglichen unterschiedlichen Wertungsreihen von Turnieren mit nein = 0, 1, 2, 3, ... Teilnehmer ist, Reihe A000571 im OEIS, 1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, ...

T.X. jao^[6] hat bewiesen, dass jede endliche Menge von nicht-negativen ganzen Zahlen die Ergebnismenge eines bestimmten Turniers ist. K.B. Reid hatte dies als Verdacht 1978 formuliert.

Turniermatrix

Die Ergebnisse eines Turniers können auch sein Matrix werden angezeigt:

1 wenn ${displaystyle v_{i}ightarrow v_{j}}$

-1 wenn ${displaystyle v_{j}ightarrow v_{i}}$

0, wenn das Ergebnis zwischen . liegt ich und j ist noch nicht bekannt und wann ich=j.

Die Elemente auf der Diagonale bleiben 0.

Eine solche Matrix ein ist ein antisymmetrische Matrix: das transponierte Matrix von ein entspricht dem Gegenteil von ein:

${Displaystil A^{T}=-A}$

Die Definition eines Turniers wurde so gewählt, dass es vollständig gespielt wird. Die Turniermatrix des Turniers mit vier Teilnehmern in der obigen Abbildung sieht wie folgt aus:

${displaystyle { egin{bmatrix}0&1&-1&1/-1&0&-1&1/1&1&0&-1/-1&-1&1&0end{bmatrix}}}$

Externer Link

• (und) Mathworld, Turnier.