| 释义 |
- Definition
- Constructions
- Extensions
- Notes
- References
- Further reading
In mathematics, a partial cyclic order is a ternary relation that generalizes a cyclic order in the same way that a partial order generalizes a linear order. Definition{{sfn|Novák|1982}}ConstructionsDirect sum Direct product Power{{sfn|Novák|Novotný|1984a}}{{sfn|Novák|Novotný|1984b}} Dedekind–MacNeille completionExtensionslinear extension, Szpilrajn extension theoremstandard exampleThe relationship between partial and total cyclic orders is more complex than the relationship between partial and total linear orders. To begin with, not every partial cyclic order can be extended to a total cyclic order. An example is the following relation on the first thirteen letters of the alphabet: {acd, bde, cef, dfg, egh, fha, gac, hcb} ∪ {abi, cij, bjk, ikl, jlm, kma, lab, mbc} ∪ {hcm, bhm}. This relation is a partial cyclic order, but it cannot be extended with either abc or cba; either attempt would result in a contradiction.{{sfn|Megiddo|1976|pp=274–275}} The above was a relatively mild example. One can also construct partial cyclic orders with higher-order obstructions such that, for example, any 15 triples can be added but the 16th cannot. In fact, cyclic ordering is NP-complete, since it solves 3SAT. This is in stark contrast with the recognition problem for linear orders, which can be solved in linear time.{{sfn|Megiddo|1976|pp=275–276}}{{sfn|Galil|Megiddo|1977|p=179}} NotesReferences{{Refbegin}}- {{Citation |last=Galil |first=Zvi |authorlink=Zvi Galil|last2=Megiddo |first2=Nimrod|author2-link=Nimrod Megiddo |date=October 1977 |title=Cyclic ordering is NP-complete |journal=Theoretical Computer Science |volume=5 |issue=2 |pages=179–182 |doi=10.1016/0304-3975(77)90005-6 |url=http://theory.stanford.edu/~megiddo/pdf/cyc-npc.pdf |accessdate=30 April 2011}}
- {{Citation |last=Megiddo |first=Nimrod |authorlink=Nimrod Megiddo|date=March 1976 |title=Partial and complete cyclic orders |journal=Bulletin of the American Mathematical Society |volume=82 |issue=2 |pages=274–276 |doi=10.1090/S0002-9904-1976-14020-7 |url=http://www.ams.org/journals/bull/1976-82-02/S0002-9904-1976-14020-7/S0002-9904-1976-14020-7.pdf |accessdate=30 April 2011}}
- {{Citation |last=Novák |first=Vítězslav |year=1982 |title=Cyclically ordered sets |journal=Czechoslovak Mathematical Journal |volume=32 |issue=3 |pages=460–473 |hdl=10338.dmlcz/101821 |url=http://dml.cz/bitstream/handle/10338.dmlcz/101821/CzechMathJ_32-1982-3_12.pdf |accessdate=30 April 2011}}
- {{Citation |last=Novák |first=Vítězslav |last2=Novotný |first2=Miroslav |year=1984a |title=On a power of cyclically ordered sets |journal=Časopis pro pěstování matematiky |volume=109 |issue=4 |pages=421–424 |hdl=10338.dmlcz/118209 |url=http://dml.cz/bitstream/handle/10338.dmlcz/118209/CasPestMat_109-1984-4_7.pdf |accessdate=30 April 2011}}
- {{Citation |last=Novák |first=Vítězslav |last2=Novotný |first2=Miroslav |year=1984b |title=Universal cyclically ordered sets |journal=Czechoslovak Mathematical Journal |volume=35 |issue=1 |pages=158–161 |hdl=10338.dmlcz/102004 |url=http://dml.cz/bitstream/handle/10338.dmlcz/102004/CzechMathJ_35-1985-1_11.pdf |accessdate=30 April 2011}}
{{Refend}}Further reading{{Refbegin}}- {{Citation |last=Alles |first=Peter |last2=Nešetřil |first2=Jaroslav |last3=Poljak |first3=Svatopluck |year=1991 |title=Extendability, Dimensions, and Diagrams of Cyclic Orders |journal=SIAM Journal on Discrete Mathematics |volume=4 |issue=4 |pages=453–471 |doi=10.1137/0404041}}
- {{Citation |last=Bandelt |first=Hans–Jürgen |last2=Chepoi |first2=Victor |last3=Eppstein |first3=David |author3-link=David Eppstein|year=2010 |title=Combinatorics and geometry of finite and infinite squaregraphs |journal=SIAM Journal on Discrete Mathematics |volume=24 |issue=4 |pages=1399–1440 |doi=10.1137/090760301 |url=http://epub.sub.uni-hamburg.de/epub/volltexte/2009/3280/pdf/0905.4537v1.pdf |accessdate=23 May 2011 |arxiv=0905.4537}}
- {{Citation |last=Chajda |first=Ivan |last2=Novák |first2=Vítězslav |year=1985 |title=On extensions of cyclic orders |journal=Časopis pro pěstování matematiky |volume=110 |issue=2 |pages=116–121 |hdl=10338.dmlcz/108597 |url=http://dml.cz/bitstream/handle/10338.dmlcz/108597/CasPestMat_110-1985-2_2.pdf |accessdate=30 April 2011}}
- {{Citation |last=Fishburn |first=P. C. |authorlink=Peter C. Fishburn|last2=Woodall |first2=D. R. |date=June 1999 |title=Cycle Orders |journal=Order |volume=16 |issue=2 |pages=149–164 |doi=10.1023/A:1006381208272}}
- {{Citation |last=Haar |first=Stefan |year=2001 |chapter=Cyclic and partial order models for concurrency |title=Geometry and Topology in Concurrency Theory GETCO ’01 |pages=51–62 |url=http://www.brics.dk/NS/01/7/BRICS-NS-01-7.pdf |accessdate=23 May 2011}}
- {{Citation |last=Ille |first=Pierre |last2=Ruet |first2=Paul |date=30 April 2008 |title=Cyclic Extensions of Order Varieties |journal=Electronic Notes in Theoretical Computer Science |volume=212 |pages=119–132 |doi=10.1016/j.entcs.2008.04.057 |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.2305 |accessdate=23 May 2011}}
- {{Citation |last=Jakubík |first=Ján |year=1994 |title=On extended cyclic orders |journal=Czechoslovak Mathematical Journal |volume=44 |issue=4 |pages=661–675 |hdl=10338.dmlcz/128486 |url=http://dml.cz/bitstream/handle/10338.dmlcz/128486/CzechMathJ_44-1994-4_8.pdf |accessdate=30 April 2011}}
- {{Citation |last=Melliès |first=Paul-André |year=2004 |chapter=A topological correctness criterion for non-commutative logic |editor=Thomas Ehrhard and Jean-Yves Girard and Paul Ruet and Philip Scott |title=Linear Logic in Computer Science |pages=283–323 |url=http://hal.archives-ouvertes.fr/docs/00/15/42/04/PDF/critere.pdf |accessdate=23 May 2011}}
- {{Citation |last=Novák |first=Vítězslav |year=1984 |title=On some minimal problem |journal=Archivum Mathematicum |volume=20 |issue=2 |pages=95–99 |hdl=10338.dmlcz/107191 |zbl=0554.06003 |mr=784860 |url=http://dml.cz/bitstream/handle/10338.dmlcz/107191/ArchMath_020-1984-2_5.pdf |accessdate=23 May 2011}}
- {{Citation |last=Stehr |first=Mark-Oliver |year=1998 |chapter=Thinking in Cycles |pages=205–225 |editor-first=Jörg |editor-last=Desel |editor2-first=Manuel |editor2-last=Silva |title=ICATPN '98 Proceedings of the 19th International Conference on Application and Theory of Petri Nets |series=Lecture Notes in Computer Science |volume=1420 |isbn=3-540-64677-9 |doi=10.1007/3-540-69108-1_12}}{{Refend}}
- S. Haar. Cyclic Ordering through Partial Orders. Journal of Multiple-Valued Logic and Soft Computing 27(2-3), pages 209-228, 2016.
- http://www.lif.univ-mrs.fr/~lsantoca/TRECOLOCOCO/rencontre_Marseille/Stefan.pdf
2 : Order theory|Circles |