Turnaj (teorie grafů)

Turnaj je orientovaný graf získaný z neorientovaného kompletního grafu přiřazením směru každé hraně. Turnaj je tedy digraf, ve kterém je každá dvojice vrcholů spojena jediným směrovaným obloukem.

Landau [ 1] zvažuje mnoho důležitých vlastností turnajů , aby prozkoumal vzor dominance kuřat v hejnu. Současné aplikace turnajů zahrnují mimo jiné výzkum hlasování a kolektivní volby Název turnaje pochází z grafického znázornění výsledků turnaje typu round robin , ve kterém se každý hráč utká s každým hráčem právě jednou a ve kterém nemůže dojít k remíze . V turnajovém digrafu odpovídají vrcholy hráčům. Oblouk mezi každou dvojicí hráčů je orientován od vítěze k poraženému. Pokud hráč porazí hráče , pak se říká , že dominuje nad . $A$ $b$ $A$ $b$

Cesty a cykly

Každý turnaj s konečným počtem vrcholů obsahuje hamiltonovskou cestu , tedy směrovanou cestu obsahující všechny vrcholy [2] . To lze snadno ukázat matematickou indukcí na : nechť je výrok pravdivý pro , a nechť existuje nějaký turnaj s vrcholy. Zvolme vrchol at a nechť je směrovaná cesta k . Dovolit je maximální číslo takové, že pro všechny existuje oblouk od do . Pak $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}

je požadovaná orientovaná cesta. Tento důkaz také poskytuje algoritmus pro nalezení hamiltonovské cesty. Je znám efektivnější algoritmus, který vyžaduje výčet všech oblouků [3] . $\O(n\log n)$

To znamená, že přísně propojený turnaj má hamiltonovský cyklus [4] . Přesněji řečeno, každý silně propojený turnaj je vertex-pancyklický — pro jakýkoli vrchol v a pro libovolné k od tří do počtu vrcholů v turnaji existuje cyklus délky k obsahující v [5] . Navíc, pokud je turnaj 4-souvislý, může být libovolný pár vrcholů spojen hamiltonovskou cestou [6] .

Tranzitivita

Turnaj, ve kterém a se nazývá tranzitivní . V tranzitivním turnaji mohou být vrcholy kompletně seřazeny v pořadí dosažitelnosti . $((a\šipka doprava b)$ $(b\šipka doprava c))$ $\Šipka doprava$ $(a\šipka doprava c)$

Ekvivalentní podmínky

Následující tvrzení pro turnaj s n vrcholy jsou ekvivalentní:

T je tranzitivní.
T je acyklický .
T neobsahuje cykly délky 3.
Posloupnost počtu výher (množina polovičních výsledků) T je {0,1,2,…, n − 1}.
T obsahuje právě jednu hamiltonovskou cestu.

Ramseyho teorie

Tranzitivní turnaje hrají v Ramseyově teorii zásadní roli , podobnou roli, kterou hrají kliky v neorientovaných grafech. Konkrétně každý turnaj s n vrcholy obsahuje tranzitivní dílčí turnaj s vrcholy [7] . Důkaz je jednoduchý: zvolte libovolný vrchol v jako součást tohoto dílčího turnaje a sestrojte dílčí turnaj rekurzivně na množině buď příchozích sousedů v nebo na množině odchozích sousedů, podle toho, co je větší. Například jakýkoli turnaj se sedmi vrcholy obsahuje tranzitivní turnaj se třemi vrcholy. Paleyho turnaj sedmi nejlepších ukazuje, že toto je maximum, které lze zaručit [7] . Reid a Parker [8] však ukázali, že tato hranice není přísná pro některé velké hodnoty n . $1+\lpatro \log _{2}n\rpatro$

Erdős a Moser [7] dokázali, že existují n -vertexové turnaje bez tranzitivních subturnajů velikosti . Jejich důkaz používá počítání : počet způsobů, jakými může být tranzitivní turnaj s k vrcholy obsažen ve větším turnaji s n označenými vrcholy je $2+2\lpatro \log _{2}n\rpatro$

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

a pro k větší než toto číslo je příliš malé na to, aby tranzitivní turnaj byl v každém z různých turnajů stejné sady n označených vrcholů. $2+2\lpatro \log _{2}n\rpatro$ $2^{{{\binom {n}{2))))$

Paradoxové turnaje

Hráč, který vyhraje všechny hry, se přirozeně stane vítězem turnaje. Jak však ukazuje existence netranzitivních turnajů, takový hráč nemusí být. Turnaj, ve kterém každý hráč prohraje alespoň jednu hru, se nazývá 1-paradoxní turnaj. Obecněji se o turnaji T =( V , E ) říká , že je k -paradoxní, pokud pro jakoukoli k -prvkovou podmnožinu S množiny V existuje vrchol v 0 v takovém, že pro všechny . Pomocí pravděpodobnostní metody Erdős ukázal, že pro jakékoli pevné k za podmínky | v | ≥ k 2 2 k ln(2 + o(1)) téměř každý turnaj na V je k -paradoxní [9] . Na druhou stranu jednoduchý argument ukazuje, že každý k -paradoxní turnaj musí mít alespoň 2 k +1 − 1 hráčů, což Esther a György Sekeresami (1965 ) zlepšili na ( k + 2)2 k −1 − 1 ) [10] . Graham a Spencer vyvinuli explicitní metodu pro konstrukci k -paradoxních turnajů s k 2 4 k −1 (1 + o(1)) hráčů, konkrétně Paleyho turnaj [11] . $V\setminus S$ $v_{0}\rightarrow v$ $v\in S$

Kondenzace

Kondenzace jakéhokoli turnaje je tranzitivní turnaj. I když tedy turnaj není tranzitivní, lze pevně propojené komponenty turnaje kompletně objednat [12] .

Posloupnosti výsledků a sady výsledků

Posloupnost turnajových výsledků je neklesající posloupnost výsledných půlstupňů vrcholů turnaje. Množina výsledků turnaje je množina celých čísel, která jsou půlstupněmi výsledku vrcholů turnaje.

Landauův teorém (1953) - Neklesající posloupnost celých čísel je posloupnost výsledků právě tehdy, když: $(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 \vyberte 2},$ pro $i=1,2,\cdots ,n-1$
$s_{1}+s_{2}+\cdots +s_{n}={n \vyberte 2}.$

Dovolit je počet různých sekvencí výsledků velikosti . Sekvence začíná: $s(n)$ $n$ $s(n)$

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

(sekvence A000571 v OEIS )

Winston a Kleitman dokázali, že pro dostatečně velké n

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

kde Takacs později ukázal [13] pomocí nějakého věrohodného, ale neprokázaného dohadu, že $c_{1}=0,049.$

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

kde $c_{2}<4 858.$

Dohromady to naznačuje

s(n)\in \Theta (4^{n}n^{{-{5 \přes 2}}}).

Zde se odráží asymptoticky přísná vazba . $\Theta$

Yao ukázal [14] , že jakákoli neprázdná sada nezáporných celých čísel je výslednou množinou pro nějaký turnaj.

Viz také

Poznámky

↑ HG Landau. O vztazích dominance a struktuře zvířecích společností. III. Podmínka pro strukturu skóre // Bulletin of Mathematical Biophysics. - 1953. - T. 15 , čís. 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. Třídění, minimální sady zpětné vazby a Hamiltonovy cesty v turnajích // SIAM Journal on Discrete Mathematics . - 1990. - T. 3 , vydání. 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. O dílčích turnajích turnaje // Canadian Mathematical Bulletin. - 1966. - T. 9 , no. 3 . - S. 297-301 . - doi : 10.4153/CMB-1966-038-7 . Archivováno z originálu 3. března 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. O reprezentaci orientovaných grafů jako svazků uspořádání // Magyar Tud. Akad. Rohož. Kutato Int. Kozl. - 1964. - T. 9 . - S. 125-132 . Archivováno z originálu 13. prosince 2013.
↑ K.B. Reid, E.T. Parker. Vyvrácení domněnky Erdöse a Mosera // Journal of Combinatorial Theory. - 1970. - T. 9 , no. 3 . - S. 225-238 . - doi : 10.1016/S0021-9800(70)80061-8 .
↑ Paul Erdős. K problému v teorii grafů // The Mathematical Gazette. - 1963. - T. 47 . - S. 220-223 . — . Archivováno z originálu 22. prosince 2014.
↑ Esther Szekeres, George Szekeres. K problému Schütteho a Erdőse // The Mathematical Gazette. - 1965. - T. 49 . - S. 290-293 .
↑ Ronald Graham, Joel Spencer. Konstruktivní řešení turnajového problému // Canadian Mathematical Bulletin. Bulletin Canadien de Mathematics. - 1971. - T. 14 . - S. 45-48 .
↑ Frank Harary, Leo Moser. Teorie kruhových turnajů // American Mathematical Monthly. - 1966. - T. 73 , čís. 3 . - S. 231-246 . - doi : 10.2307/2315334 . — .
↑ Lajos Takacs. Bernoulliho exkurze a její různé aplikace // Pokroky v aplikované pravděpodobnosti. - 1991. - T. 23 , no. 3 . - S. 557-585 . - doi : 10.2307/1427622 . — .
↑ T.X. Yao. On Reid Conjecture Of Score Sets for Tournaments // Chinese Sci. Býk. - 1989. - T. 34 . - S. 804-808 .