Möbius-létra

A matematika, azon belül a gráfelmélet területén a Möbius-létra, M_n olyan, páros n számú csúcsból álló 3-reguláris cirkuláns gráf, ami egy n-körből hozható létre a kör szemközti csúcspárjainak összekötésével (a létra fokainak hozzáadásával), vagy ezzel ekvivalens módon, egy létragráf négy 2 fokszámú csúcsát keresztben összekötve. Nevét onnan kapta, hogy (az M₆, azaz a K_3,3 kivételével) az M_n pontosan n/2 4-körrel rendelkezik, melyek közös élei topológiailag egy Möbius-szalagot alkotnak. A Möbius-létrákat Guy and Harary (1967) nevezte el és vizsgálta elsőként.

Az M₁₆ Möbius-létra két nézete; a kettő közötti transzformációt megmutató animáció: itt megtekinthető.

Tulajdonságok

A Möbius-létrák síkba nem rajzolható csúcsgráfok, ami azt jelenti, nem rajzolhatók le a síkba egymást metsző élek nélkül, de egyetlen csúcs eltávolításával már igen. A Möbius-létrák metszési száma egy, tóruszfelületbe vagy projektív síkba metszés nélkül beágyazhatók. Így a tóruszra rajzolható gráfok közé tartozik. (Li 2005) vizsgálja ezen gráfok magasabb génuszú felületekbe ágyazását.

A Möbius-létrák csúcstranzitívak – rendelkeznek bármely csúcsot bármely másik csúcsba átvivő szimmetriákkal – de (ismét az M₆ kivételével) nem éltranzitívak. A létrát alkotó kör élei megkülönböztethetők a létra fokaitól, mivel a körbe tartozó élek egyetlen 4-kör részét képezik, míg a létra fokai két-két ilyen körhöz tartoznak. Ezért nem létezik a kör éleit létrafok-élbe, vagy a létrafok-éleket a kör éleibe átvivő szimmetria.

Amikor n ≡ 2 (mod 4), M_n páros. Amikor n ≡ 0 (mod 4), nem páros. Az egyes létrafokok végpontjai ugyanis az eredeti körben páros távolságra vannak, minden újabb létrafok hozzáadása egy-egy páratlan kört hoz létre. Ebben az esetben, mivel a gráf 3-reguláris, de nem páros, a Brooks-tétel következményeként kromatikus száma 3. (De Mier & Noy 2004) megmutatta, hogy a Möbius-létrákat Tutte-polinomjuk egyedileg meghatározza.

Az M₈ Möbius-létrának 392 feszítőfája van; ennek és az M₆-nak van a legtöbb feszítőfája az ugyanannyi csúccsal rendelkező 3-reguláris gráfok közül. A legtöbb feszítőfával rendelkező 10 csúcsú 3-reguláris gráf azonban nem egy Möbius-létra, hanem a Petersen-gráf.

A Möbius-létrák Tutte-polinomjai egyszerű rekurzióval kiszámíthatók.

Gráfminorok

Az M₈ Wagner-gráf

A Möbius-létrák fontos szerepet játszanak a gráfminorok elméletében. Az első ilyen jellegű eredmény Klaus Wagner (1937) tétele volt, miszerint a K₅ minor nélküli gráfok előállíthatók a síkbarajzolható gráfokból és az M₈ Möbius-létrából a klikk-összeg művelet segítségével; emiatt az M₈-at Wagner-gráfnak nevezik.

(Gubser 1996) definíciója szerint a csaknem síkbarajzolható gráf (almost-planar graph) olyan nem síkbarajzolható gráf, aminek minden nemtrivális minora síkba rajzolható. Megmutatja, hogy a 3-szorosan összefüggő, csaknem síkbarajzolható gráfok közé a Möbius-létrák és még néhány gráfcsalád tartozik, és ezekből néhány egyszerű művelet segítségével elő lehet állítani a többi csaknem síkbarajzolható gráfot.

(Maharry 2000) megmutatta, hogy majdnem minden gráf, ami nem tartalmaz kocka minort előállítható Möbius-létrákból egyszerű műveletek segítségével.

Kémia és fizika

(Walba, Richards & Haltiwanger 1982) volt az első, aki Möbius-létra szerkezetet tartalmazó molekulákat állított elő, ez a szerkezet később nagyobb jelentőségre tett szert a kémiában és a kémiai sztereográfiában, különösen a DNS-molekulák létraszerű alakjára tekintettel. Ennek az alkalmazásnak figyelembe vételével Flapan (1989) tanulmányozza a Möbius-létrák R³-beli beágyazásainak matematikai szimmetriáit.

Egyes szupravezetéssel kapcsolatos kísérletekben a szupravezető gyűrűk topológiájaként kipróbálták a Möbius-létrákat is, hogy megvizsgálják a vezető topológiájának az elektronok közti interakciókra való hatását.

Kombinatorikus optimalizálás

A számítástudomány a halmazpakolási és lineáris rendezési feladatok egészértékű programozási megközelítéseiben használja a Möbius-létrákat. Ezen problémák egyes konfigurációi felhasználhatók a probléma lineáris programozási relaxációját leíró politóp lapjainak meghatározására; ezek a lapok a Möbius-létra korlátozások (Möbius ladder constraints).

Kapcsolódó szócikkek

• Létragráf
• Hasábgráf

Fordítás

• Ez a szócikk részben vagy egészben a Möbius ladder című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• (1972) „Recursive families of graphs”. Journal of Combinatorial Theory 12, 123–131. o. DOI:10.1016/0095-8956(72)90016-0. 
• (1999) „New facets of the linear ordering polytope”. SIAM Journal on Discrete Mathematics 12 (3), 326–336. o. DOI:10.1137/S0895480196300145. 
• (2000) „Set packing relaxations of some integer programs”. Mathematical Programming 88 (3), 425–450. o. DOI:10.1007/PL00011381. 
• (2002) „Period halving of persistent currents in mesoscopic Möbius ladders”. Chinese Physics Letters 19 (7), 988–991. o. DOI:10.1088/0256-307X/19/7/333. 
• Flapan, Erica (1989). „Symmetries of Möbius ladders”. Mathematische Annalen 283 (2), 271–283. o. DOI:10.1007/BF01446435. 
• (1985a) „On the acyclic subgraph polytope”. Mathematical Programming 33, 28–42. o. DOI:10.1007/BF01582009. 
• (1985b) „Facets of the linear ordering polytope”. Mathematical Programming 33, 43–60. o. DOI:10.1007/BF01582010. 
• Gubser, Bradley S. (1996). „A characterization of almost-planar graphs”. Combinatorics, Probability and Computing 5 (3), 227–245. o. DOI:10.1017/S0963548300002005. 
• (1967) „On the Möbius ladders”. Canadian Mathematical Bulletin 10, 493–496. o. DOI:10.4153/CMB-1967-046-4. 
• (1999) „On some extremal problems in graph theory”. 
• Li, De-ming (2005). „Genus distributions of Möbius ladders”. Northeastern Mathematics Journal 21 (1), 70–80. o. 
• Maharry, John (2000). „A characterization of graphs with no cube minor”. Journal of Combinatorial Theory 80 (2), 179–201. o. DOI:10.1006/jctb.2000.1968. 
• McSorley, John P. (1998). „Counting structures in the Möbius ladder”. Discrete Mathematics 184 (1–3), 137–164. o. DOI:10.1016/S0012-365X(97)00086-1. 
• (2004) „On graphs determined by their Tutte polynomials”. Graphs and Combinatorics 20 (1), 105–119. o. DOI:10.1007/s00373-003-0534-z. 
• (1998) „Persistent currents in a Möbius ladder: A test of interchain coherence of interacting electrons”. Physical Review B 57 (3), 1457–1460. o. DOI:10.1103/PhysRevB.57.1457. 
• (2001) „Fences are futile: on relaxations for the linear ordering problem”. Integer Programming and Combinatorial Optimization: 8th International IPCO Conference, Utrecht, The Netherlands, June 13–15, 2001, Proceedings 2081: 333–347, Berlin: Springer-Verlag. [2004. január 2-i dátummal az eredetiből archiválva]. doi:10.1007/3-540-45535-3_26. Hozzáférés: 2018. május 13. 
• Simon, Jonathan (1992). „Knots and chemistry”. New scientific applications of geometry and topology (Baltimore, MD, 1992) 45: 97–130, Providence, RI: American Mathematical Society. 
• Valdes, L. (1991). „Extremal properties of spanning trees in cubic graphs”. Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991) 85: 143–160. 
• Wagner, K. (1937). „Über eine Eigenschaft der ebenen Komplexe”. Mathematische Annalen 114, 570–590. o. DOI:10.1007/BF01594196. 
• (1982) „Total synthesis of the first molecular Möbius strip”. Journal of the American Chemical Society 104 (11), 3219–3221. o. DOI:10.1021/ja00375a051. 

További információk

• Weisstein, Eric W.: Möbius Ladder (angol nyelven). Wolfram MathWorld