Turneu | |
Un turneu cu 4 summit-uri. Acest turneu este 1-paradoxal. Secvența sa de scor este (1, 1, 2, 2). | |
Număr de vârfuri | |
---|---|
Numărul de margini | |
În matematică , în cadrul teoriei graficelor , un turneu este un grafic direcționat obținut prin orientarea fiecărei muchii a unui grafic complet nedirecționat. Îl putem vedea, de asemenea, ca o orientare (în) a unui grafic complet sau ca un grafic direcționat în care fiecare pereche de vârfuri este conectată printr-o margine direcționată și doar una.
Multe proprietăți importante ale turneelor au fost explorate de HG Landau pentru a modela relațiile de dominanță în grupuri de pui. Aplicațiile actuale ale turneelor se referă la teoria sistemelor electorale , precum și la teoria alegerii în societate , printre altele.
Numele de turneu provine din interpretarea unor astfel de grafice ca rezultat al unui turneu complet , în care fiecare participant se întâlnește unul cu celălalt participant o singură dată și în care nu există nicio egalitate. În grafic, vârfurile corespund participanților și marginile corespund rezultatelor jocurilor jucate, marginea mergând de la câștigător la învins. Dacă participantul îl bate pe participant , spunem că domină , notat .
Fiecare turneu pe un număr finit de vârfuri conține o cale Hamiltoniană , adică o cale direcționată care trece prin vârfuri o singură dată. Acest rezultat se datorează lui László Rédei (en) în 1934.
DemonstrațieSă continuăm prin inducție asupra numărului de vârfuri .
Să presupunem că acest lucru este adevărat pentru . Sau un turneu summit. Alegeți un vârf de . Prin ipoteză de inducție, are cel puțin o cale orientată . Fie indexul maxim astfel încât toți ( ) să verifice dacă există o margine orientată a en . În figura de exemplu , deoarece există margini ale și ale din , dar nu ale din .
Rețineți că calea este o cale direcționată care trece prin toate vârfurile graficului. Prin urmare, proprietatea este valabilă și pentru . De altfel, este adevărat pentru un turneu cu două vârfuri, prin recurență, este adevărat pentru orice, de la două.
Această dovadă este constructivă : oferă un algoritm care permite găsirea unei căi hamiltoniene. Sunt cunoscuți algoritmi mai eficienți, care presupun doar că examinează un număr de margini de ordinul lui .
Acest lucru are drept consecință faptul că un puternic conectat turneu , adică astfel încât există o cale între orice pereche de noduri, are un circuit hamiltonian, adică un ciclu închis și orientat care trece prin toate summit - urile o dată și numai o dată (rezultat din cauza Paul Camion în 1959).
Un rezultat mai puternic este faptul că orice turneu puternic conectate sus-pancyclique (în) : pentru orice nod și pentru toți în cazul în care este numărul de noduri, există un circuit lung prin .
Un turneu este uneori definit și ca o relație binară între și . Prin definiție, în cazul în care predomină , atunci nu nu domina . Putem nota această definiție în două moduri:
Spunem apoi că relația este asimetrică . Cu această definiție, putem verifica cu ușurință dacă această relație binară este ireflexivă :
Să rezonăm prin absurd .
Să luăm doi participanți și astfel încât și .
Prin ipoteză, prin urmare, acest lucru implică .
Acum, prin definiție .
Prin urmare, acest rezultat este absurd, iar relația binară a unui turneu este, prin urmare, ireflexivă.
Putem observa că un turneu:
În relațiile binare turneu nu sunt matrici de turneu , avem:
În turneele din viața reală, este de așteptat ca, dacă o persoană domină o persoană și, la rândul său, domină o a treia persoană , atunci va domina . Aceasta corespunde tranzitivității relației de dominație binară .
Declarat oficial, aceasta oferă următoarea definiție:
Numim tranzitiv un turneu în care:
Având în vedere un turneu T cu n vârfuri, următoarele afirmații sunt echivalente:
Un participant la un turneu care câștigă toate jocurile este în mod firesc câștigătorul turneului. Cu toate acestea, după cum arată figura din partea de sus a acestui articol, este posibil ca un astfel de câștigător să nu existe. Un turneu în care fiecare participant pierde cel puțin un joc se numește turneu 1-paradoxal .
Mai general, un turneu se numește k-paradoxal dacă pentru fiecare subset cu elemente , există un vârf în ca pentru toate vârfurile lui .
Într-un turneu de zi cu zi, dacă nu există câștigător net (cineva care îi bate pe toți ceilalți), putem încerca să decidem între candidați calculând scorul lor , adică - să spunem numărul de jocuri câștigate.
Secvența de scoruri pentru un turneu este ordinea în ordinea gradelor de ieșire ale vârfurile unui turneu ascendent.
Setul de turneu scoruri este setul de grade în afara vârfurilor de turneu.
Teorema lui Landau (1953) afirmă că o succesiune de numere întregi este o succesiune de scoruri dacă și numai dacă:
De exemplu, este o secvență de scoruri, deoarece:
De fapt, acest lucru corespunde continuării scorurilor turneului din partea de sus a articolului.
În ceea ce privește seturile de scoruri, TX Yao a dovedit că orice set neferic de numere întregi pozitive sau zero este scorul setat pentru un anumit turneu.
Este firesc să înregistrezi rezultatele unui turneu într-un tabel care arată rezultatul fiecărui joc.
Numim matricea turneului o matrice pătrată ale cărei elemente valorează:
O matrice de turneu este egală cu opusul transpunerii sale (este antisimetrică ).
(ro) Eric W. Weisstein , „ Turneu ” , pe MathWorld
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">