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 Format:Harvtxt, 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 Format:Math îl învinge pe jucătorul Format:Math, atunci se spune că Format:Math domină Format:Math. 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 Format:Math de noduri conține un drum hamiltonian, adică un drum orientat prin toate cele Format:Math noduri (Format:Ill-wd 1934). Se demonstează ușor prin inducție pe Format:Math: presupunând că afirmația este valabilă pentru Format:Math, și considerând orice turneu Format:Math pe $n + 1$ noduri. Se alege un nod $v_{0}$ din Format:Math și se consideră un drum orientat $v_{1}, v_{2}, \dots, v_{n}$ din $T ∖ {v_{0}}$ . Fie $i \in {0, \dots, n}$ maxim astfel încât pentru orice $j \leq i$ există o muchie orientată de la $v_{j}$ la $v_{0}$ .

v_{1}, \dots, v_{i}, v_{0}, v_{i + 1}, \dots, 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 Format:Ill-wd 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 Format:Ill-wd: 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 în care $((a \to b)$ și $(b \to c))$ $\Rightarrow$ $(a \to 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 Format:Ill-wd.

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 Format:Ill-wd.
T nu conține un ciclu de lungime 3.
Mulțimea gradelor exterioare a lui Format:Math este ${0, 1, 2, \dots, 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 + ⌊ \log_{2} n ⌋$ noduri.^[3] Demonstrația este simplă: se alege orice nod Format:Math ca parte din acest subgraf, și se formează restul subgrafului recursiv fie pe mulțimea nodurilor care au muchii de la Format:Math, fie pe mulțimea nodurilor care au muchii care duc la Format:Math, oricare este mai mare. De exemplu, fiecare graf turneu de șapte noduri conține trei subgrafuri turneu tranzitive; Format:Ill-wd de șapte noduri arată că aceasta este maximul ce poate fi garantat Format:Harvard citation. Cu toate acestea, Format:Harvtxt au arătat că această limită nu este strictă pentru unele valori mai mari ale lui Format:Math.

Format:Harvtxt au demonstrat că există grafuri turneu de n noduri fără subgrafuri turneu tranzitive de dimensiune $2 + 2 ⌊ \log_{2} n ⌋$ 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 Format:Math este mai mare decât $2 + 2 ⌊ \log_{2} n ⌋$ 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 Format:Math 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 Format:Math elemente Format:Math a lui Format:Math există un nod $v_{0}$ în $V ∖ S$ astfel încât $v_{0} \to v$ pentru orice $v \in S$ . Prin intermediul Format:Ill-wd, Pál Erdős a arătat că pentru orice valoare fixă a lui Format:Math, dacă $| V | \geq k^{2} 2^{k} \ln (2 + o (1))$ , atunci aproape orice graf turneu peste Format:Math este Format:Math-paradoxal.^[4] Pe de altă parte, se poate ușor demonstra că orice graf turneu Format:Math-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 Format:Ill-wd și Format:Ill-wd (1965).^[5] Există o construcție explicită de grafuri turneu Format:Math-paradoxale cu $k^{2} 4^{k - 1} (1 + o (1))$ jucători elaborată de Graham și Spencer (1971) și anume Format:Ill-wd.

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}, \dots, s_{n})$ este un șir de scor dacă și numai dacă:

$0 \leq s_{1} \leq s_{2} \leq \dots \leq s_{n}$
$s_{1} + s_{2} + \dots + s_{i} \geq (\binom{i}{2}), pentru i = 1, 2, \dots, n - 1$
$s_{1} + s_{2} + \dots + s_{n} = (\binom{n}{2}) .$

Fie $s (n)$ numărul de șiruri de scor diferite de dimensiune Format:Math. Șirul $s (n)$ Format: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^{- \frac{5}{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^{- \frac{5}{2}},

unde $c_{2} < 4.858 .$

Împreună, acestea demonstrează că:

s (n) \in Θ (4^{n} n^{- \frac{5}{2}}) .

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 Format:Math mulțimea finită de alternative, și fie o listă $P = (≻_{1}, \dots, ≻_{n})$ de relații de ordine totală peste Format:Math. Fiecare ordonare $≻_{i}$ se interpretează ca clasificarea preferinței unui votant Format:Math. Relația de majoritate (strictă) $≻_{maj}$ a lui Format:Math peste Format:Math se definește atunci astfel încât $a ≻_{maj} b$ dacă și numai dacă o majoritate a votanților preferă pe Format:Math lui Format:Math, adică $| {i \in [n] : a ≻_{i} b} | > | {i \in [n] : b ≻_{i} a} |$ . Dacă numărul Format:Math de votanți este impar, atunci relația de majoritate formează o relație de dominanță a unui graf turneu peste mulțimea Format:Math.

Conform unei leme a lui Biesenthal, orice graf turneu de Format:Math 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 $Θ (m / \log m)$ alegători pentru a induce toate grafurile turneu de Format:Math 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

↑ Format:Harvtxt.
↑ Format:Harvtxt, Theorem 1.
↑ Format:Harvtxt.
↑ Format:Harvtxt
↑ Format:Citat revistă
↑ Format:Harvtxt, Corolarul 5b.
↑ Brandt, Felix and Brill, Markus and Harrenstein, Paul, "Tournament Solutions".
↑ Format:Citat revistă
↑ Format:Citat revistă
↑ Austen-Smith, D. and J. Banks, Positive Political theory, 1999, The University of Michigan Press.

Bibliografie

Format:PlanetMath attribution

Format:Portal Format:Clase de grafuri

[1] Format:Harvtxt.

[2] Format:Harvtxt, Theorem 1.

[3] Format:Harvtxt.

[4] Format:Harvtxt

[5] Format:Citat revistă

[6] Format:Harvtxt, Corolarul 5b.

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

[8] Format:Citat revistă

[9] Format:Citat revistă

[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]

Graf turneu

Cuprins

Drumuri și cicluri

Tranzitivitate

Condiții echivalente

Teoria lui Ramsey

Grafuri turneu paradoxale

Condensarea

Șiruri de scor și mulțimi de scor

Relații de majoritate

Note

Bibliografie

Meniu de navigare

Graf turneu

Drumuri și cicluri

Tranzitivitate

Condiții echivalente

Teoria lui Ramsey

Grafuri turneu paradoxale

Condensarea

Șiruri de scor și mulțimi de scor

Relații de majoritate

Note

Bibliografie

Meniu de navigare

Căutare