نردبان موبیوس

دو نما از نردبان موبیوس M₁₆.

در حوزهٔ نظریه گراف، نردبان موبیوس Mnیک گراف دورانی مکعبی با تعداد رئوس زوج nاست، که از یک n-دور و چند یال

، تشکیل شده‌است. این گراف به این دلیل که دقیقاً n/2تا ۴-دور(McSorley 1998)دارد که به وسیله یال‌های مشترکشان به هم متصل اند و یک نوار موبیوس توپولوژیکی تشکیل می‌دهند، این گونه نام‌گذاری شده‌است. نردبان موبیوس اولین بار به وسیلهٔ Guy وHarary مورد مطالعه قرار گرفت و نام‌گذاری شد.

ویژگی‌ها

هر نردبان موبیوس غیر مسطح است. نردبان موبیوس دارای عدد تقاطع ۱ است، و می‌تواند در یک چنبره یا صفحهٔ مسطح جاسازی شود؛ بنابراین نردبان موبیوس نمونه‌ای از گراف‌های چنبره ای است. (Li(2005 قابلیت جاسازی آن‌ها را در سطوح دستهٔ بالاتر کشف کرد. نردبانهای موبیوس رأس-ترایا(vertex-transitive)(به استثناء (M6))هستند نه یال-ترایا(edge-transitive):هر رأس از دوری که نردبان از آن تشکیل شده‌است، مربوط به یک ۴-دور است، در حالی که هر پله مربوط به دو تا از این دورها است. وقتی (Mn, n ≡ 2 (mod ۴دو قسمتی است. وقتی (n ≡ 0 (mod ۴با توجه به قضیهٔ بروکس(Brooks' theorem)دارای عدد رنگی ۳ است. (De Mier, Noy (2005 نشان دادند که نردبان‌های موبیوس به وسیلهٔ تعدادحالات رنگ آمیزی با حد اقل رنگ(chromatic polynomials)مشخص می‌شوند. نردبان موبیوس M₈دارای ۳۹۲ درخت پوشا است، این گراف و گراف M₆بیشترین تعداد درختان پوشا را بین تمام گراف‌های مکعبی با تعداد رئوس مشابه، دارا هستند. (Jakobson and Rivin 1999; Valdes 1991)با این حال، گراف ۱۰ رأسی با بیشترین درخت پوشا، گراف پترسن است، که نردبان موبیوس نیست.

مینورهای گراف(Graph minors)

نردبان موبیوس نقش مهمی در نظریه مینورهای گراف بازی می‌کند. آخرین نتیجه از این دست، قضیه‌ای از Klaus Wagner در ۱۹۳۷ بود که گراف‌هایی که مینور K₅ندارند، می‌توانند با استفاده از عملیات clique-sumبرای ترکیب گراف‌های مسطح و نردبان موبیوسM₈ ساخته شوند؛ به همین دلیل M₈ گاهی گراف واگنر نامیده می‌شود.

(Gubser (1996)گراف تقریباً-مسطح را گرافی غیر مسطح که مینورهای مسطح دارد، تعریف کرد، او نشان داد که گرافهای ۳-همبند تقریباً-مسطح یا نردبان‌های موبیوس هستند یا عضو تعداد کمی از سایر انواع، و سایر گرافهای تقریباً-مسطح را می‌توان با انجام عملیات ساده روی این گرافها ساخت.

(Maharry (2001نشان داد که تقریباً تمام گراف‌هایی که مینور مکعب ندارند می‌توانند با استفاده از عملیات ساده از نردبان موبیوس مشتاق شوند.

شیمی و فیزیک

(Walba et al (1982 اولین بر ساختارهای ملکولی را به صورت نردبان موبیوس درآورد، و به همین دلیل این ساختار در شیمی و استریو گرافی شیمیایی (نشان دادن اجسام روی صفحه) مورد توجه قرار گرفته‌اند، به خصوص در مورد شکل نردبانی ملکولهای DNA. با توجه به این کاربرد، (Flapan (1989روی تقارن‌های ریاضی جاسازی نردبان‌های موبیوس درR³ مطالعه کرد. همچنین نردبانهای موبیوس به شکل یک حلقهٔ ابر رسانا در آزمایشهای مطالعهٔ تأثیرات توپولوژی رسانا روی برهم کنش‌های الکترونی مورد استفاده قرار گرفته‌اند. (Mila et al 1998; Deng et al 2002)

بهینه‌سازی ترکیبیاتی

نردبان‌های موبیوس همچنین در علوم کامپوتر به عنوان بخشی از برنامه‌نویسی صحیح مسائل بستن مجموعه (set packing) و مرتب‌سازی خطی(linear ordering) مورد استفاده قرار گرفته‌اند. پیکربندی معینی می‌تواند در این مسائل برای تعریف بندهای polytopeکه linear programming relaxationمسئله را تشریح می‌کنند، مورد استفاده قرار گیرد؛ این بندها محدودیتهای نردبان موبیوس خوانده می‌شوند(Bolotashvili et al 1999; Borndörfer and Weismantel 2000; Grötschel et al 1985a, 1985b; Newman and Vempala 2004).

منابع

• Wikipedia contributors, "Möbius ladder," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Möbius_ladder&oldid=336651303 (accessed February 7, 2010).
• Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen (به انگلیسی), vol. 114, p. 570–590 {{citation}}: External link in |شاپا= (help)
• Walba, D. ; Richards, R. ; Haltiwanger, R.C. (1982), "Total synthesis of the first molecular Möbius strip", Journal of the American Chemical Society (به انگلیسی), vol. 104, p. 3219–3221 {{citation}}: External link in |شاپا= (help)نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)

جستارهای وابسته

• نوار موبیوس