Möbiův žebřík
Möbiův žebřík je kubický oběžný graf se sudým počtem vrcholů , vytvořený z cyklu s vrcholy přidáním hran (nazývaných „příčky“) spojujícími opačné páry vrcholů cyklu. Pojmenováno tak, protože sestává z cyklů délky 4 [1] spojených společnými hranami a topologicky tvořících Möbiův pás . Kompletní bipartitní graf (graf „ domy a studny “) je Möbiův žebřík (na rozdíl od ostatních má další cykly o délce 4).
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![M_{n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8656f32ad5c50e679b491b361a423727491496a0)
![K_{{3,3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb683d61b6b89e9e408ac8488e97d892e1776fa8)
![{\displaystyle M_{6}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5872ee52818f77fc3d6d8b15a0f665a740de9cf4)
![{\displaystyle M_{6}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5872ee52818f77fc3d6d8b15a0f665a740de9cf4)
Nejprve studoval Guy a Harari [2] .
Vlastnosti
Jakýkoli Möbiův žebřík je nerovinný vrcholový graf. Počet překročení Möbiova žebříku je jeden a graf lze vložit bez průsečíků do torusové nebo projektivní roviny (tj. je to toroidní graf ). Lee [3] studoval vkládání těchto grafů do povrchů vyšších rodů.
Möbiovy schody jsou vrcholově tranzitivní , ale (s výjimkou ) ne hraně tranzitivní - každá hrana cyklu, ze kterého je žebřík vytvořen, patří do jednoho 4hranného cyklu, zatímco každá příčka patří do dvou takových cyklů.
![{\displaystyle M_{6}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5872ee52818f77fc3d6d8b15a0f665a740de9cf4)
Jestliže , pak je bipartitní . Když je podle Brooksova teorému chromatické číslo 3. Je známo [4] , že Möbiův žebřík je jednoznačně určen jeho polynomem Tatta .
![{\displaystyle n\equiv 2{\pmod {4}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/38ae7eda971a300bb76ee1d17c1933406a2c74f5)
![M_{n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8656f32ad5c50e679b491b361a423727491496a0)
![M_{n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8656f32ad5c50e679b491b361a423727491496a0)
Möbiův žebřík má 392 kostrových stromů . Tento graf má také největší počet kostry mezi kubickými grafy se stejným počtem vrcholů [5] [6] . Mezi kubickými grafy s 10 vrcholy má však Petersenův graf největší počet kostry , což není Möbiův žebřík.
![{\displaystyle M_{8}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6aa576eff43aba0c003279050c77a0d95c2fc7b)
![{\displaystyle M_{6}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5872ee52818f77fc3d6d8b15a0f665a740de9cf4)
Tuttovy polynomy Möbiových žebříků lze získat jednoduchým rekurzivním vzorcem [7] .
Počítat nezletilé
Möbiovy schody hrají důležitou roli v teorii graf minors . Nejranějším výsledkem tohoto typu je Wagnerova věta [8] , že graf, který neobsahuje -minory, lze vytvořit pomocí klikových součtů pro kombinaci rovinných grafů a Möbiova žebříku (v této souvislosti nazývaného Wagnerův graf .
![K_{5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10a83da34fe45aa3be9a7d0b197417021bb4a884)
![{\displaystyle M_{8}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6aa576eff43aba0c003279050c77a0d95c2fc7b)
![M_{n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8656f32ad5c50e679b491b361a423727491496a0)
Všechny 3-spojené téměř rovinné grafy [9] jsou Möbiovy žebříky nebo patří do malého počtu jiných rodin a zbytek téměř rovinných grafů lze z těchto grafů získat pomocí řady jednoduchých operací [10] .
Téměř všechny[ upřesnit ] grafy, které neobsahují kostku jako vedlejší, lze získat z Möbiových žebříků jako výsledek sekvenční aplikace jednoduchých operací [11] .
Chemie a fyzika
V roce 1982 byla syntetizována molekulární struktura ve formě Möbiova žebříku [12] a od té doby jsou takové grafy zajímavé pro chemiky a chemickou stereografii [13] , zejména ve světle molekul DNA podobných Möbiovu žebříku. S ohledem na tuto skutečnost byly matematické symetrie vložení Möbiových žebříků speciálně studovány v [14] .
![\mathbb {R} ^{3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f936ddf584f8f3dd2a0ed08917001b7a404c10b5)
Möbiovy žebříky se používají jako model supravodivého prstence v experimentech ke studiu vlivů topologie vedení při interakci elektronů [15] [16] .
Kombinatorická optimalizace
Möbiovy žebříky se také používají v informatice jako součást přístupu celočíselného programování k problémům s balením množin a lineárním uspořádáním. Některé konfigurace v těchto úlohách mohou být použity k definování ploch polytopů , které popisují relaxaci podmínek lineárního programování . Tyto plochy se nazývají omezení Möbiových schodů [17] [18] [19] [20] .
Viz také
Poznámky
- ↑ McSorley, 1998 .
- ↑ Guy, Harari, 1967 .
- ↑ Lee, 2005 .
- ↑ De Mieu, Nua, 2004 .
- ↑ Jacobson, Rivin, 1999 .
- ↑ Valdes, 1991 .
- ↑ Biggs, Daymrell, Sands, 1972 .
- ↑ Wagner, 1937 .
- ↑ Téměř rovinný graf je nerovinný graf, pro který je každá netriviální vedlejší rovina rovinná
- ↑ Gubser, 1996 .
- ↑ Maharri, 2000 .
- ↑ Walba, Richards, Haltiwanger 1982 .
- ↑ Simon, 1992 .
- ↑ Flapan, 1989 .
- ↑ Mila, Stafford, Capponi, 1998 .
- ↑ Deng, Xu, Liu, 2002 .
- ↑ Bolotashvili, Kovalev, Girlich, 1999 .
- ↑ Borndörfer, Weissmantel, 2000 .
- ↑ Grötschel, Jünger, Reinelt, 1985 .
- ↑ Newman, Vempala, 2001 .
Literatura
- NL Biggs, RM Damerell, DA Sands. Rekurzivní rodiny grafů // Journal of Combinatorial Theory . - 1972. - T. 12 . — S. 123–131 . - doi : 10.1016/0095-8956(72)90016-0 .
- G. Bolotashvili, M. Kovalev, E. Girlich. Nové aspekty polytopu lineárního uspořádání // SIAM Journal on Discrete Mathematics . - 1999. - T. 12 , no. 3 . — S. 326–336 . - doi : 10.1137/S0895480196300145 .
- Ralf Borndörfer, Robert Weismantel. Nastavte balící relaxace některých celočíselných programů // Matematické programování . - 2000. - T. 88 , čís. 3 . — S. 425–450 . - doi : 10.1007/PL00011381 .
- Wen-Ji Deng, Ji-Huan Xu, Ping Liu. Periodické půlení perzistentních proudů v mezoskopických Möbiových žebřících // Chinese Physics Letters . - 2002. - T. 19 , vydání. 7 . — S. 988–991 . - doi : 10.1088/0256-307X/19/7/333 . - arXiv : cond-mat/0209421 .
- Erika Flapanová. Symetrie Möbiových žebříků // Mathematische Annalen . - 1989. - T. 283 , čís. 2 . — S. 271–283 . - doi : 10.1007/BF01446435 .
- M. Grötschel, M. Junger, G. Reinelt. Na acyklickém podgrafu polytop // Matematické programování . - 1985. - T. 33 . — S. 28–42 . - doi : 10.1007/BF01582009 .
- M. Grötschel, M. Junger, G. Reinelt. Fasety polytopu lineárního uspořádání // Matematické programování . - 1985. - T. 33 . — S. 43–60 . - doi : 10.1007/BF01582010 .
- Bradley S Gubser. Charakterizace téměř rovinných grafů // Kombinatorika, pravděpodobnost a výpočetní technika. - 1996. - V. 5 , čís. 3 . — S. 227–245 . - doi : 10.1017/S0963548300002005 .
- Richard K. Guy, Frank Harary. On the Möbius ladders // Canadian Mathematical Bulletin . - 1967. - T. 10 . — S. 493–496 . - doi : 10.4153/CMB-1967-046-4 .
- Dmitrij Jakobson, Igor Rivin. O některých extrémních problémech v teorii grafů. - 1999. - arXiv : math.CO/9907050 .
- Deming Li. Rodová distribuce Möbiových žebříků // Northeastern Mathematics Journal. - 2005. - T. 21 , no. 1 . — S. 70–80 .
- John Maharry. Charakterizace grafů bez krychle // Journal of Combinatorial Theory . - 2000. - T. 80 , no. 2 . — S. 179–201 . - doi : 10.1006/jctb.2000.1968 .
- John P. McSorley. Počítání struktur v Möbiově žebříku // Diskrétní matematika . - 1998. - T. 184 , no. 1–3 . — S. 137–164 . - doi : 10.1016/S0012-365X(97)00086-1 .
- Anna De Mier, Marc Noy. Na grafech určených jejich Tutteovými polynomy // Grafy a kombinatorika. - 2004. - T. 20 , no. 1 . — S. 105–119 . - doi : 10.1007/s00373-003-0534-z .
- Frederic Mila, CA Stafford, Sylvain Capponi. Perzistentní proudy v Möbiově žebříku: Test meziřetězcové koherence interagujících elektronů // Fyzikální přehled B . - 1998. - T. 57 , no. 3 . - S. 1457-1460 . - doi : 10.1103/PhysRevB.57.1457 .
- Alantha Newman, Santosh Vempala. Celočíselné programování a kombinatorická optimalizace: 8. mezinárodní konference IPCO, Utrecht, Nizozemsko, 13.–15. června 2001, sborník příspěvků. - Berlin: Springer-Verlag, 2001. - T. 2081. - S. 333-347. — (Poznámky z informatiky). - doi : 10.1007/3-540-45535-3_26 .
- Jonathan Simon. Nové vědecké aplikace geometrie a topologie (Baltimore, MD, 1992). - Providence, RI: American Mathematical Society , 1992. - V. 45. - S. 97-130. — (Sborník sympozií v aplikované matematice).
- L. Valdes. Sborník z 22. jihovýchodní konference o kombinatorice, teorii grafů a počítačích (Baton Rouge, LA, 1991). - 1991. - T. 85. - S. 143-160. — (Congressus Numerantium).
- K. Wagner. Über eine Eigenschaft der ebenen Komplexe // Mathematische Annalen. - 1937. - T. 114 . — S. 570–590 . - doi : 10.1007/BF01594196 .
- D. Walba, R. Richards, R. C. Haltiwanger. Totální syntéza prvního molekulárního Möbiova proužku // Journal of the American Chemical Society. - 1982. - T. 104 , čís. 11 . — S. 3219–3221 . - doi : 10.1021/ja00375a051 .
Odkazy