Hispanopedia Wiki
Articulo de referencia

Torneo (teoría de grafos)

n "},"edges":{"wt":" \\binom{n}{2} "}},"i":0}}]}"> En teoría de grafos , un torneo es un grafo dirigido con exactamente una arista entre cada par de vértices , en una de las dos...

Hispanopedia WikiContenido en espanolLectura gratuita

En teoría de grafos , un torneo es un grafo dirigido con exactamente una arista entre cada par de vértices , en una de las dos direcciones posibles. De forma equivalente, un torneo es una orientación de un grafo completo no dirigido . (Sin embargo, como grafos dirigidos, los torneos no son completos: los grafos dirigidos completos tienen dos aristas, en ambas direcciones, entre cada par de vértices. [ 1 ] ) De forma equivalente, un torneo es una relación asimétrica completa . [ 2 ] [ 3 ]

El nombre " torneo" proviene de interpretar el gráfico como el resultado de un torneo de todos contra todos , un juego en el que cada jugador se enfrenta a todos los demás exactamente una vez. En un torneo, los vértices representan a los jugadores y las aristas entre ellos apuntan del ganador al perdedor.

Muchas de las propiedades importantes de los torneos fueron investigadas por HG Landau en 1953 para modelar las relaciones de dominancia en bandadas de pollos. [ 4 ] Los torneos también se estudian ampliamente en la teoría de la votación , donde pueden representar información parcial sobre las preferencias de los votantes entre múltiples candidatos, y son fundamentales para la definición de los métodos de Condorcet .

Si cada jugador vence al mismo número de otros jugadores ( grado de entrada − grado de salida = 0), el torneo se denomina regular . El número de torneos regulares sin etiquetar con 2n+1 vértices es:

1, 1, 1, 3, 15, 1223, 1495297, 18400989629, 2406183070160597,... (secuencia A096368 en el OEIS )

Caminos y ciclos

a se inserta entre v 2 y v 3 .

Cualquier torneo en un número finitonorte{\displaystyle n}de vértices contiene un camino hamiltoniano , es decir, un camino dirigido en todosnorte{\displaystyle n}vértices ( Rédei 1934).

Esto se demuestra mediante inducción ennorte{\displaystyle n}: supongamos que la afirmación se cumple paranorte{\displaystyle n}y considerar cualquier torneoT{\displaystyle T}ennorte+1{\displaystyle n+1}vértices. Elige un vértice.v0{\displaystyle v_{0}}deT{\displaystyle T}y considere un camino dirigidov1,v2,…,vnorte{\displaystyle v_{1},v_{2},\ldots,v_{n}}enT∖{v0}{\displaystyle T\smallsetminus \{v_{0}\}}Hay algunos.i∈{0,…,norte}{\displaystyle i\in \{0,\ldots ,n\}}de tal manera que(i=0∨vi→v0)∧(v0→vi+1∨i=norte){\displaystyle (i=0\vee v_{i}\rightarrow v_{0})\wedge (v_{0}\rightarrow v_{i+1}\vee i=n)}. (Una posibilidad es dejari∈{0,…,norte}{\displaystyle i\in \{0,\ldots ,n\}}sea ​​máximo tal que para cadaj≤i,vj→v0{\displaystyle j\leq i,v_{j}\rightarrow v_{0}}. Alternativamente, dejei{\displaystyle i}ser mínimo tal que∀j>i,v0→vj{\displaystyle \forall j>i,v_{0}\rightarrow v_{j}}.) v1,…,vi,v0,vi+1,…,vnorte{\displaystyle v_{1},\ldots,v_{i},v_{0},v_{i+1},\ldots,v_{n}} es un camino dirigido como se desea. Este argumento también proporciona un algoritmo para encontrar el camino hamiltoniano. Algoritmos más eficientes, que requieren examinar soloO(norteregistro⁡norte){\displaystyle O(n\log n)}de las aristas, son conocidas. Los caminos hamiltonianos están en correspondencia biunívoca con los conjuntos mínimos de arcos de retroalimentación del torneo. [ 5 ] El teorema de Rédei es el caso especial para grafos completos del teorema de Gallai-Hasse-Roy-Vitaver , que relaciona las longitudes de los caminos en orientaciones de grafos con el número cromático de estos grafos. [ 6 ]

Otro resultado básico sobre torneos es que todo torneo fuertemente conectado tiene un ciclo hamiltoniano . [ 7 ] Más fuertemente, todo torneo fuertemente conectado es pancíclico de vértices : para cada vérticev{\displaystyle v}y cada unok{\displaystyle k}en el rango de tres al número de vértices en el torneo, hay un ciclo de longitudk{\displaystyle k}que contienev{\displaystyle v}. [ 8 ] Un torneoT{\displaystyle T}esk{\displaystyle k}-fuertemente conectados si para cada conjuntoU{\displaystyle U}dek−1{\displaystyle k-1}vértices deT{\displaystyle T},T−U{\displaystyle TU}está fuertemente conectado. Si el torneo es 4-fuertemente conectado, entonces cada par de vértices puede conectarse con un camino hamiltoniano. [ 9 ] Para cada conjuntoB{\displaystyle B}de como máximok−1{\displaystyle k-1}arcos de unk{\displaystyle k}-torneo con fuerte conexiónT{\displaystyle T}, tenemos esoT−B{\displaystyle TB}tiene un ciclo hamiltoniano. [ 10 ] Este resultado fue extendido por Bang-Jensen, Gutin y Yeo (1997) . [ 11 ]

Transitividad

Un torneo transitivo en 8 vértices

Un torneo en el que((a→b){\displaystyle ((a\rightarrow b)}y(b→do)){\displaystyle (b\rightarrow c))}⇒{\displaystyle \Rightarrow }(a→do){\displaystyle (a\rightarrow c)}se denomina transitivo . En otras palabras, en un torneo transitivo, los vértices pueden estar (estrictamente) totalmente ordenados por la relación de aristas, y la relación de aristas es la misma que la alcanzabilidad .

Condiciones equivalentes

Las siguientes afirmaciones son equivalentes para un torneo.T{\displaystyle T}ennorte{\displaystyle n}vértices:

  1. T{\displaystyle T}es transitivo.
  2. T{\displaystyle T}es un pedido total estricto.
  3. T{\displaystyle T}es acíclico .
  4. T{\displaystyle T}no contiene un ciclo de longitud 3.
  5. La secuencia de puntuación (conjunto de grados de salida) deT{\displaystyle T}es{0,1,2,…,norte−1}{\displaystyle \{0,1,2,\ldots ,n-1\}}.
  6. T{\displaystyle T}tiene exactamente una trayectoria hamiltoniana.

teoría de Ramsey

Los torneos transitivos juegan un papel en la teoría de Ramsey análogo al de las camarillas en los grafos no dirigidos. En particular, cada torneo ennorte{\displaystyle n}vértices contiene un subtorneo transitivo en1+⌊registro2⁡norte⌋{\displaystyle 1+\lfloor \log _{2}n\rfloor }vértices. La prueba es simple: elija cualquier vérticev{\displaystyle v}ser parte de este subtorneo y formar el resto del subtorneo recursivamente en cualquiera de los conjuntos de vecinos entrantes dev{\displaystyle v}o el conjunto de vecinos salientes dev{\displaystyle v}, el que sea mayor. Por ejemplo, todo torneo de siete vértices contiene un subtorneo transitivo de tres vértices; el torneo de Paley de siete vértices muestra que esto es lo máximo que se puede garantizar. [ 12 ] Sin embargo, Reid y Parker (1970) demostraron que esta cota no es ajustada para algunos valores mayores de norte{\displaystyle n}. [ 13 ]

Erdős y Moser (1964) demostraron que hay torneos ennorte{\displaystyle n}vértices sin un subtorneo transitivo de tamaño2+2⌊registro2⁡norte⌋{\displaystyle 2+2\lfloor \log _{2}n\rfloor }Su prueba utiliza un argumento de conteo : el número de maneras en que unk{\displaystyle k}-El elemento transitivo del torneo puede ocurrir como un subtorneo de un torneo más grande ennorte{\displaystyle n}vértices etiquetados es (nortek)k¡2(norte2)−(k2),{\displaystyle {\binom {n}{k}}k!2^{{\binom {n}{2}}-{\binom {k}{2}}},} y cuandok{\displaystyle k}es más grande que2+2⌊registro2⁡norte⌋{\displaystyle 2+2\lfloor \log _{2}n\rfloor }, este número es demasiado pequeño para permitir que se produzca un torneo transitivo dentro de cada uno de los2(norte2){\displaystyle 2^{\binom {n}{2}}}diferentes torneos en el mismo conjunto denorte{\displaystyle n}vértices etiquetados. [ 12 ]

Torneos paradójicos

Un jugador que gana todas las partidas sería, naturalmente, el ganador del torneo. Sin embargo, como demuestra la existencia de torneos no transitivos, puede que no exista tal jugador. Un torneo en el que cada jugador pierde al menos una partida se denomina torneo 1-paradójico. De forma más general, un torneoT=(V,mi){\displaystyle T=(V,E)}se llamak{\displaystyle k}-paradójico si para cadak{\displaystyle k}subconjunto de elementosS{\displaystyle S}deV{\displaystyle V}hay un vérticev0{\displaystyle v_{0}}enV∖S{\displaystyle V\setminus S}de tal manera quev0→v{\displaystyle v_{0}\rightarrow v}a pesar dev∈S{\displaystyle v\in S}. Mediante el método probabilístico , Paul Erdős demostró que para cualquier valor fijo dek{\displaystyle k}, si|V|≥k22kln⁡(2+o(1)){\displaystyle |V|\geq k^{2}2^{k}\ln(2+o(1))}, entonces casi todos los torneos enV{\displaystyle V}esk{\displaystyle k}-paradójico. [ 14 ] Por otro lado, un argumento sencillo muestra que cualquierk{\displaystyle k}-El torneo paradójico debe tener al menos2k+1−1{\displaystyle 2^{k+1}-1}jugadores, lo cual mejoró a(k+2)2k−1−1{\displaystyle (k+2)2^{k-1}-1}por Esther y George Szekeres en 1965. [ 15 ] Hay una construcción explícita dek{\displaystyle k}-torneos paradójicos conk24k−1(1+o(1)){\displaystyle k^{2}4^{k-1}(1+o(1))}jugadores por Graham y Spencer (1971) concretamente el torneo Paley.

Condensación

La condensación de cualquier torneo es en sí misma un torneo transitivo. Por lo tanto, incluso para torneos que no son transitivos, los componentes fuertemente conectados del torneo pueden estar totalmente ordenados. [ 16 ]

Secuencias de puntuación y conjuntos de puntuación

La secuencia de puntuación de un torneo es la secuencia no decreciente de grados de salida de los vértices del torneo. El conjunto de puntuación de un torneo es el conjunto de números enteros que representan los grados de salida de los vértices de dicho torneo.

Teorema de Landau (1953) Una sucesión no decreciente de números enteros(s1,s2,…,snorte){\displaystyle (s_{1},s_{2},\ldots ,s_{n})}es una secuencia de puntuación si y solo si: [ 4 ]

  1. 0≤s1≤s2≤⋯≤snorte{\displaystyle 0\leq s_{1}\leq s_{2}\leq \cdots \leq s_{n}}
  2. s1+s2+⋯+si≥(i2), para i=1,2,…,norte−1{\displaystyle s_{1}+s_{2}+\cdots +s_{i}\geq {i \choose 2},{\text{ for }}i=1,2,\ldots ,n-1}
  3. s1+s2+⋯+snorte=(norte2).{\displaystyle s_{1}+s_{2}+\cdots +s_{n}={n \choose 2}.}

Dejars(norte){\displaystyle s(n)}sea ​​el número de secuencias de puntuación diferentes de tamañonorte{\displaystyle n}La secuencias(norte){\displaystyle s(n)}(secuencia A000571 en el OEIS ) comienza como:

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, ...

Winston y Kleitman demostraron que para n suficientemente grande :

s(norte)>do14nortenorte−5/2,{\displaystyle s(n)>c_{1}4^{n}n^{-5/2},}

dóndedo1=0,049.{\displaystyle c_{1}=0.049.} Takács demostró posteriormente, utilizando algunas suposiciones razonables pero no probadas, que

s(norte)<do24nortenorte−5/2,{\displaystyle s(n)<c_{2}4^{n}n^{-5/2},}

dóndedo2<4.858.{\displaystyle c_{2}<4.858.}[ 17 ]

En conjunto, estos elementos proporcionan evidencia de que:

s(norte)∈Θ(4nortenorte−5/2).{\displaystyle s(n)\in \Theta (4^{n}n^{-5/2}).}

AquíΘ{\displaystyle \Theta }significa una cota asintóticamente ajustada .

Yao demostró que todo conjunto no vacío de enteros no negativos es el conjunto de puntuación de algún torneo. [ 18 ]

Relaciones mayoritarias

En la teoría de la elección social , los torneos surgen naturalmente como relaciones de mayoría de perfiles de preferencia. [ 19 ] SeaA{\displaystyle A}Sea un conjunto finito de alternativas y considere una lista.PAG=(≻1,…,≻norte){\displaystyle P=(\succ _{1},\dots ,\succ _{n})}de órdenes lineales sobreA{\displaystyle A}. Interpretamos cada orden≻i{\displaystyle \succ _{i}}como la clasificación de preferencias de un votantei{\displaystyle i}. La relación de mayoría (estricta)≻comandante{\displaystyle \succ _{\text{maj}}}dePAG{\displaystyle P}encimaA{\displaystyle A}entonces se define de manera quea≻comandanteb{\displaystyle a\succ _{\text{maj}}b}si y solo si la mayoría de los votantes prefierea{\displaystyle a}ab{\displaystyle b}, eso es|{i∈[norte]:a≻ib}|>|{i∈[norte]:b≻ia}|{\displaystyle |\{i\in [n]:a\succ _{i}b\}|>|\{i\in [n]:b\succ _{i}a\}|}. Si el númeronorte{\displaystyle n}El número de votantes es impar, entonces la relación de mayoría forma la relación de dominancia de un torneo en el conjunto de vértices.A{\displaystyle A}.

Por un lema de McGarvey, cada torneo enmetro{\displaystyle m}Los vértices se pueden obtener como la relación de mayoría de como máximometro(metro−1){\displaystyle m(m-1)}votantes. [ 20 ] Los resultados de Stearns y Erdős & Moser establecieron posteriormente queΘ(metro/registro⁡metro){\displaystyle \Theta (m/\log m)}Se necesitan votantes para inducir cada torneo enmetro{\displaystyle m}vértices. [ 21 ]

Laslier (1997) estudia en qué sentido un conjunto de vértices puede llamarse el conjunto de "ganadores" de un torneo. [ 22 ] Esto resultó útil en la ciencia política para estudiar, en modelos formales de economía política , cuál puede ser el resultado de un proceso democrático. [ 23 ]

Véase también

Notas

  1. ^ Weisstein, Eric W. , "Torneo" , MathWorld
  2. ↑ Moulin, Hervé (1986). "Elegir en un torneo" . Social Choice and Welfare . 3 (4): 271– 291. doi : 10.1007/BF00292732 . Recuperado el 19 de enero de 2025. Un torneo es cualquier relación asimétrica completa sobre un conjunto finito A de resultados que describe comparaciones por pares.
  3. ↑ Laffond, Gilbert; Laslier, Jean-Francois; Le Breton, Michel (enero de 1993). "El conjunto bipartidista de un juego de torneo" . Juegos y comportamiento económico . 5 (1): 182–201 . doi : 10.1006/game.1993.1010 . Recuperado el 19 de enero de 2025. Un torneo es una relación binaria asimétrica completa U sobre un conjunto finito X de resultados.
  4. 1 2 Landau (1953) .
  5. ↑ Bar-Noy y Naor (1990) .
  6. ↑ Havet (2013) .
  7. ↑ Camion (1959) .
  8. ↑ Moon (1966) , Teorema 1.
  9. ↑ Thomassen (1980) .
  10. ↑ Fraisse y Thomassen (1987) .
  11. ↑ Bang-Jensen, Gutin y Yeo (1997) .
  12. 1 2 Erdős y Moser (1964) .
  13. ↑ Reid y Parker (1970) .
  14. ↑ Erdős (1963)
  15. ↑ Székeres y Székeres (1965) .
  16. ^ Harary y Moser (1966) , Corolario 5b.
  17. ↑ Takács (1991) .
  18. ↑ Yao (1989) .
  19. ↑ Brandt, Brill y Harrenstein (2016) .
  20. ^ McGarvey (1953) ; Brandt, Brill y Harrenstein (2016)
  21. ^ Stearns (1959) ; Erdős y Moser (1964)
  22. ↑ Laslier (1997) .
  23. ↑ Austen-Smith y Banks (1999) .

Referencias

  • Austen-Smith, D.; Banks, J. (1999), Teoría política positiva , University of Michigan Press
  • Bang-Jensen, J.; Gutin, G .; Yeo, A. (1997), "Ciclos hamiltonianos que evitan arcos prescritos en torneos", Combinatorics, Probability and Computing , 6 (3): 255– 261, doi : 10.1017/S0963548397003027
  • Bar-Noy, A.; Naor, J. (1990), "Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments", SIAM Journal on Discrete Mathematics , 3 (1): 7– 20, doi : 10.1137/0403002
  • Brandt, Félix; Genial, Markus; Harrenstein, Paul (2016), "Capítulo 3: Soluciones para torneos", en Brandt, Felix; Conitzer, Vicente; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (eds.), Manual de elección social computacional , Cambridge University Press, ISBN 9781107060432
  • Camion, Paul (1959), "Chemins et circuitos hamiltoniens des graphes complets" , Comptes Rendus de l'Académie des Sciences de Paris (en francés), 249 : 2151– 2152
  • Erdős, P. (1963), "Sobre un problema en teoría de grafos" (PDF) , The Mathematical Gazette , 47 (361): 220–223 , doi : 10.2307/3613396 , JSTOR 3613396 , MR 0159319  
  • Erdős, P .; Moser, L. (1964), "Sobre la representación de grafos dirigidos como uniones de ordenamientos" (PDF) , Magyar Tud. Akád. Estera. Aeropuerto Internacional de Kutató. Kozl. , 9 : 125-132 , SEÑOR 0168494 
  • Fraisse, P.; Thomassen, C. (1987), "Una solución constructiva a un problema de torneo", Graphs and Combinatorics , 3 : 239–250 , doi : 10.1007/BF01788546.
  • Graham, RL ; Spencer, JH (1971), "Una solución constructiva a un problema de torneo", Canadian Mathematical Bulletin , 14 : 45–48 , doi : 10.4153/cmb-1971-007-1 , MR 0292715 .
  • Harary, Frank ; Moser, Leo (1966), "La teoría de los torneos round robin", American Mathematical Monthly , 73 (3): 231–246 , doi : 10.2307/2315334 , JSTOR 2315334 .
  • Havet, Frédéric (2013), "Sección 3.1: Teorema de Gallai-Roy y resultados relacionados" (PDF) , Orientaciones y coloración de grafos , Apuntes de clase para la escuela de verano SGT 2013 en Oléron, Francia, pp. 15-19 . 
  • Landau, HG (1953), "Sobre las relaciones de dominancia y la estructura de las sociedades animales. III. La condición para una estructura de puntuación", Bulletin of Mathematical Biophysics , 15 (2): 143–148 , doi : 10.1007/BF02476378.
  • Laslier, J.-F. (1997), Soluciones de torneo y votación mayoritaria , Springer
  • McGarvey, David C. (1953), "Un teorema sobre la construcción de paradojas de votación", Econometrica , 21 (4): 608– 610, doi : 10.2307/1907926 , JSTOR 1907926 
  • Moon, JW (1966), "Sobre los subtorneos de un torneo" , Canadian Mathematical Bulletin , 9 (3): 297–301 , doi : 10.4153/CMB-1966-038-7.
  • Rédei, László (1934), "Ein kombinatorischer Satz", Acta Litteraria Szeged , 7 : 39– 43.
  • Reid, KB; Parker, ET (1970), "Refutación de una conjetura de Erdös y Moser", Journal of Combinatorial Theory , 9 (3): 225– 238, doi : 10.1016/S0021-9800(70)80061-8
  • Stearns, Richard (1959), "El problema de la votación", The American Mathematical Monthly , 66 (9): 761– 763, doi : 10.2307/2310461 , JSTOR 2310461 
  • Székeres, E .; Szekeres, G. (1965), "Sobre un problema de Schütte y Erdős", The Mathematical Gazette , 49 (369): 290– 293, doi : 10.2307/3612854 , JSTOR 3612854 , MR 0186566  .
  • Takács, Lajos (1991), "Una excursión de Bernoulli y sus diversas aplicaciones", Advances in Applied Probability , 23 (3), Applied Probability Trust: 557–585 , doi : 10.2307/1427622 , ​​JSTOR 1427622 .
  • Thomassen, Carsten (1980), "Torrementos conectados hamiltonianos", Journal of Combinatorial Theory , Serie B, 28 (2): 142– 163, doi : 10.1016/0095-8956(80)90061-1.
  • Yao, TX (1989), "Sobre la conjetura de Reid de los conjuntos de puntuación para torneos", Chinese Sci. Bull. , 34 : 804–808.

Este artículo incorpora material del torneo en PlanetMath , que está bajo la licencia Creative Commons Attribution/Share-Alike License .