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 noduri. Se alege un nod din T ș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.[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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6c/8-tournament-transitive.svg/240px-8-tournament-transitive.svg.png)
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 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 .
- 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.[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 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 k 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 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 în astfel încât pentru orice . Prin intermediul metodei probabilistice(d), Pál Erdős a arătat că pentru orice valoare fixă a lui k, dacă , 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 jucători, rezultat care a fost îmbunătățit la de către Esther(d) și George Szekeres(d) (1965).[5] Există o construcție explicită de grafuri turneu k-paradoxale cu 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 este un șir de scor dacă și numai dacă:
Fie numărul de șiruri de scor diferite de dimensiune n. Șirul Ș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:
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.[7] Fie A mulțimea finită de alternative, și fie o listă de relații de ordine totală peste A. Fiecare ordonare se interpretează ca clasificarea preferinței unui votant i. Relația de majoritate (strictă) a lui P peste A se definește atunci astfel încât dacă și numai dacă o majoritate a votanților preferă pe a lui b, adică . 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 votanți.[8] 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 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. (). „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. (). „A Theorem on the Construction of Voting Paradoxes”. Econometrica (în engleză). 21 (4): 608–610. doi:10.2307/1907926. JSTOR 1907926.
- ^ Stearns, Richard (). „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. (), „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 (), „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. (), „On a problem in graph theory” (PDF), The Mathematical Gazette (în engleză), 47: 220–223
- en Erdős, P.; Moser, L. (), „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. (), „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 (), „The theory of round robin tournaments”, American Mathematical Monthly(d) (în engleză), 73 (3): 231–246, doi:10.2307/2315334
- en Landau, H.G. (), „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. (), „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 , accesat în
- en Rédei, László (), „Ein kombinatorischer Satz”, Acta Litteraria Szeged (în germană), 7: 39–43 .
- en Reid, K.B.; Parker, E.T. (), „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. (), „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 (), „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 (), „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. (), „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ă |