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 , 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 îl învinge pe jucătorul , atunci se spune că domină . 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 de noduri conține un drum hamiltonian, adică un drum orientat prin toate cele noduri ( 1934). Se demonstează ușor prin inducție pe : presupunând că afirmația este valabilă pentru , și considerând orice turneu pe noduri. Se alege un nod din și se consideră un drum orientat din . Fie maxim astfel încât pentru orice există o muchie orientată de la la .
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 muchii..
Aceasta implică faptul că un graf turneu 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 : pentru fiecare nod v, și orice k între 3 și numărul de noduri există un ciclu de lungime k ce conține v., Theorem 1. Mai mult, dacă turneul este 4‑conex, orice pereche de noduri poate fi conectată printr-un drum hamiltonian (Thomassen 1980).
Tranzitivitate miniatura|240x240px|Un graf turneu tranzitiv cu 8 noduri. Un graf turneu în care și 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 .
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 . T nu conține un ciclu de lungime 3. Mulțimea gradelor exterioare a lui este . 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 noduri.. Demonstrația este simplă: se alege orice nod ca parte din acest subgraf, și se formează restul subgrafului recursiv fie pe mulțimea nodurilor care au muchii de la , fie pe mulțimea nodurilor care au muchii care duc la , oricare este mai mare. De exemplu, fiecare graf turneu de șapte noduri conține trei subgrafuri turneu tranzitive; de șapte noduri arată că aceasta este maximul ce poate fi garantat . Cu toate acestea, au arătat că această limită nu este strictă pentru unele valori mai mari ale lui .
au demonstrat că există grafuri turneu de n noduri fără subgrafuri turneu tranzitive de dimensiune 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
și când este mai mare decât acest număr este prea mic pentru a permite apariția unui graf turneu tranzitiv în oricare dintre cele grafuri turneu diferite pe aceeași mulțime de 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 elemente a lui există un nod în astfel încât pentru orice . Prin intermediul , Pál Erdős a arătat că pentru orice valoare fixă a lui , dacă , atunci aproape orice graf turneu peste este -paradoxal. Pe de altă parte, se poate ușor demonstra că orice graf turneu -paradoxal trebuie să aibă cel puțin jucători, rezultat care a fost îmbunătățit la de către și (1965). Există o construcție explicită de grafuri turneu -paradoxale cu jucători elaborată de Graham și Spencer (1971) și anume .
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., Corolarul 5b.
Ș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 este un șir de scor dacă și numai dacă:
Fie numărul de șiruri de scor diferite de dimensiune . Șirul î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:
unde Takács a arătat mai târziu, folosind unele ipoteze rezonabile, dar nedemonstrate, că
unde
Împreună, acestea demonstrează că:
Aici 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.Brandt, Felix and Brill, Markus and Harrenstein, Paul, "Tournament Solutions". Fie mulțimea finită de alternative, și fie o listă de relații de ordine totală peste . Fiecare ordonare se interpretează ca clasificarea preferinței unui votant . Relația de majoritate (strictă) a lui peste se definește atunci astfel încât dacă și numai dacă o majoritate a votanților preferă pe lui , adică . Dacă numărul de votanți este impar, atunci relația de majoritate formează o relație de dominanță a unui graf turneu peste mulțimea .
Conform unei leme a lui Biesenthal, orice graf turneu de noduri poate fi obținut ca relație de majoritate a cel mult votanți. Rezultatele lui Stearns și Erdős & Moser de mai târziu au stabilit că este nevoie de alegători pentru a induce toate grafurile turneu de noduri.
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.Austen-Smith, D. and J. Banks, Positive Political theory, 1999, The University of Michigan Press.
Note
Bibliografie
.
Turneu