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

 

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

در حوزهٔ نظریه گراف، نردبان موبیوس Mnیک گراف دورانی مکعبی با تعداد رئوس زوج nاست، که از یک n-دور و چند یال به نام پله(rungs)که جفت رئوس مخالف دور را به هم وصل می‌کنند، تشکیل شده است.این گراف به این دلیل که دقیقا n/2تا 4-دور(McSorley 1998)دارد که به وسیله یال‌های مشترکشان به هم متصل اند و یک نوار موبیوس توپولوژیکی تشکیل می‌دهند، این گونه نام گذاری شده است.نردبان موبیوس اولین بار به وسیلهٔ Guy وHarary مورد مطالعه قرار گرفت و نام گذاری شد.اگر علاقمند هستید ادامه مطلب را بخوانید........

محتویات ۱ ویژگی‌ها ۲ مینورهای گراف(Graph minors) ۳ شیمی و فیزیک ۴ بهینه سازی ترکیبیاتی ۵ منابع ۶ جستارهای وابسته

ویژگی‌ها

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

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

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

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

(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%C3%B6bius_ladder&oldid=336651303 (accessed February 7, 2010).

• Wagner, K.. “Über eine Eigenschaft der ebenen Komplexe”. Mathematische Annalen. 1937.114, doi: 10.1007/BF01594196, ‏570–590.

• Walba, D.; Richards, R.; Haltiwanger, R.C.. “Total synthesis of the first molecular Möbius strip”. Journal of the American Chemical Society. 1982.104, doi: 10.1021/ja00375a051, ‏3219–3221.