Möbiový žebřík - Möbius ladder - Wikipedia
v teorie grafů, Möbiový žebřík Mn je krychlový oběhový graf s sudé číslo n vrcholů, vytvořených z n-cyklus přidáním hran (nazývaných „příčky“) spojujících protilehlé páry vrcholů v cyklu. Je tak pojmenovaný, protože (s výjimkou M6 = K.3,3 ) Mn má přesně n/ 2 4 cykly[1] které se vzájemně spojují svými společnými okraji a tvoří topologii Möbiusův proužek. Möbiovy žebříky byly pojmenovány a nejprve studovány Chlap a Harary (1967 ).
Vlastnosti
Každý žebřík Möbius je neplanární vrcholový graf, což znamená, že jej nelze nakreslit bez křížení v rovině, ale odstranění jednoho vrcholu umožňuje nakreslit zbývající graf bez křížení. Möbiovy žebříky mají číslo křížení jeden a může být vložen bez křížení na a torus nebo projektivní rovina. Jsou tedy příklady toroidní grafy. Li (2005) zkoumá vložení těchto grafů na povrchy vyšších rodů.
Möbiovy žebříky jsou vrchol-tranzitivní - mají symetrie, které berou jakýkoli vrchol na jakýkoli jiný vrchol - ale (opět s výjimkou M6) nejsou hrana tranzitivní. Okraje z cyklu, ze kterého je žebřík vytvořen, lze odlišit od příček žebříku, protože každá hrana cyklu patří do jednoho 4-cyklu, zatímco každá příčka patří do dvou takových cyklů. Proto neexistuje žádná symetrie, která by vedla hranu cyklu na hranu příčky nebo naopak.
Když n ≡ 2 (mod 4), Mn je bipartitní. Když n ≡ 0 (mod 4), není to bipartita. Koncové body každé příčky jsou v počátečním cyklu od sebe rovnoměrně vzdálené, takže přidání každé příčky vytvoří lichý cyklus. V tomto případě, protože graf je 3-pravidelný, ale není bipartitní, Brooksova věta má to chromatické číslo 3. De Mier & Noy (2004) ukazují, že žebříky Möbius jsou jednoznačně určeny svými Výukové polynomy.
Möbiový žebřík M8 má 392 klenout se nad stromy; to a M6 mít nejvíce kostry mezi všemi kubickými grafy se stejným počtem vrcholů.[2] Desetimístný kubický graf s nejrozsáhlejšími stromy je však Petersenův graf, což není Möbiový žebřík.
The Výukové polynomy žebříků Möbius lze vypočítat jednoduchým způsobem relace opakování.[3]
Graf nezletilí
Möbiovy žebříky hrají důležitou roli v teorii nezletilí v grafu. Nejstarším výsledkem tohoto typu je věta o Klaus Wagner (1937 ), že grafy s č K.5 menší lze vytvořit pomocí klika-součet operace kombinující rovinné grafy a Möbiový žebřík M8; z tohoto důvodu M8 se nazývá Wagnerův graf.
Gubser (1996) definuje téměř rovinný graf být neplanární graf, pro který je každá netriviální molární rovinná; on ukazuje, že 3-spojené téměř rovinné grafy jsou Möbiovy žebříky nebo členy malého počtu dalších rodin a že z nich lze vytvořit další téměř rovinné grafy posloupností jednoduchých operací.
Maharry (2000) ukazuje, že téměř všechny grafy, které nemají a krychle menší lze odvodit posloupností jednoduchých operací z Möbiových žebříků.
Chemie a fyzika
Walba, Richards a Haltiwanger (1982) nejprve syntetizované molekulární struktury ve formě Möbiova žebříku a od té doby je tato struktura zajímavá v chemii a chemické stereografii,[4] zejména s ohledem na žebříkovou formu molekul DNA. S ohledem na tuto aplikaci Flapan (1989 ) studuje matematické symetrie vložení Möbiových žebříků do R3. Zejména, jak ukazuje, každé trojrozměrné vložení Möbiova žebříku s lichým počtem příček je topologicky chirální: nelze jej převést na zrcadlový obraz kontinuální deformací prostoru, aniž by jedna hrana prošla druhou. Na druhou stranu, do Möbiových žebříků se sudým počtem příček jsou všechny zabudovány R3 které se mohou deformovat do jejich zrcadlových obrazů.
Möbiovy žebříky byly také použity jako tvar a supravodivé prsten v experimentech ke studiu účinků topologie vodičů na elektronové interakce.[5]
Kombinatorická optimalizace
Möbius žebříky byly také použity v počítačová věda, jako část celočíselné programování přístupy k problémům množinového balení a lineárního řazení. Určité konfigurace v rámci těchto problémů lze použít k definování aspektů polytop popisující a lineární programování relaxace problému; tyto fasety se nazývají Möbiovy žebříkové omezení.[6]
Viz také
Poznámky
- ^ McSorley (1998).
- ^ Jakobson & Rivin (1999); Valdes (1991).
- ^ Biggs, Damerell & Sands (1972).
- ^ Simon (1992).
- ^ Mila, Stafford & Capponi (1998); Deng, Xu & Liu (2002).
- ^ Bolotashvili, Kovalev & Girlich (1999); Borndörfer & Weismantel (2000); Grötschel, Jünger a Reinelt (1985a, 1985b ); Newman & Vempala (2001)
Reference
- Biggs, N.L.; Damerell, R. M .; Sands, D. A. (1972). "Rekurzivní rodiny grafů". Journal of Combinatorial Theory. Řada B. 12 (2): 123–131. doi:10.1016/0095-8956(72)90016-0. PAN 0294172.CS1 maint: ref = harv (odkaz)
- Bolotashvili, G .; Kovalev, M .; Girlich, E. (1999). Msgstr "Nové aspekty lineárně uspořádaného polytopu". SIAM Journal on Discrete Mathematics. 12 (3): 326–336. CiteSeerX 10.1.1.41.8722. doi:10.1137 / S0895480196300145. PAN 1710240.CS1 maint: ref = harv (odkaz)
- Borndörfer, Ralf; Weismantel, Robert (2000). Msgstr "Nastavit uvolnění balení některých celočíselných programů". Matematické programování. Řada A. 88 (3): 425–450. doi:10.1007 / PL00011381. PAN 1782150. S2CID 206862305.CS1 maint: ref = harv (odkaz)
- Deng, Wen-Ji; Xu, Ji-Huan; Liu, Ping (2002). "Období poloviny trvalých proudů v mezoskopických Möbiových žebřících". Čínská fyzikální písmena. 19 (7): 988–991. arXiv:cond-mat / 0209421. Bibcode:2002ChPhL..19..988D. doi:10.1088 / 0256-307X / 19/7/333. S2CID 119421223.CS1 maint: ref = harv (odkaz)
- Flapan, Erica (1989). „Symetrie Möbiových žebříků“. Mathematische Annalen. 283 (2): 271–283. doi:10.1007 / BF01446435. PAN 0980598. S2CID 119705062.CS1 maint: ref = harv (odkaz)
- Grötschel, M.; Jünger, M .; Reinelt, G. (1985a). Msgstr "Na acyklickém podgrafu mnohostěnu". Matematické programování. 33: 28–42. doi:10.1007 / BF01582009. PAN 0809747. S2CID 206798683.CS1 maint: ref = harv (odkaz)
- Grötschel, M .; Jünger, M .; Reinelt, G. (1985b). "Fazety polytopu s lineárním uspořádáním". Matematické programování. 33: 43–60. doi:10.1007 / BF01582010. PAN 0809748. S2CID 21071064.CS1 maint: ref = harv (odkaz)
- Gubser, Bradley S. (1996). "Charakterizace téměř rovinných grafů". Kombinatorika, pravděpodobnost a výpočet. 5 (3): 227–245. doi:10.1017 / S0963548300002005. PAN 1411084.CS1 maint: ref = harv (odkaz)
- Guy, Richard K.; Harary, Franku (1967). „Na žebřících Möbius“. Kanadský matematický bulletin. 10 (4): 493–496. doi:10.4153 / CMB-1967-046-4. PAN 0224499.CS1 maint: ref = harv (odkaz)
- Jakobson, Dmitry; Rivin, Igor (1999). „O některých extrémních problémech v teorii grafů“. arXiv:math.CO/9907050. Citovat deník vyžaduje
| deník =(Pomoc)CS1 maint: ref = harv (odkaz) - Li, Deming (2005). "Rodové distribuce Möbiových žebříků". Northeastern Mathematics Journal. 21 (1): 70–80. PAN 2124859.CS1 maint: ref = harv (odkaz)
- Maharry, John (2000). "Charakterizace grafů bez menších krychlí". Journal of Combinatorial Theory. Řada B. 80 (2): 179–201. doi:10.1006 / jctb.2000.1968. PAN 1794690.CS1 maint: ref = harv (odkaz)
- McSorley, John P. (1998). "Počítání struktur v Möbiově žebříku". Diskrétní matematika. 184 (1–3): 137–164. doi:10.1016 / S0012-365X (97) 00086-1. PAN 1609294.CS1 maint: ref = harv (odkaz)
- De Mier, Anna; Noy, Marc (2004). "Na grafech určených jejich Tutteovými polynomy". Grafy a kombinatorika. 20 (1): 105–119. doi:10.1007 / s00373-003-0534-z. PAN 2048553. S2CID 46312268.CS1 maint: ref = harv (odkaz)
- Mila, Frédéric; Stafford, C. A .; Capponi, Sylvain (1998). „Trvalé proudy v Möbiově žebříku: Test koherence mezi řetězci interagujících elektronů“ (PDF). Fyzický přehled B. 57 (3): 1457–1460. arXiv:cond-mat / 9705119. Bibcode:1998PhRvB..57.1457M. doi:10.1103 / PhysRevB.57.1457. S2CID 35931632.CS1 maint: ref = harv (odkaz)
- Newman, Alantha; Vempala, Santosh (2001). „Ploty jsou marné: na uvolnění pro problém lineárního řazení“. Celočíselné programování a kombinatorická optimalizace: 8. mezinárodní konference IPCO, Utrecht, Nizozemsko, 13. – 15. Června 2001, sborník. Přednášky z informatiky. 2081. Berlín: Springer-Verlag. 333–347. doi:10.1007/3-540-45535-3_26. PAN 2041937. Archivovány od originál dne 02.01.2004. Citováno 2006-10-08.CS1 maint: ref = harv (odkaz)
- Simon, Jonathan (1992). "Uzly a chemie". Nové vědecké aplikace geometrie a topologie (Baltimore, MD, 1992). Proceedings of Symposia in Applied Mathematics. 45. Providence, RI: Americká matematická společnost. 97–130. PAN 1196717.CS1 maint: ref = harv (odkaz)
- Valdes, L. (1991). Msgstr "Extrémní vlastnosti překlenujících stromů v kubických grafech". Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991). Congressus Numerantium. 85. 143–160. PAN 1152127.CS1 maint: ref = harv (odkaz)
- Wagner, K. (1937). „Über eine Eigenschaft der ebenen Komplexe“. Mathematische Annalen. 114: 570–590. doi:10.1007 / BF01594196. PAN 1513158. S2CID 123534907.CS1 maint: ref = harv (odkaz)
- Walba, D .; Richards, R .; Haltiwanger, R. C. (1982). "Celková syntéza prvního molekulárního Möbiova pásu". Journal of the American Chemical Society. 104 (11): 3219–3221. doi:10.1021 / ja00375a051.CS1 maint: ref = harv (odkaz)