Graf turneu

Un turneu este un graf orientat obținut prin atribuirea unei direcții fiecărei muchii dintr-un graf neorientat complet. Cu alte cuvinte, este o orientare a unui graf complet, sau, echivalent, un graf orientat în care fiecare pereche de noduri distincte este conectată printr-o singură muchie orientată.

Multe dintre cele mai importante proprietăți ale grafurilor turneu au fost investigate în premieră de către Landau (1953), pentru a modela relațiile de dominanță în grupurile de găini. Printre aplicațiile actuale ale grafurilor turneu se numără, printre altele, studiul teoriei voturilor și teoria socială a alegerii.

Numele de turneu provine de la o astfel de interpretare a grafului ca fiind rezultatul unui turneu în care fiecare jucător joacă cu toți ceilalți exact o dată, și în care nu au loc remize. În graful orientat turneu, nodurile corespund jucătorilor. Muchia dintre fiecare pereche de jucători este orientată de la câștigător la învins. Dacă jucătorul $a$ îl învinge pe jucătorul $b$ , atunci se spune că $a$ domină $b$ . Dacă fiecare jucător învinge același număr de alți jucători (grad interior = grad exterior), se spune că turneul este regulat.

Drumuri și cicluri

Orice graf turneu cu un număr finit $n$ de noduri conține un drum hamiltonian, adică un drum orientat prin toate cele $n$ noduri (Rédei^⁠(d) 1934). Se demonstează ușor prin inducție pe $n$ : presupunând că afirmația este valabilă pentru $n$ , și considerând orice turneu $T$ pe $n+1$ noduri. Se alege un nod $v_{0}$ din $T$ și se consideră un drum orientat $v_{1},v_{2},\ldots ,v_{n}$ din $T\setminus \{v_{0}\}$ . Fie $i\in \{0,\ldots ,n\}$ maxim astfel încât pentru orice $j\leq i$ există o muchie orientată de la $v_{j}$ la $v_{0}$ .

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

este un drum orientat ca cel cerut. Acest argument oferă și un algoritm pentru găsirea drumului hamiltonian. Se cunosc și algoritmi mai eficienți, care necesită examinarea a numai $\ O(n\log n)$ muchii.^[1]

Aceasta implică faptul că un graf turneu tare conex^⁠(d) are un ciclu hamiltonian (Camion 1959). O afirmație mult mai puternică ce poate fi făcută este că orice graf turneu tare conex este panciclic în raport cu nodurile^⁠(d): pentru fiecare nod v, și orice k între 3 și numărul de noduri există un ciclu de lungime k ce conține v.^[2] Mai mult, dacă turneul este 4‑conex, orice pereche de noduri poate fi conectată printr-un drum hamiltonian (Thomassen 1980).

Tranzitivitate

Un graf turneu tranzitiv cu 8 noduri.

Un graf turneu în care $((a\rightarrow b)$ și $(b\rightarrow c))$ $\Rightarrow$ $(a\rightarrow c)$ se numește tranzitiv. Cu alte cuvinte, într-un graf turneu tranzitiv, nodurile pot fi (strict) total ordonate prin relația muchiilor, și relația muchiilor este aceeași ca și accesibilitatea^⁠(d).

Condiții echivalente

Următoarele afirmații sunt echivalente pentru un graf turneu T pe n noduri:

T este tranzitiv.
T este o ordonare totală strictă.
T este aciclic^⁠(d).
T nu conține un ciclu de lungime 3.
Mulțimea gradelor exterioare a lui $T$ este $\{0,1,2,\ldots ,n-1\}$ .
T are exact un drum hamiltonian.

Teoria lui Ramsey

Grafurile turneu tranzitive joacă un rol în teoria lui Ramsey, similar cu cel pe care îl joacă clicile în grafurile neorientate. În particular, orice graf turneu cu n noduri conține un subgraf turneu tranzitiv cu $1+\lfloor \log _{2}n\rfloor$ noduri.^[3] Demonstrația este simplă: se alege orice nod $v$ ca parte din acest subgraf, și se formează restul subgrafului recursiv fie pe mulțimea nodurilor care au muchii de la $v$ , fie pe mulțimea nodurilor care au muchii care duc la $v$ , oricare este mai mare. De exemplu, fiecare graf turneu de șapte noduri conține trei subgrafuri turneu tranzitive; graful turneu Paley^⁠(d) de șapte noduri arată că aceasta este maximul ce poate fi garantat (Erdős & Moser 1964). Cu toate acestea, Reid & Parker (1970) au arătat că această limită nu este strictă pentru unele valori mai mari ale lui $n$ .

Erdős & Moser (1964) au demonstrat că există grafuri turneu de n noduri fără subgrafuri turneu tranzitive de dimensiune $2+2\lfloor \log _{2}n\rfloor$ Demonstrația lor foloseste un argument de numărare: numărul de moduri în care poate să apară un graf turneu tranzitiv cu k elemente ca subgraf turneu al unui graf turneu mai mare pe n noduri este

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

și când $k$ este mai mare decât $2+2\lfloor \log _{2}n\rfloor$ acest număr este prea mic pentru a permite apariția unui graf turneu tranzitiv în oricare dintre cele $2^{\binom {n}{2}}$ grafuri turneu diferite pe aceeași mulțime de $n$ noduri etichetate.

Grafuri turneu paradoxale

Un jucător care câștigă toate jocurile va fi în mod natural câștigător al turneului. Cu toate acestea, așa cum arată existența unor turnee netranzitive, ar putea 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 mult, în general, un turneu T=(V,E) se numește k-paradoxal dacă pentru fiecare submulțime de $k$ elemente $S$ a lui $V$ există un nod $v_{0}$ în $V\setminus S$ astfel încât $v_{0}\rightarrow v$ pentru orice $v\in S$ . Prin intermediul metodei probabilistice^⁠(d), Pál Erdős a arătat că pentru orice valoare fixă a lui $k$ , dacă $|V|\geq k^{2}2^{k}\ln(2+o(1))$ , atunci aproape orice graf turneu peste $V$ este $k$ -paradoxal.^[4] Pe de altă parte, se poate ușor demonstra că orice graf turneu $k$ -paradoxal trebuie să aibă cel puțin $2^{k+1}-1$ jucători, rezultat care a fost îmbunătățit la $(k+2)2^{k-1}-1$ de către Esther^⁠(d) și George Szekeres^⁠(d) (1965).^[5] Există o construcție explicită de grafuri turneu $k$ -paradoxale cu $k^{2}4^{k-1}(1+o(1))$ jucători elaborată de Graham și Spencer (1971) și anume graful turneu Paley^⁠(d).

Condensarea

Condensarea oricărui graf turneu este în sine un graf turneu tranzitiv. Astfel, chiar și pentru grafuri turneu care nu sunt tranzitive, componentele tare conexe ale turneului pot fi total ordonate.^[6]

Șiruri de scor și mulțimi de scor

Șirul de scorul al unui graf turneu este șirul nedescrescător al gradelor exterioare ale nodurilor grafului. Mulțimea de scor a unui graf turneu este o mulțime de numere întregi care sunt grade exterioare ale nodurilor din acel graf turneu.

Teorema lui Landau (1953) Un șir nedescrescător de numere întregi $(s_{1},s_{2},\cdots ,s_{n})$ este un șir de scor dacă și numai dacă:

$0\leq s_{1}\leq s_{2}\leq \cdots \leq s_{n}$
$s_{1}+s_{2}+\cdots +s_{i}\geq {i \choose 2},{\mbox{pentru }}i=1,2,\cdots ,n-1$
$s_{1}+s_{2}+\cdots +s_{n}={n \choose 2}.$

Fie $s(n)$ numărul de șiruri de scor diferite de dimensiune $n$ . Șirul $s(n)$ Șirul A000571 la Enciclopedia electronică a șirurilor de numere întregi (OEIS) începe astfel:

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

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

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

unde $c_{1}=0.049.$ Takács a arătat mai târziu, folosind unele ipoteze rezonabile, dar nedemonstrate, că

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

unde $c_{2}<4.858.$

Împreună, acestea demonstrează că:

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

Aici $\Theta$ semnifică o limită asimptotică strictă.

Yao a arătat că orice mulțime nevidă de numere întregi nenegative este mulțimea de scor a unui graf turneu.

Relații de majoritate

În teoria socială a alegerii, grafurile turneu apar natural ca relații de majoritate a profilelor de preferințe.^[7] Fie $A$ mulțimea finită de alternative, și fie o listă $P=(\succ _{1},\dots ,\succ _{n})$ de relații de ordine totală peste $A$ . Fiecare ordonare $\succ _{i}$ se interpretează ca clasificarea preferinței unui votant $i$ . Relația de majoritate (strictă) $\succ _{\text{maj}}$ a lui $P$ peste $A$ se definește atunci astfel încât $a\succ _{\text{maj}}b$ dacă și numai dacă o majoritate a votanților preferă pe $a$ lui $b$ , adică $|\{i\in [n]:a\succ _{i}b\}|>|\{i\in [n]:b\succ _{i}a\}|$ . Dacă numărul $n$ de votanți este impar, atunci relația de majoritate formează o relație de dominanță a unui graf turneu peste mulțimea $A$ .

Conform unei leme a lui Biesenthal, orice graf turneu de $m$ noduri poate fi obținut ca relație de majoritate a cel mult $m(m-1)$ votanți.^[8] Rezultatele lui Stearns și Erdős & Moser de mai târziu au stabilit că este nevoie de $\Theta (m/\log m)$ alegători pentru a induce toate grafurile turneu de $m$ noduri.^[9]

Laslier (1997) studiază în ce sens poate fi numită o mulțime de noduri mulțimea „câștigătorilor” unui turneu. Aceasta s-a dovedit utilă în științele politice, în modelele formale ale economiei politice, pentru studiul posibilelor rezultate ale unui proces democratic.^[10]

Note

^ Bar-Noy & Naor (1990).
^ Moon (1966), Theorem 1.
^ Erdős & Moser (1964).
^ Erdős (1963)
^ Szekeres, E.; Szekeres, G. (1965). „On a problem of Schütte and Erdős”. Math. Gaz. 49: 290–293.
^ Harary & Moser (1966), Corolarul 5b.
^ Brandt, Felix and Brill, Markus and Harrenstein, Paul, "Tournament Solutions".
^ McGarvey, David C. (1 ianuarie 1953). „A Theorem on the Construction of Voting Paradoxes”. Econometrica (în engleză). 21 (4): 608–610. doi:10.2307/1907926. JSTOR 1907926.
^ Stearns, Richard (1 ianuarie 1959). „The Voting Problem”. The American Mathematical Monthly (în engleză). 66 (9): 761–763. doi:10.2307/2310461. JSTOR 2310461.
^ Austen-Smith, D. and J. Banks, Positive Political theory, 1999, The University of Michigan Press.

Bibliografie

en Bar-Noy, A.; Naor, J. (1990), „Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments”, SIAM Journal on Discrete Mathematics^⁠(d) (în engleză), 3 (1): 7–20, doi:10.1137/0403002
en Camion, Paul (1959), „Chemins et circuits hamiltoniens des graphes complets”, Comptes Rendus de l'Académie des Sciences de Paris (în franceză), 249: 2151–2152
en Erdős, P. (1963), „On a problem in graph theory” (PDF), The Mathematical Gazette (în engleză), 47: 220–223
en Erdős, P.; Moser, L. (1964), „On the representation of directed graphs as unions of orderings” (PDF), Magyar Tud. Akad. Mat. Kutató Int. Közl. (în engleză), 9: 125–132
en Graham, R. L.; Spencer, J. H. (1971), „A constructive solution to a tournament problem”, Canadian Mathematical Bulletin^⁠(d) (în engleză), 14: 45–48, doi:10.4153/cmb-1971-007-1
en Harary, Frank; Moser, Leo (1966), „The theory of round robin tournaments”, American Mathematical Monthly^⁠(d) (în engleză), 73 (3): 231–246, doi:10.2307/2315334
en Landau, H.G. (1953), „On dominance relations and the structure of animal societies. III. The condition for a score structure”, Bulletin of Mathematical Biophysics (în engleză), 15 (2): 143–148, doi:10.1007/BF02476378
en Moon, J. W. (1966), „On subtournaments of a tournament”, Canadian Mathematical Bulletin^⁠(d) (în engleză), 9 (3): 297–301, doi:10.4153/CMB-1966-038-7, arhivat din original la 3 martie 2016, accesat în 22 iunie 2017
en Rédei, László (1934), „Ein kombinatorischer Satz”, Acta Litteraria Szeged (în germană), 7: 39–43 .
en Reid, K.B.; Parker, E.T. (1970), „Disproof of a conjecture of Erdös and Moser”, Journal of Combinatorial Theory^⁠(d) (în engleză), 9 (3): 225–238, doi:10.1016/S0021-9800(70)80061-8
en Szekeres, E.; Szekeres, G. (1965), „On a problem of Schütte and Erdős”, The Mathematical Gazette (în engleză), 49: 290–293, doi:10.2307/3612854
en Takács, Lajos (1991), „A Bernoulli Excursion and Its Various Applications”, Advances in Applied Probability (în engleză), Applied Probability Trust, 23 (3): 557–585, doi:10.2307/1427622
en Thomassen, Carsten (1980), „Hamiltonian-Connected Tournaments”, Journal of Combinatorial Theory^⁠(d), Series B (în engleză), 28 (2): 142–163, doi:10.1016/0095-8956(80)90061-1
en Yao, T.X. (1989), „On Reid conjecture of score sets for tournaments”, Chinese Sci. Bull., 34: 804–808

Acest articol cuprinde material de la tournament de la PlanetMath, licențiat cu Creative Commons Atribuire/Distribuire în condiții identice.

Portal Matematică

[1] Bar-Noy & Naor (1990).

[2] Moon (1966), Theorem 1.

[3] Erdős & Moser (1964).

[4] Erdős (1963)

[5] Szekeres, E.; Szekeres, G. (1965). „On a problem of Schütte and Erdős”. Math. Gaz. 49: 290–293.

[6] Harary & Moser (1966), Corolarul 5b.

[:0-7] Brandt, Felix and Brill, Markus and Harrenstein, Paul, "Tournament Solutions".

[8] McGarvey, David C. (1 ianuarie 1953). „A Theorem on the Construction of Voting Paradoxes”. Econometrica (în engleză). 21 (4): 608–610. doi:10.2307/1907926. JSTOR 1907926.

[9] Stearns, Richard (1 ianuarie 1959). „The Voting Problem”. The American Mathematical Monthly (în engleză). 66 (9): 761–763. doi:10.2307/2310461. JSTOR 2310461.

[10] Austen-Smith, D. and J. Banks, Positive Political theory, 1999, The University of Michigan Press.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]