Turneu (teoria graficelor)

Un turneu este un grafic direcționat obținut dintr -un grafic complet nedirecționat prin alocarea unei direcții fiecărei margini. Astfel, un turneu este un digraf în care fiecare pereche de vârfuri este conectată printr-un singur arc direcționat.

Multe proprietăți importante ale turneelor sunt luate în considerare de către Landau [ 1] pentru a investiga modelul de dominanță a puiului într-un turmă. Aplicațiile actuale ale turneelor includ, printre altele, cercetarea privind votul și alegerea colectivă . Numele turneului provine dintr-o interpretare grafică a rezultatelor unui turneu round robin , în care fiecare jucător se confruntă cu fiecare alt jucător exact o dată și în care nu pot exista remize . În digraful turneului, vârfurile corespund jucătorilor. Arcul dintre fiecare pereche de jucători este orientat de la câștigător la învins. Dacă jucătorul îl bate pe jucător , atunci se spune că domină . $A$ $b$ $A$ $b$

Căi și cicluri

Orice turneu cu un număr finit de vârfuri conține o cale hamiltoniană , adică o cale direcționată care conține toate vârfurile [2] . Acest lucru poate fi demonstrat cu ușurință prin inducerea matematică pe : să fie afirmația adevărată pentru , și să existe un turneu cu vârfuri. Să alegem un vârf la și să fie o cale direcționată către . Fie numărul maxim astfel încât pentru oricare să existe un arc de la până la . Apoi $n$ $n$ $n$ $n$ $T$ $n+1$ $v_{0}$ $T$ $v_{1},v_{2},\ldots ,v_{n}$ $T\setminus \{v_{0}\}$ $i\în \{0,\ldots ,n\}$ $j\leq i$ $v_{j}$ $v_{0}$

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

este calea orientată dorită. Această demonstrație oferă, de asemenea, un algoritm pentru găsirea unei căi hamiltoniene. Este cunoscut un algoritm mai eficient care necesită enumerarea tuturor arcurilor [3] . $\O(n\log n)$

Aceasta înseamnă că un turneu strict conectat are un ciclu hamiltonian [4] . Mai strict, orice turneu puternic conectat este vârf-panciclic — pentru orice vârf v și pentru orice k de la trei până la numărul de vârfuri din turneu, există un ciclu de lungime k care conține v [5] . Mai mult, dacă turneul este 4-conectat, orice pereche de vârfuri poate fi conectată printr-o cale hamiltoniană [6] .

Tranzitivitate

Un turneu în care și se numește tranzitiv . Într-un turneu tranzitiv, vârfurile pot fi ordonate complet în ordinea accesibilității . $((a\săgeată la dreapta b)$ $(b\săgeată la dreapta c))$ $\Sageata dreapta$ $(a\rightarrow c)$

Condiții echivalente

Următoarele afirmații pentru un turneu cu n vârfuri sunt echivalente:

T este tranzitiv.
T este aciclic .
T nu conține cicluri de lungime 3.
Secvența numărului de victorii (setul de jumătăți de rezultate) T este {0,1,2,..., n − 1}.
T conține exact o cale hamiltoniană.

Teoria Ramsey

Turneele tranzitive joacă un rol esențial în teoria Ramsey , similar cu rolul jucat de clicurile în graficele nedirecționate. În special, orice turneu cu n vârfuri conține un subturneu tranzitiv cu vârfuri [7] . Dovada este simplă: alegeți orice vârf v ca parte a acestui subturneu și construiți recursiv subturniul fie pe mulțimea vecinilor de intrare ai lui v , fie pe mulțimea vecinilor care ies, oricare dintre acestea este mai mare. De exemplu, orice turneu cu șapte vârfuri conține un turneu tranzitiv cu trei vârfuri. Turneul cu șapte topuri al lui Paley arată că acesta este maximul care poate fi garantat [7] . Cu toate acestea, Reid și Parker [8] au arătat că această limită nu este strictă pentru unele valori mari ale lui n . $1+\lfloor \log _{2}n\rfloor$

Erdős și Moser [7] au demonstrat că există turnee n -vertice fără subturnee tranzitive de dimensiune . Dovada lor folosește numărarea : numărul de moduri în care un turneu tranzitiv cu k vârfuri poate fi conținut într-un turneu mai mare cu n vârfuri etichetate este $2+2\lfloor \log _{2}n\rfloor$

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

iar pentru k mai mare decât acest număr este prea mic pentru ca un turneu tranzitiv să fie în fiecare dintre turneele diferite ale aceluiași set de n vârfuri etichetate. $2+2\lfloor \log _{2}n\rfloor$ $2^{{{\binom {n}{2))))$

Turnee Paradox

Jucătorul care câștigă toate jocurile va fi în mod natural câștigătorul turneului. Totuși, după cum arată existența turneelor netranzitive, este posibil să nu existe un astfel de jucător. Un turneu în care fiecare jucător pierde cel puțin un joc se numește turneu 1-paradoxal. Mai general , un Turneu T =( V , E ) se spune a fi k - paradoxal dacă pentru orice k - element submulțime S din mulțimea V există un vârf v 0 astfel încât pentru toate . Folosind metoda probabilistică , Erdős a arătat că pentru orice k fix în condiția | v | ≥ k 2 2 k ln(2 + o(1)) aproape orice turneu de pe V este k -paradoxal [9] . Pe de altă parte, un argument simplu arată că orice turneu k -paradoxal trebuie să aibă cel puțin 2 k +1 − 1 jucători, care a fost îmbunătățit la ( k + 2)2 k −1 − 1 de Esther și György Sekeresami (1965). ) [ 10] . Există o metodă explicită de construire a turneelor k -paradoxale cu k 2 4 k −1 (1 + o(1)) jucători dezvoltată de Graham și Spencer, și anume turneul Paley [11] . $V\setminus S$ $v_{0}\rightarrow v$ $v\în S$

Condens

Condensarea a oricărui turneu este un turneu tranzitiv. Astfel, chiar dacă turneul nu este tranzitiv, componentele puternic conectate ale turneului pot fi ordonate complet [12] .

Secvențe de rezultate și seturi de rezultate

Secvența rezultatelor turneului este o secvență nedescrescătoare a semigradelor de rezultat ale vârfurilor turneului. Setul de rezultate ale turneului este setul de numere întregi care sunt semigrade ale rezultatului nodurilor turneului.

Teorema lui Landau (1953) - O succesiune de numere întregi nedescrescătoare este o succesiune de rezultate dacă și numai dacă: $(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},$ pentru $i=1,2,\cdots ,n-1$
$s_{1}+s_{2}+\cdots +s_{n}={n \alege 2}.$

Fie numărul de secvențe distincte de rezultate de dimensiune . Secvența începe cu: $s(n)$ $n$ $s(n)$

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

(secvența A000571 în OEIS )

Winston și Kleitman au demonstrat că pentru n suficient de mare

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

unde Takacs a arătat mai târziu [13] folosind o presupunere plauzibilă dar nedovedită că $c_{1}=0,049.$

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

Unde $c_{2}<4.858.$

Împreună, acest lucru indică faptul că

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

Aici reflectă limita strictă asimptotic . $\Theta$

Yao a arătat [14] că orice set nevid de numere întregi nenegative este rezultatul stabilit pentru un anumit turneu.

Vezi și

Note

↑ HG Landau. Despre relațiile de dominanță și structura societăților animale. III. Condiția pentru o structură de scor // Buletin de Biofizică Matematică. - 1953. - T. 15 , nr. 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. Sortare, seturi minime de feedback și căi Hamilton în turnee // SIAM Journal on Discrete Mathematics . - 1990. - T. 3 , nr. 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. Despre subturneele unui turneu // Canadian Mathematical Bulletin. - 1966. - T. 9 , nr. 3 . - S. 297-301 . - doi : 10.4153/CMB-1966-038-7 . Arhivat din original pe 3 martie 2016.
↑ Carsten Thomassen. Hamiltonian-Connected Tournaments // Journal of Combinatorial Theory, Seria B. - 1980. - V. 28 , nr. 2 . - S. 142-163 . - doi : 10.1016/0095-8956(80)90061-1 .
↑ 1 2 3 Paul Erdős, Leo Moser. Despre reprezentarea graficelor dirijate ca uniuni de ordonanțe // Magyar Tud. Akad. Mat. Kutato Int. Kozl. - 1964. - T. 9 . - S. 125-132 . Arhivat din original pe 13 decembrie 2013.
↑ K.B. Reid, E.T. Parker. Infirmarea unei conjecturi a lui Erdös și Moser // Journal of Combinatorial Theory. - 1970. - T. 9 , nr. 3 . - S. 225-238 . - doi : 10.1016/S0021-9800(70)80061-8 .
↑ Paul Erdős. Despre o problemă în teoria grafurilor // The Mathematical Gazette. - 1963. - T. 47 . - S. 220-223 . — . Arhivat din original pe 22 decembrie 2014.
↑ Esther Szekeres, George Szekeres. Despre o problemă a lui Schütte și Erdős // The Mathematical Gazette. - 1965. - T. 49 . - S. 290-293 .
↑ Ronald Graham, Joel Spencer. O soluție constructivă la o problemă de turneu // Canadian Mathematical Bulletin. Buletinul Canadien de Mathematiques. - 1971. - T. 14 . - S. 45-48 .
↑ Frank Harary, Leo Moser. Teoria turneelor round robin // American Mathematical Monthly. - 1966. - T. 73 , nr. 3 . - S. 231-246 . - doi : 10.2307/2315334 . — .
↑ Lajos Takacs. O excursie Bernoulli și diversele sale aplicații // Progrese în probabilitatea aplicată. - 1991. - T. 23 , nr. 3 . - S. 557-585 . - doi : 10.2307/1427622 . — .
↑ T.X. Yao. Pe Reid Conjectura seturi de scor pentru turnee // Chinese Sci. Taur. - 1989. - T. 34 . - S. 804-808 .