Turnering (grafteori)

Turnering
En turnering med 4 topmøder. Denne turnering er 1-paradoksal. Dens scoresekvens er (1, 1, 2, 2).

Antal hjørner	$ikke$
Antal kanter	${\ displaystyle {\ frac {n (n-1)} {2}}}$

I matematik , inden for rammerne af grafteori , er en turnering en rettet graf opnået ved at orientere hver kant af en komplet ikke-rettet graf . Vi kan også tænke på det som en orientering (in) af en komplet graf eller som en rettet graf, hvor hvert par af hjørner er forbundet med en rettet kant og kun en.

Ansøgninger

Mange vigtige egenskaber ved turneringer er blevet udforsket af HG Landau for at modellere dominansforhold i grupper af kyllinger. De nuværende anvendelser af turneringer vedrører blandt andet teorien om valgsystemer samt teorien om valg i samfundet .

Navnet turnering kommer fra fortolkning af sådanne grafer som følge af en all-round turnering , hvor hver deltager møder hinanden deltager én gang og kun én gang, og hvor der ikke er noget slips. I grafen svarer hjørnerne til deltagerne, og kanterne svarer til resultaterne af de spillede spil, kanten går fra vinder til taber. Hvis deltageren slår deltageren , siger vi, at det dominerer , bemærket . $på$ $b$ $på$ $b$ $a \ højrepil b$

Stier og kredsløb

Hver turnering på et begrænset antal af knuder indeholder en hamiltonkreds , det vil sige en rettet sti passerer gennem knudepunkter én gang og kun én gang. Dette resultat skyldes László Rédei (en) i 1934. $ikke$ $ikke$

Demonstration

Lad os fortsætte med induktion på antallet af hjørner . $ikke$

Antag, at dette er sandt for . Eller en topturnering. Vælg et toppunkt på . Ved induktionshypotese har mindst en orienteret vej . Lad det maksimale indeks være sådan, at alle ( ) kontrollerer, at der findes en orienteret kant på en . I eksemplet figur , fordi der er kanter af og af i , men ikke af i . $ikke$ ${\ displaystyle T = (V, E)}$ $n + 1$ $på$ $V$ ${\ displaystyle V \ setminus \ {a \}}$ ${\ displaystyle (v_ {1}, v_ {2}, \ cdots, v_ {n})}$ ${\ displaystyle i \ i [0, n]}$ $v_ {j}$ ${\ displaystyle j \ leq i}$ $v_ {j}$ $på$ $jeg = 2$ $v_ {1}$ $v_ {2}$ $på$ $v_ {3}$ $på$

Bemærk, at stien er en rettet sti, der passerer gennem alle hjørnerne i grafen. Ejendommen gælder derfor også for . Da det desuden er sandt for en turnering med to hjørner, ved gentagelse er det sandt for alt fra to. ${\ displaystyle (v_ {1}, \ cdots, v_ {i}, a, v_ {i + 1}, \ cdots, v_ {n})}$ $n + 1$ $ikke$

Dette bevis er konstruktivt : det giver en algoritme, der gør det muligt at finde en Hamilton-sti. Mere effektive algoritmer, som kun Antag for at undersøge en række kanter rækkefølge af , er kendt. $O (n \ log n)$

Dette har den konsekvens, at en stærkt forbundet turnering , dvs. således at der er en sti mellem ethvert par af knuder, har en hamiltonsk kredsløb, det vil sige et lukket kredsløb og orienteret passerer gennem alle topmøderne kun én gang (resultat skyldes Paul Camion i 1959).

Et stærkere resultat er, at enhver stærkt forbundet turnerings top-pancyclique (in) : for ethvert toppunkt og for alle hvor er antallet af hjørner, er der en lang kredsløb igennem . $v$ ${\ displaystyle k \ in [3, n]}$ $ikke$ $k$ $v$

Binære relationer

En turnering defineres undertiden også som et binært forhold mellem og . Pr. Definition, hvis det dominerer , så dominerer det ikke . Vi kan bemærke denne definition på to måder: $R$ $E$ $E$ $på$ $b$ $b$ $på$

${\ displaystyle a \ rightarrow b \ Rightarrow b {\ cancel {\ mathcal {\ rightarrow}} a}$
${\ displaystyle \ forall (x, y) \ i E ^ {2}, x {\ mathcal {R}} y \ Rightarrow y {\ annuller {\ mathcal {R}}} x}$ med , forholdet mellem dominans. $R$

Vi siger derefter, at forholdet er asymmetrisk . Med denne definition kan vi let kontrollere, at dette binære forhold er irrefleksivt :

${\ displaystyle \ forall x \ i E \ quad x {\ annuller {\ mathcal {R}}} x}$ : Intet element kan relateres til sig selv. Faktisk kan en deltager ikke dominere sig selv.

Demonstration

Lad os ræsonnere med det absurde .

Lad os tage to deltagere og sådan, at og . $x$ $y$ $x = y$ ${\ displaystyle x {\ mathcal {R}} y}$

Efter hypotese indebærer dette . $x = y$ ${\ displaystyle x {\ mathcal {R}} y \ Rightarrow y {\ mathcal {R}} x}$

Nu, pr. Definition . ${\ displaystyle x {\ mathcal {R}} y \ Rightarrow y {\ annuller {\ mathcal {R}}} x}$

Dette resultat er derfor absurd, og den binære relation til en turnering er derfor refleksiv.

Vi kan bemærke, at en turnering:

Kan være forbigående. Hvis det ikke er tilfældet, siges det at være en paradoksal turnering.
Kan ikke være et samlet forhold, fordi det ikke er reflekterende.
Kan ikke være en ordrerelation, fordi den ikke er reflekterende.
Kan ikke være et ækvivalensforhold, fordi det hverken er refleksivt eller symmetrisk.

De binære relationer turnering ikke er turnerings matricer , har vi:

1 hvis ${\ displaystyle x {\ mathcal {R}} y}$
0 hvis ${\ displaystyle x {\ cancel {\ mathcal {R}}} y}$
0 hvis ${\ displaystyle x = y}$

Transitivitet og paradoksale turneringer

I virkelige turneringer forventes det, at hvis en person dominerer en person , og hvis igen dominerer en tredje person , så dominerer . Dette svarer til transitiviteten af det binære dominansforhold. $på$ $b$ $b$ $vs.$ $på$ $vs.$

Formelt anført giver dette følgende definition:

Vi kalder transitive en turnering , hvor: ${\ displaystyle T = (V, E)}$

{\ displaystyle \ forall (a, b, c) \ i V ^ {3}, (a \ rightarrow b {\ text {and}} b \ rightarrow c) \ Rightarrow a \ rightarrow c}

Givet en turnering T med n hjørner er følgende udsagn ækvivalente:

T er transitiv;
T er acyklisk ;
T indeholder ikke et kredsløb med længde 3;
Sekvensen af T- scores (se nedenfor) er ; ${\ displaystyle (0,1,2, \ cdots, n-1)}$
T har nøjagtigt en Hamilton-sti.

En deltager i en turnering, der vinder alle spil, er naturligvis vinderen af turneringen. Som figuren øverst i denne artikel viser, er det dog muligt, at en sådan vinder ikke eksisterer. En turnering, hvor hver deltager mister mindst et spil kaldes en 1-paradoksal turnering .

Mere generelt kaldes en turnering k-paradoksalt, hvis der for hver delmængde med elementer er en top i som for alle hjørner af . ${\ displaystyle T = (V, E)}$ $S$ $k$ $V$ $v_0$ ${\ displaystyle V \ setminus S}$ ${\ displaystyle v_ {0} \ rightarrow v}$ $v$ $S$

Scorer sekvens og sæt score

I en hverdagsturnering, hvis der ikke er nogen nettovinder (nogen der slår alle andre), kan vi prøve at vælge mellem kandidaterne ved at beregne deres score , det vil sige antallet af vundne spil.

Den sekvens af scorer for en turnering er den rækkefølge alfabetisk rækkefølge af grader der udgår fra knudepunkter af en turnering.

Den sæt turnering scorer er mængden af grader ud af turnering toppe.

Landaus sætning (1953) siger, at en sekvens af heltal er en sekvens af scores, hvis og kun hvis: ${\ displaystyle (s_ {1}, s_ {2}, \ cdots, s_ {n})}$

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

For eksempel er en sekvens af scores, fordi: ${\ displaystyle (1,1,2,2)}$

${\ displaystyle 0 \ leq 1 \ leq 1 \ leq 2 \ leq 2}$
${\ displaystyle 1 \ geq C_ {1} ^ {2}}$ fordi ; fordi ; fordi ${\ displaystyle 1 \ geq 0}$ ${\ displaystyle 1 + 1 \ geq C_ {2} ^ {2}}$ ${\ displaystyle 2 \ geq 1}$ ${\ displaystyle 1 + 1 + 2 \ geq C_ {3} ^ {2}}$ ${\ displaystyle 4 \ geq 3}$
${\ displaystyle 1 + 1 + 2 + 2 = C_ {4} ^ {2}}$ fordi ${\ displaystyle 6 = 6}$

Faktisk svarer dette til fortsættelsen af turneringsresultaterne øverst i artiklen.

Med hensyn til scoresættene beviste TX Yao, at ethvert ikke-frit sæt af positive eller nul heltal er scoringssættet for en bestemt turnering.

Turneringsmatrix

Det er naturligt at registrere resultaterne af en turnering i en tabel, der viser resultatet af hvert spil.

Vi kalder turneringsmatrix en firkantet matrix, hvis elementer er værd: $PÅ$ $a _ {{ij}}$

$1$ hvis ${\ displaystyle v_ {i} \ rightarrow v_ {j}}$
$-1$ hvis ${\ displaystyle v_ {j} \ rightarrow v_ {i}}$
${\ displaystyle 0}$ ja . $jeg = j$

En turneringsmatrix er lig med det modsatte af dens transponering (den er antisymmetrisk ).

Noter og referencer

(de) Lázló Rédei, “ Ein kombinatorischer Satz ” , Acta Litteraria Szeged , vol. 7,1934, s. 39-43.
(in) A. Bar-Noy og J. Naor , " Sortering, minimale feedback-sæt og Hamilton-stier i turneringer " , SIAM Journal on Discrete Mathematics , bind. 3, n o 1,1990, s. 7–20 ( DOI 10.1137 / 0403002 ).
Paul Camion , “ Hamiltonian stier og kredsløb med komplette grafer ”, CR Acad. Sci. Paris , vol. 249,1959, s. 2151-2152 ( læs online ).
JW Moon , “ Om underturneringer i en turnering, ” Canadian Mathematical Bulletin , bind. 9, nr . 3,1966, s. 297–301 ( DOI 10.4153 / CMB-1966-038-7 , læs online ), Sætning 1.
(i) HG Landau , " Vi dominans relationer og strukturen af animalske samfund. III. Betingelsen for en score-struktur ” , Bulletin of Mathematical Biophysics , bind. 15, nr . 21953, s. 143-148 ( DOI 10.1007 / BF02476378 ).
(in) TX Yao , " We Reid Conjecture Of Score Sets For Turneringer " , kinesisk Sci. Tyr. , Vol. 34,1989, s. 804-808

Se også

Kilder

(fr) Denne artikel er helt eller delvist taget fra Wikipedia-artiklen på engelsk med titlen " Turnering (grafteori) " ( se forfatterlisten ) .
(da) Denne artikel bruger indhold fra turneringssiden på PlanetMath under CC_BT-SA- licensen .

Eksternt link

(da) Eric W. Weisstein , ” Turnering ” , på MathWorld