En matemáticas, un orden cíclico parcial es una relación ternaria que generaliza un orden cíclico de la misma forma que un orden parcial generaliza un orden lineal .
Definición
Sobre un conjunto dado, un orden cíclico parcial es una relación ternaria es decir:
- cíclico , es decir, es invariante bajo una permutación cíclica :
- asimétrico :
- transitivo : y [1]
Construcciones
Extensiones
extensión lineal , teorema de extensión de Szpilrajn
ejemplo estándar
La relación entre órdenes cíclicos totales y parciales es más compleja que la relación entre órdenes lineales totales y parciales. Para empezar, no todo orden cíclico parcial puede extenderse a un orden cíclico total. Un ejemplo es la siguiente relación en las primeras trece letras del alfabeto: { acd, bde, cef, dfg, egh, fha, gac, hcb } ∪ { abi, cij, bjk, ikl, jlm, kma, lab, mbc } . Esta relación es un orden cíclico parcial, pero no puede extenderse ni con abc ni con cba ; cualquier intento resultaría en una contradicción. [4]
Lo anterior fue un ejemplo relativamente moderado. También se pueden construir órdenes cíclicos parciales con obstrucciones de orden superior de modo que, por ejemplo, se pueden agregar 15 triples cualesquiera pero no el 16. De hecho, el orden cíclico es NP-completo , ya que resuelve 3SAT . Esto está en marcado contraste con el problema de reconocimiento de órdenes lineales, que puede resolverse en tiempo lineal . [5] [6]
Notas
- ↑ Novák, 1982 .
- ^ Novák y Novotný 1984a .
- ^ Novák y Novotný 1984b .
- ^ Megiddo 1976 , págs. 274-275.
- ^ Megiddo 1976 , págs. 275-276.
- ^ Galil y Megiddo 1977 , p. 179.
Referencias
- Galil, Zvi ; Megiddo, Nimrod (octubre de 1977), "Cyclic ordering is NP-complete" (PDF) , Theoretical Computer Science , 5 (2): 179-182, doi : 10.1016 / 0304-3975 (77) 90005-6 , consultado el 30 de abril 2011
- Megiddo, Nimrod (marzo de 1976), "Órdenes cíclicos parciales y completos" (PDF) , Bulletin of the American Mathematical Society , 82 (2): 274-276, doi : 10.1090 / S0002-9904-1976-14020-7 , recuperado 30 de abril de 2011
- Novák, Vítězslav (1982), "Conjuntos ordenados cíclicamente" (PDF) , Czechoslovak Mathematical Journal , 32 (3): 460–473, doi : 10.21136 / CMJ.1982.101821 , hdl : 10338.dmlcz / 101821 , consultado el 30 de abril de 2011
- Novák, Vítězslav; Novotný, Miroslav (1984a), "Sobre una potencia de conjuntos ordenados cíclicamente" (PDF) , Časopis Pro Pěstování Matematiky , 109 (4): 421–424, doi : 10.21136 / CPM.1984.118209 , hdl : 10338.dmlcz / 118209 , consultado el 30 de abril de 2011
- Novák, Vítězslav; Novotný, Miroslav (1984b), "Conjuntos ordenados cíclicamente universales" (PDF) , Czechoslovak Mathematical Journal , 35 (1): 158–161, doi : 10.21136 / CMJ.1985.102004 , hdl : 10338.dmlcz / 102004 , consultado el 30 de abril de 2011
Otras lecturas
- Alles, Peter; Nešetřil, Jaroslav; Poljak, Svatopluck (1991), "Extendability, Dimensions, and Diagrams of Cyclic Orders", SIAM Journal on Discrete Mathematics , 4 (4): 453–471, doi : 10.1137 / 0404041
- Bandelt, Hans – Jürgen; Chepoi, Victor; Eppstein, David (2010), "Combinatoria y geometría de gráficos cuadrados finitos e infinitos" (PDF) , SIAM Journal on Discrete Mathematics , 24 (4): 1399-1440, arXiv : 0905.4537 , doi : 10.1137 / 090760301 , S2CID 10788524 , recuperado 23 de mayo de 2011
- Chajda, Ivan; Novák, Vítězslav (1985), "On extensions of cyclic orders" (PDF) , Časopis Pro Pěstování Matematiky , 110 (2): 116-121, doi : 10.21136 / CPM.1985.108597 , hdl : 10338.dmlcz / 108597 , consultado 30 Abril de 2011
- Fishburn, PC ; Woodall, DR (junio de 1999), "Órdenes de ciclo", Orden , 16 (2): 149-164, doi : 10.1023 / A: 1006381208272 , S2CID 37680085
- Haar, Stefan (2001), "Modelos cíclicos y de orden parcial para la concurrencia" (PDF) , Geometry and Topology in Concurrency Theory GETCO '01 , págs. 51–62 , consultado el 23 de mayo de 2011
- Ille, Pierre; Ruet, Paul (30 de abril de 2008), "Cyclic Extensions of Order Varieties", Electronic Notes in Theoretical Computer Science , 212 : 119-132, CiteSeerX 10.1.1.103.2305 , doi : 10.1016 / j.entcs.2008.04.057
- Jakubík, Ján (1994), "On extended cyclic orders" (PDF) , Czechoslovak Mathematical Journal , 44 (4): 661–675, doi : 10.21136 / CMJ.1994.128486 , hdl : 10338.dmlcz / 128486 , consultado el 30 de abril de 2011
- Melliès, Paul-André (2004), "Un criterio de corrección topológica para la lógica no conmutativa" (PDF) , en Thomas Ehrhard y Jean-Yves Girard y Paul Ruet y Philip Scott (ed.), Linear Logic in Computer Science , págs. . 283–323 , consultado el 23 de mayo de 2011
- Novák, Vítězslav (1984), "On some minimal problem" (PDF) , Archivum Mathematicum , 20 (2): 95–99, hdl : 10338.dmlcz / 107191 , MR 0784860 , Zbl 0554.06003 , consultado el 23 de mayo de 2011
- Stehr, Mark-Oliver (1998), "Pensando en ciclos", en Desel, Jörg; Silva, Manuel (eds.), ICATPN '98 Proceedings of the 19th International Conference on Application and Theory of Petri Nets , Lecture Notes in Computer Science, 1420 , pp. 205–225, doi : 10.1007 / 3-540-69108-1_12 , ISBN 3-540-64677-9
- Haar, Stefan (2016), "Orden cíclico a través de órdenes parciales" (PDF) , Journal of Multiple-Valued Logic and Soft Computing , Old City Publishing, 27 (2–3): 209–228