Vizualizare sursă pentru „Graf turneu”

Un '''turneu''' este un [[graf orientat]] obținut prin atribuirea unei direcții fiecărei muchii dintr-un [[Graf|graf neorientat]] [[Graf complet|complet]]. Cu alte cuvinte, este o orientare a unui graf complet, sau, echivalent, un graf orientat în care fiecare pereche de [[Nod (teoria grafurilor)|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 {{harvtxt|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 alegerii sociale|teoria socială a alegerii]]. 

Numele de ''turneu'' provine de la o astfel de interpretare a grafului ca fiind rezultatul unui [[Turneu fiecare cu fiecare|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 {{math|a}} îl învinge pe jucătorul {{math|b}}, atunci se spune că {{math|a}} ''domină'' {{math|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 [[Mulțime finită|finit]] {{math|n}} de noduri conține un [[drum hamiltonian]], adică un drum orientat prin toate cele {{math|n}} noduri ({{Ill-wd|Q220478|3=Rédei}} 1934). Se demonstează ușor prin [[Inducție matematică|inducție]] pe {{math|n}}: presupunând că afirmația este valabilă pentru {{math|n}}, și considerând orice turneu {{math|T}} pe <math>n+1</math> noduri. Se alege un nod <math>v_0</math> din {{math|T}} și se consideră un drum orientat <math>v_1,v_2,\ldots,v_n</math> din <math>T\setminus \{v_0\}</math>. Fie <math>i \in \{0,\ldots,n\}</math> maxim astfel încât pentru orice <math>j \leq i</math> există o muchie orientată de la <math>v_j</math> la <math>v_0</math>.
:: <math>v_1,\ldots,v_i,v_0,v_{i+1},\ldots,v_n</math>
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 <math>\ O(n \log n)</math> muchii.<ref>{{harvtxt|Bar-Noy|Naor|1990}}.</ref>

Aceasta implică faptul că un graf turneu {{Ill-wd|Q2003238|3=tare conex}} are un [[Drum hamiltonian|ciclu hamiltonian]] (Camion 1959). O afirmație mult mai puternică ce poate fi făcută este că orice graf turneu tare conex este {{Ill-wd|Q7130424|3=panciclic în raport cu nodurile}}: pentru fiecare nod ''v'', și orice ''k'' între 3 și numărul de noduri există un ciclu de lungime ''k'' ce conține ''v''.<ref>{{harvtxt|Moon|1966}}, Theorem 1.</ref> Mai mult, dacă turneul este 4‑conex, orice pereche de noduri poate fi conectată printr-un drum hamiltonian (Thomassen 1980).

== Tranzitivitate ==
[[Fișier:8-tournament-transitive.svg|miniatura|240x240px|Un graf turneu tranzitiv cu 8 noduri.]]
Un graf turneu în care <math>((a \rightarrow b)</math> și <math>(b \rightarrow c))</math> <math>\Rightarrow</math> <math>(a \rightarrow c)</math> se numește '''tranzitiv'''. Cu alte cuvinte, într-un graf turneu tranzitiv, nodurile pot fi (strict) [[Relație de ordine totală|total ordonate]] prin relația muchiilor, și relația muchiilor este aceeași ca și {{Ill-wd|Q1361526|3=accesibilitatea}}.

=== 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 {{Ill-wd|Q1195339|3=aciclic}}.
# ''T'' nu conține un ciclu de lungime 3.
# Mulțimea gradelor exterioare a lui {{math|T}} este <math>\{0,1,2,\ldots,n-1\}</math>.
# ''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ă [[Clică|clicile]] în grafurile neorientate. În particular, orice graf turneu cu ''n'' noduri conține un subgraf turneu tranzitiv cu <math>1+\lfloor\log_2 n\rfloor</math> noduri.<ref>{{harvtxt|Erdős|Moser|1964}}.</ref> Demonstrația este simplă: se alege orice nod {{math|v}} ca parte din acest subgraf, și se formează restul subgrafului recursiv fie pe mulțimea nodurilor care au muchii de la {{math|v}}, fie pe mulțimea nodurilor care au muchii care duc la {{math|v}}, oricare este mai mare. De exemplu, fiecare graf turneu de șapte noduri conține trei subgrafuri turneu tranzitive; {{Ill-wd|Q3026495|3=graful turneu Paley}} de șapte noduri arată că aceasta este maximul ce poate fi garantat {{Harvard citation|Erdős|Moser|1964}}.
Cu toate acestea, {{harvtxt|Reid|Parker|1970}} au arătat că această limită nu este strictă pentru unele valori mai mari ale lui {{math|n}}.

{{harvtxt|Erdős|Moser|1964}} au demonstrat că există grafuri turneu de ''n'' noduri fără subgrafuri turneu tranzitive de dimensiune <math>2+2\lfloor\log_2 n\rfloor</math> 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
: <math>\binom{n}{k}k!2^{\binom{n}{2}-\binom{k}{2}},</math>
și când {{math|k}} este mai mare decât <math>2+2\lfloor\log_2 n\rfloor</math> acest număr este prea mic pentru a permite apariția unui graf turneu tranzitiv în oricare dintre cele <math>2^{\binom{n}{2}}</math> grafuri turneu diferite pe aceeași mulțime de {{math|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 {{math|k}} elemente {{math|S}} a lui {{math|V}} există un nod <math>v_0</math> în <math>V\setminus S</math> astfel încât <math>v_0 \rightarrow v</math> pentru orice <math>v \in S</math>. Prin intermediul {{Ill-wd|Q3333679|3=metodei probabilistice}}, [[Paul Erdős|Pál Erdős]] a arătat că pentru orice valoare fixă a lui {{math|k}}, dacă <math>|V| \geq k^22^k\ln(2+o(1))</math>, atunci aproape orice graf turneu peste {{math|V}} este {{math|k}}-paradoxal.<ref>{{harvtxt|Erdős|1963}}</ref> Pe de altă parte, se poate ușor demonstra că orice graf turneu {{math|k}}-paradoxal trebuie să aibă cel puțin <math>2^{k+1}-1</math> jucători, rezultat care a fost îmbunătățit la <math>(k+2)2^{k-1}-1</math> de către {{Ill-wd|Q51109|3=Esther}} și {{Ill-wd|Q177504}} (1965).<ref>{{Citat revistă|nume=Szekeres|nume2=Szekeres|prenume=E.|prenume2=G.|dată=1965|titlu=On a problem of Schütte and Erdős|journal=Math. Gaz.|volum=49|pagini=290–293}}</ref> Există o construcție explicită de grafuri turneu {{math|k}}-paradoxale cu <math>k^24^{k-1}(1+o(1))</math> jucători elaborată de [[Ronald Graham|Graham]] și Spencer (1971) și anume {{Ill-wd|Q3026495|3=graful turneu Paley}}.

=== 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.<ref>{{harvtxt|Harary|Moser|1966}}, Corolarul 5b.</ref>

== Ș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 <math>(s_1, s_2, \cdots, s_n)</math> este un șir de scor [[dacă și numai dacă]]:
# <math>0 \le s_1 \le s_2 \le \cdots \le s_n</math>
# <math>s_1 + s_2 + \cdots + s_i \ge {i \choose 2}, \mbox{pentru }i = 1, 2, \cdots, n - 1</math>
# <math>s_1 + s_2 + \cdots + s_n = {n \choose 2}.</math>
Fie <math>s(n)</math> numărul de șiruri de scor diferite de dimensiune {{math|n}}. Șirul <math>s(n)</math> {{OEIS|id=A000571}} î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:
: <math>s(n) > c_1 4^n n^{-{5 \over 2}},</math>
unde <math>c_1 = 0.049.</math>
Takács a arătat mai târziu, folosind unele ipoteze rezonabile, dar nedemonstrate, că
: <math>s(n) < c_2 4^n n^{-{5 \over 2}},</math>
unde <math>c_2 < 4.858.</math>

Împreună, acestea demonstrează că:
: <math>s(n) \in \Theta (4^n n^{-{5 \over 2}}).</math>
Aici <math>\Theta</math> semnifică o [[Notația Big 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.<ref name=":0">Brandt, Felix and Brill, Markus and Harrenstein, Paul, 
"Tournament Solutions". </ref>
Fie {{math|A}} mulțimea finită de alternative, și fie o listă <math>P = (\succ_1, \dots, \succ_n)</math> de [[Relație de ordine totală|relații de ordine totală]] peste {{math|A}}. Fiecare ordonare <math>\succ_i</math> se interpretează ca clasificarea preferinței unui votant {{math|i}}. Relația de majoritate (strictă) <math>\succ_{\text{maj}}</math> a lui {{math|P}} peste {{math|A}} se definește atunci astfel încât <math>a \succ_{\text{maj}} b</math> dacă și numai dacă o majoritate a votanților preferă pe {{math|a}} lui {{math|b}}, adică <math>|\{ i \in [n] : a \succ_i b \}| > |\{ i \in [n] : b \succ_i a \}|</math>. Dacă numărul {{math|n}} de votanți este impar, atunci relația de majoritate formează o relație de dominanță a unui graf turneu peste mulțimea {{math|A}}.

Conform unei leme a lui Biesenthal, orice graf turneu de {{math|m}} noduri poate fi obținut ca relație de majoritate a cel mult <math>m(m-1)</math> votanți.<ref>{{Citat revistă|nume=McGarvey|prenume=David C.|dată=1953-01-01|titlu=A Theorem on the Construction of Voting Paradoxes|journal=Econometrica|volum=21|număr=4|pagini=608–610|jstor=1907926|doi=10.2307/1907926|language=en}}</ref> Rezultatele lui [[Richard Stearns|Stearns]] și Erdős & Moser de mai târziu au stabilit că este nevoie de <math>\Theta(m/\log m)</math> alegători pentru a induce toate grafurile turneu de {{math|m}} noduri.<ref>{{Citat revistă|nume=Stearns|prenume=Richard|dată=1959-01-01|titlu=The Voting Problem|journal=The American Mathematical Monthly|volum=66|număr=9|pagini=761–763|jstor=2310461|doi=10.2307/2310461|language=en}}</ref>

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.<ref>Austen-Smith, D. and J. Banks, Positive Political theory, 1999, The University of Michigan Press.</ref>

== Note ==
<references />

== Bibliografie ==
* {{en icon}} {{Citation|title=Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments|year=1990|last1=Bar-Noy|last2=Naor|first1=A.|first2=J.|author2-link=Joseph Seffi Naor|journal={{Ill-wd|Q7390256}}|volume=3|issue=1|pages=7–20|doi=10.1137/0403002|language=en}}
* {{en icon}} {{Citation|title=Chemins et circuits hamiltoniens des graphes complets|year=1959|last=Camion|first=Paul|journal=Comptes Rendus de l'Acad&eacute;mie des Sciences de Paris|volume=249|pages=2151&ndash;2152|language=fr}}
* {{en icon}} {{Citation|title=On a problem in graph theory|year=1963|last=Erdős|first=P.|author1-link=Paul Erdős|url=http://www.renyi.hu/~p_erdos/1963-08.pdf|journal=[[The Mathematical Gazette]]|volume=47|pages=220–223|language=en}}
* {{en icon}} {{Citation|title=On the representation of directed graphs as unions of orderings|year=1964|last1=Erdős|last2=Moser|first1=P.|first2=L.|author1-link=Paul Erdős|author2-link=Leo Moser|url=http://www.renyi.hu/~p_erdos/1964-22.pdf|journal=Magyar Tud. Akad. Mat. Kutató Int. Közl.|volume=9|pages=125–132|language=en}}
* {{en icon}} {{Citation|title=A constructive solution to a tournament problem|year=1971|last1=Graham|last2=Spencer|first1=R. L.|first2=J. H.|author1-link=Ronald Graham|author2-link=Joel Spencer|journal={{Ill-wd|Q5030309}}|volume=14|pages=45–48|doi=10.4153/cmb-1971-007-1|language=en}}
* {{en icon}} {{Citation|title=The theory of round robin tournaments|year=1966|last1=Harary|last2=Moser|first1=Frank|first2=Leo|author1-link=Frank Harary|author2-link=Leo Moser|journal={{Ill-wd|Q2707818}}|volume=73|issue=3|pages=231–246|doi=10.2307/2315334|language=en}}
* {{en icon}} {{Citation|title=On dominance relations and the structure of animal societies. III. The condition for a score structure|year=1953|last=Landau|first=H.G.|journal=Bulletin of Mathematical Biophysics|volume=15|issue=2|pages=143–148|doi=10.1007/BF02476378|language=en}}
* {{en icon}} {{Citation|title=On subtournaments of a tournament|year=1966|last=Moon|first=J. W.|url=http://cms.math.ca/cmb/v9/p297|journal={{Ill-wd|Q5030309}}|volume=9|issue=3|pages=297–301|doi=10.4153/CMB-1966-038-7|language=en|access-date=2017-06-22|archive-date=2016-03-03|archive-url=https://web.archive.org/web/20160303211053/http://cms.math.ca/cmb/v9/p297|dead-url=yes}}
* {{en icon}} {{Citation|title=Ein kombinatorischer Satz|year=1934|last=Rédei|first=László|author-link=László Rédei|journal=Acta Litteraria Szeged|volume=7|pages=39&ndash;43|language=de}}.
* {{en icon}} {{Citation|title=Disproof of a conjecture of Erdös and Moser|year=1970|last1=Reid|last2=Parker|first1=K.B.|first2=E.T.|journal={{Ill-wd|Q3186905}}|volume=9|issue=3|pages=225&ndash;238|doi=10.1016/S0021-9800(70)80061-8|language=en}}
* {{en icon}} {{Citation|title=On a problem of Schütte and Erdős|year=1965|last1=Szekeres|last2=Szekeres|first1=E.|first2=G.|author1-link=Esther Szekeres|author2-link=George Szekeres|journal=[[The Mathematical Gazette]]|volume=49|pages=290–293|doi=10.2307/3612854|language=en}}
* {{en icon}} {{Citation|title=A Bernoulli Excursion and Its Various Applications|year=1991|last=Takács|first=Lajos|author-link=Lajos Takács|journal=Advances in Applied Probability|volume=23|issue=3|pages=557–585|publisher=Applied Probability Trust|doi=10.2307/1427622|language=en}}
* {{en icon}} {{Citation|title=Hamiltonian-Connected Tournaments|year=1980|last=Thomassen|first1=Carsten|author-link=Carsten Thomassen|series=Series B|journal={{Ill-wd|Q3186905}}|volume=28|issue=2|pages=142&ndash;163|doi=10.1016/0095-8956(80)90061-1|language=en}}
* {{en icon}} {{Citation|title=On Reid conjecture of score sets for tournaments|year=1989|last=Yao|first=T.X.|journal=Chinese Sci. Bull.|volume=34|pages=804&ndash;808}}
{{PlanetMath attribution|id=3518|title=tournament}}

{{Portal|Matematică}}
{{Clase de grafuri}}

[[Categorie:Grafuri|Turneu]]