Turnering (grafteori)

En turnering er en rettet graf , der opnås fra en urettet komplet graf ved at tildele en retning til hver kant. En turnering er således en digraf, hvor hvert par af hjørner er forbundet med en enkelt rettet bue.

Mange vigtige egenskaber ved turneringer overvejes af Landau [ 1] for at undersøge mønstret for kyllingedominans i en flok. Aktuelle anvendelser af turneringer omfatter blandt andet forskning i afstemning og kollektive valg . Turneringens navn kommer fra en grafisk fortolkning af resultaterne af en round robin-turnering , hvor hver spiller møder hver anden spiller præcis én gang, og hvor der ikke kan være uafgjort . I turneringsdigrafen svarer hjørnerne til spillerne. Buen mellem hvert par spillere er orienteret fra vinder til taber. Hvis spilleren slår spilleren , så siges den at dominere over . $-en$ $b$ $-en$ $b$

Stier og cyklusser

Enhver turnering med et endeligt antal hjørner indeholder en Hamiltonsk bane , det vil sige en rettet sti, der indeholder alle knudepunkter [2] . Dette kan let vises ved matematisk induktion på : lad udsagnet være sandt for , og lad der være en turnering med hjørner. Lad os vælge et toppunkt ved og lade være en rettet vej til . Lade være det maksimale antal sådan, at der for enhver er en bue fra til . Derefter $n$ $n$ $n$ $n$ $T$ $n+1$ $v_{0}$ $T$ $v_{1},v_{2},\ldots,v_{n}$ $T\setminus \{v_{0}\}$ $i\in \{0,\ldots ,n\}$ $j\leq i$ $v_{j}$ $v_{0}$

v_{1},\ldots,v_{i},v_{0},v_{{i+1}},\ldots,v_{n}

er den ønskede orienterede vej. Dette bevis giver også en algoritme til at finde en Hamilton-sti. Der kendes en mere effektiv algoritme, der kræver opregning af alle buer [3] . $\O(n\log n)$

Det betyder, at en strengt forbundet turnering har en Hamilton-cyklus [4] . Mere strengt er enhver stærkt forbundet turnering toppunkt-pancyklisk - for ethvert toppunkt v og for ethvert k fra tre til antallet af hjørner i turneringen er der en cyklus med længden k indeholdende v [5] . Desuden, hvis turneringen er 4-forbundet, kan et hvilket som helst par af hjørner forbindes med en Hamilton-sti [6] .

Transitivitet

En turnering, hvor og kaldes transitive . I en transitiv turnering kan hjørnerne ordnes fuldstændigt i rækkefølge . $((a\højrepil b)$ $(b\højrepil c))$ $\Højre pil$ $(a\højrepil c)$

Tilsvarende betingelser

Følgende udsagn for en turnering med n hjørner er ækvivalente:

T er transitiv.
T er acyklisk .
T indeholder ikke cyklusser af længde 3.
Rækkefølgen af antallet af sejre (sættet af halve udfald) T er {0,1,2,..., n − 1}.
T indeholder præcis én Hamilton-sti.

Ramsey teori

Transitive turneringer spiller en væsentlig rolle i Ramsey-teorien , svarende til den rolle, som kliker spiller i urettede grafer. Især indeholder enhver turnering med n hjørner en transitiv underturnering med knudepunkter [7] . Beviset er enkelt: Vælg et hvilket som helst toppunkt v som en del af denne underturnering og konstruer underturneringen rekursivt på sættet af enten indkommende naboer til v eller på sættet af udgående naboer, alt efter hvad der er størst. For eksempel indeholder enhver turnering med syv hjørner en transitiv turnering med tre hjørner. Paleys syv-top-turnering viser, at dette er det maksimale, der kan garanteres [7] . Reid og Parker [8] viste imidlertid, at denne grænse ikke er streng for nogle store værdier af n . $1+\lgulv \log _{2}n\rgulv$

Erdős og Moser [7] beviste, at der er n -vertex-turneringer uden transitive underturneringer af størrelse . Deres bevis bruger tælle : antallet af måder, hvorpå en transitiv turnering med k knudepunkter kan være indeholdt i en større turnering med n mærkede knudepunkter er $2+2\lgulv \log _{2}n\rgulv$

{\binom {n}{k}}k!2^{{{\binom {n}{2}}-{\binom {k}{2}}}},

og for k større end dette tal er det for lille til, at en transitiv turnering kan være i hver af de forskellige turneringer i det samme sæt af n mærkede hjørner. $2+2\lgulv \log _{2}n\rgulv$ $2^{{{\binom {n}{2))))$

Paradox-turneringer

Den spiller, der vinder alle spillene, bliver naturligvis vinderen af turneringen. Men som eksistensen af ikke-transitive turneringer viser, er der muligvis ikke en sådan spiller. En turnering, hvor hver spiller taber mindst et spil, kaldes en 1-paradoksal turnering. Mere generelt siges en turnering T =( V , E ) at være k -paradoksal, hvis der for en hvilken som helst k -elementdelmængde S af sættet V eksisterer et toppunkt v 0 , således at for alle . Ved hjælp af den probabilistiske metode viste Erdős , at for enhver fast k under betingelsen | v | ≥ k 2 2 k ln(2 + o(1)) næsten enhver turnering på V er k -paradoksal [9] . På den anden side viser et simpelt argument, at enhver k -paradoksal turnering skal have mindst 2 k +1 − 1 spillere, hvilket er blevet forbedret til ( k + 2)2 k −1 − 1 af Esther og György Sekeresami (1965) ) [10] . Der er en eksplicit metode til at konstruere k -paradoksale turneringer med k 2 4 k −1 (1 + o(1)) spillere udviklet af Graham og Spencer, nemlig Paley-turneringen [11] . $V\setminus S$ $v_{0}\rightarrow v$ $v\in S$

Kondensation

Kondensationen af enhver turnering er en transitiv turnering. Selvom turneringen ikke er transitiv, kan de stærkt forbundne komponenter i turneringen således bestilles fuldstændigt [12] .

Sekvenser af resultater og sæt af resultater

Sekvensen af turneringsresultater er en ikke-aftagende sekvens af udfalds-halvgrad af turneringens hjørner. Sættet af turneringsresultater er det sæt af heltal, der er halvgrader for udfaldet af turneringens toppunkter.

Landaus teorem (1953) - En ikke-aftagende sekvens af heltal er en sekvens af resultater, hvis og kun hvis: $(s_{1},s_{2},\cdots ,s_{n})$

$0\leq s_{1}\leq s_{2}\leq \cdots \leq s_{n}$
$s_{1}+s_{2}+\cdots +s_{i}\geq {i \choose 2},$ til $i=1,2,\cdots ,n-1$
$s_{1}+s_{2}+\cdots +s_{n}={n \vælg 2}.$

Lad være antallet af forskellige sekvenser af resultater af størrelse . Sekvensen starter med: $s(n)$ $n$ $s(n)$

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805 , 48107 , …

(sekvens A000571 i OEIS )

Winston og Kleitman beviste, at for en tilstrækkelig stor n

s(n)>c_{1}4^{n}n^{{-{5 \over 2}}},

hvor Takacs senere viste [13] ved hjælp af nogle plausible, men ubeviste formodninger om det $c_{1}=0,049.$

s(n)<c_{2}4^{n}n^{{-{5 \over 2}}},

hvor $c_{2}<4.858.$

Tilsammen indikerer det det

s(n)\in \Theta (4^{n}n^{{-{5 \over 2}}}).

Her afspejler den asymptotisk strenge binding . $\Theta$

Yao viste [14] at ethvert ikke-tomt sæt af ikke-negative heltal er udfaldssættet for nogle turneringer.

Se også

Noter

↑ HG Landau. Om dominansforhold og dyresamfunds struktur. III. Betingelsen for en partiturstruktur // Bulletin of Mathematical Biophysics. - 1953. - T. 15 , no. 2 . - S. 143-148 . - doi : 10.1007/BF02476378 .
↑ Lazlo Redei. Ein kombinatorischer Satz // Acta Litteraria Szeged. - 1934. - T. 7 . - S. 39-43 .
↑ A. Bar-Noy, J. Naor. Sortering, minimale feedbacksæt og Hamilton-stier i turneringer // SIAM Journal om diskret matematik . - 1990. - T. 3 , udg. 1 . - S. 7-20 . - doi : 10.1137/0403002 .
↑ Chemins et circuits hamiltoniens des graphes complets // Comptes Rendus de l'Académie des Sciences de Paris. - 1959. - T. 249 . - S. 2151-2152 .
↑ JW Moon. Om underturneringer til en turnering // Canadian Mathematical Bulletin. - 1966. - T. 9 , no. 3 . - S. 297-301 . - doi : 10.4153/CMB-1966-038-7 . Arkiveret fra originalen den 3. marts 2016.
↑ Carsten Thomassen. Hamiltonian-Connected Tournaments // Journal of Combinatorial Theory, Series B. - 1980. - V. 28 , no. 2 . - S. 142-163 . - doi : 10.1016/0095-8956(80)90061-1 .
↑ 1 2 3 Paul Erdős, Leo Moser. Om repræsentationen af rettede grafer som foreninger af ordrer // Magyar Tud. Akad. Måtte. Kutato Int. Kozl. - 1964. - T. 9 . - S. 125-132 . Arkiveret fra originalen den 13. december 2013.
↑ K.B. Reid, E.T. Parker. Modbevis for en formodning om Erdös og Moser // Journal of Combinatorial Theory. - 1970. - T. 9 , no. 3 . - S. 225-238 . - doi : 10.1016/S0021-9800(70)80061-8 .
↑ Paul Erdős. Om et problem i grafteori // The Mathematical Gazette. - 1963. - T. 47 . - S. 220-223 . — . Arkiveret fra originalen den 22. december 2014.
↑ Esther Szekeres, George Szekeres. Om et problem med Schütte og Erdős // The Mathematical Gazette. - 1965. - T. 49 . - S. 290-293 .
↑ Ronald Graham, Joel Spencer. En konstruktiv løsning på et turneringsproblem // Canadian Mathematical Bulletin. Bulletin Canadien de Mathematiques. - 1971. - T. 14 . - S. 45-48 .
↑ Frank Harary, Leo Moser. Teorien om round robin-turneringer // American Mathematical Monthly. - 1966. - T. 73 , no. 3 . - S. 231-246 . - doi : 10.2307/2315334 . — .
↑ Lajos Takacs. En Bernoulli-udflugt og dens forskellige anvendelser // Fremskridt i anvendt sandsynlighed. - 1991. - T. 23 , no. 3 . - S. 557-585 . - doi : 10.2307/1427622 . — .
↑ T.X. Yao. Om Reid-formodning om scoresæt til turneringer // kinesisk videnskabsmand. Tyr. - 1989. - T. 34 . - S. 804-808 .