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

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

دو نما از نردبان موبیوس M16.

ویژگی‌ها

هر نردبان موبیوس غیر مسطح است.نردبان موبیوس دارای عدد تقاطع 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)مشخص می‌شوند. نردبان موبیوس M8دارای 392 درخت پوشا است، این گراف و گراف M6بیشترین تعداد درختان پوشا را بین تمام گراف‌های مکعبی با تعداد رئوس مشابه، دارا هستند.(Jakobson and Rivin 1999; Valdes 1991)با این حال، گراف 10 رأسی با بیشترین درخت پوشا، گراف پترسن است، که نردبان موبیوس نیست.

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

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

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

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

شیمی و فیزیک

(Walba et al (1982 اولین بر ساختارهای ملکولی را به صورت نردبان موبیوس در آورد، و به همین دلیل این ساختار در شیمی و استریو گرافی شیمیای(نشان دادن اجسام روی صفحه)مورد توجه قرار گرفته اند، به خصوص در مورد شکل نردبانی ملکولهای DNA.با توجه به این کاربرد،(Flapan (1989روی تقارن‌های ریاضی جاسازی نردبان‌های موبیوس درR3 مطالعه کرد. همچنین نردبانهای موبیوس به شکل یک حلقهٔ ابر رسانا در آزمایشهای مطالعهٔ تأثیرات توپولوژی رسانا روی بر هم کنش‌های الکترونی مورد استفاده قرار گرفته‌اند.(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. (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen, 114, p. 570–590, ISSN doi: [http://dx.doi.org/10.1007%2FBF01594196 10.1007/BF01594196 [[Digital object identifier|doi]]: <span class="neverexpand">[http://dx.doi.org/10.1007%2FBF01594196 '"`UNIQ--nowiki-00000001-QINU`"']</span>] Check |issn= value (help)
    • Walba, D.; Richards, R.; Haltiwanger, R.C. (1982), "Total synthesis of the first molecular Möbius strip", Journal of the American Chemical Society, 104, p. 3219–3221, ISSN doi: [http://dx.doi.org/10.1021%2Fja00375a051 10.1021/ja00375a051 [[Digital object identifier|doi]]: <span class="neverexpand">[http://dx.doi.org/10.1021%2Fja00375a051 '"`UNIQ--nowiki-00000005-QINU`"']</span>] Check |issn= value (help)

    جستارهای وابسته
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.