از ویکیپدیا، دانشنامه آزاد

نردبان موبیوس
دو نما از نردبان موبیوس M 16 . برای نمایش انیمیشنی که تبدیل بین دو نما را نشان می دهد، به این فایل مراجعه کنید .
رگه ها	n (عدد زوج)
لبه ها	n +n/2
بند	4 (برای زوج n > 4 )
عدد کروماتیک	3
شاخص رنگی	3
جنس	1 (برای زوج n > 4 )
خواص	راس چرخشی مکعبی - گذرا (برای زوج n > 4 ) حلقوی (برای زوج n > 4 ) گذرا لبه (برای n = 4، 6 ) دوبخشی (برای n غیر مضاعف زوج )
نشانه گذاری	M n
جدول نمودارها و پارامترها

در تئوری گراف ، نردبان موبیوس M n ، برای اعداد زوج n ، از یک چرخه n با افزودن یال ها (به نام "پله ها") که جفت های متضاد رئوس را در چرخه به هم متصل می کنند ، تشکیل می شود . این یک گراف مکعبی و چرخشی است که به این دلیل نامیده می شود (به استثنای M 6 ( گراف مفید K 3,3 )، M n دقیقاً n / 2 چهار چرخه [1] دارد که توسط یال های مشترکشان به یکدیگر متصل می شوند. یک نوار موبیوس توپولوژیکی را تشکیل می دهد . نردبان های موبیوس برای اولین بار توسط گای و هری ( 1967 ) نامگذاری و مورد مطالعه قرار گرفتند .

خواص [ ویرایش ]

برای هر n > 4 زوج ، نردبان موبیوس Mn یک گراف راس غیرمسطح است، به این معنی که نمی توان آن را بدون تلاقی در صفحه رسم کرد، اما حذف یک راس به گراف باقی مانده اجازه می دهد تا بدون تلاقی رسم شود. این نمودارها دارای تقاطع شماره یک هستند و می‌توان آنها را بدون گذر بر روی یک چنبره یا صفحه نمایشی جاسازی کرد . بنابراین، آنها نمونه هایی از نمودارهای حلقوی هستند . لی (2005) تعبیه‌های این نمودارها را در سطوح بالاتر جنس بررسی می‌کند.

نردبان های موبیوس رأس گذرا هستند - آنها دارای تقارن هایی هستند که هر راس را به هر راس دیگری می برد - اما (به استثنای M 4 و M 6 ) آنها گذرا به لبه نیستند . لبه‌های چرخه‌ای که از آن نردبان تشکیل می‌شود را می‌توان از پله‌های نردبان تشخیص داد، زیرا هر لبه چرخه متعلق به یک 4 چرخه است، در حالی که هر پله متعلق به دو چرخه است. بنابراین، هیچ تقارنی وجود ندارد که یک لبه چرخه به یک لبه پله یا برعکس برسد.

وقتی n ≡ 2 (mod 4) ، M n دو بخشی است . وقتی n ≡ 0 (mod 4) , دوبخشی نیست. نقاط انتهایی هر پله در چرخه اولیه فاصله زوجی دارند، بنابراین اضافه کردن هر پله یک چرخه فرد ایجاد می کند. در این مورد، از آنجایی که نمودار 3-منظم است اما دو بخشی نیست، طبق قضیه بروکس دارای عدد رنگی 3 است . De Mier & Noy (2004) نشان می دهد که نردبان موبیوس به طور منحصر به فردی توسط چند جمله ای های Tutte آنها تعیین می شوند .

نردبان Möbius M 8 دارای 392 درخت پوشا است . آن و M 6 دارای بیشترین درختان پوشا در بین تمام نمودارهای مکعبی با تعداد رئوس یکسان هستند. [2] با این حال، نمودار مکعبی 10 رأس با بیشترین درختان پوشا، نمودار پترسن است که یک نردبان موبیوس نیست.

چند جمله ای های Tutte نردبان های موبیوس را می توان با یک رابطه بازگشتی ساده محاسبه کرد . [3]

نمودارهای خردسال [ ویرایش ]

نمودار واگنر M 8

نردبان موبیوس نقش مهمی در تئوری مینورهای گراف دارند . اولین نتیجه از این نوع قضیه کلاوس واگنر ( 1937 ) است که نمودارهایی بدون K 5 جزئی را می توان با استفاده از عملیات جمع-کلویه برای ترکیب نمودارهای مسطح و نردبان موبیوس M 8 تشکیل داد . به همین دلیل M 8 را گراف واگنر می نامند .

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

ماهاری (2000) نشان می دهد که تقریباً تمام نمودارهایی که مینور مکعب ندارند را می توان با دنباله ای از عملیات ساده از نردبان موبیوس استخراج کرد.

شیمی و فیزیک [ ویرایش ]

والبا، ریچاردز و هالتیوانگر (1982) برای اولین بار ساختارهای مولکولی را به شکل نردبان موبیوس سنتز کردند و از آن زمان این ساختار در شیمی و استریوگرافی شیمیایی مورد توجه قرار گرفت، [4] به ویژه با توجه به شکل نردبان مانند مولکول های DNA. . با در نظر گرفتن این کاربرد، Flapan ( 1989 ) تقارن های ریاضی تعبیه نردبان های موبیوس در R3 را مطالعه می کند . به طور خاص، همانطور که او نشان می دهد، هر تعبیه سه بعدی نردبان موبیوس با تعداد پله های فرد از نظر توپولوژیکی کایرال است : با تغییر شکل مداوم فضا بدون عبور از یک یال از لبه دیگر نمی توان آن را به تصویر آینه ای خود تبدیل کرد. از سوی دیگر، نردبان‌های موبیوس با تعداد پله‌های زوج همگی دارای تعبیه‌هایی در R3 هستند که می‌توانند به تصاویر آینه‌ای خود تغییر شکل دهند .

نردبان موبیوس همچنین به عنوان شکل یک حلقه ابررسانا در آزمایش‌ها برای مطالعه اثرات توپولوژی رسانا بر برهمکنش‌های الکترون استفاده شده است. [5]

بهینه سازی ترکیبی [ ویرایش ]

نردبان های موبیوس نیز در علوم کامپیوتر به عنوان بخشی از رویکردهای برنامه نویسی عدد صحیح برای مشکلات بسته بندی مجموعه و ترتیب خطی استفاده شده است . پیکربندی‌های خاصی در این مسائل می‌تواند برای تعریف جنبه‌های پلی‌توپ که برنامه‌ریزی خطی مشکل را توصیف می‌کند ، استفاده شود. این وجوه را محدودیت های نردبان موبیوس می نامند. [6]

همچنین ببینید [ ویرایش ]

• نمودار نردبانی
• نمودار منشوری

یادداشت ها [ ویرایش ]

1. ^ مک سورلی (1998) .
2. ^ جاکوبسون و ریوین (1999) ؛ والدز (1991) .
3. ↑ بیگز، دامرل و ساندز (1972) .
4. ^ سیمون (1992) .
5. ↑ میلا، استافورد و کاپونی (1998) ؛ دنگ، زو و لیو (2002) .
6. ↑ بولوتاشویلی، کووالف و گرلیچ (1999) ؛ Borndörfer & Weismantel (2000) ; گروتشل، یونگر، و راینلت ( 1985a ، 1985b ); نیومن و ومپالا (2001)

منابع [ ویرایش ]

• بیگز، NL ; دامرل، آر.ام. سندز، DA (1972). "خانواده های بازگشتی نمودارها" . مجله تئوری ترکیبی . سری B. 12 (2): 123-131. doi : 10.1016/0095-8956(72)90016-0 . MR 0294172 .
• بولوتاشویلی، جی. کووالف، م. Girlich، E. (1999). "جنبه های جدید پلی توپ مرتب سازی خطی". مجله SIAM در ریاضیات گسسته . 12 (3): 326-336. CiteSeerX 10.1.1.41.8722 . doi : 10.1137/S0895480196300145 . MR 1710240 .
• بورندورفر، رالف؛ ویزمانتل، رابرت (2000). "تنظیم آرامش های بسته بندی برخی از برنامه های عدد صحیح". برنامه نویسی ریاضی . سری A. 88 (3): 425–450. doi : 10.1007/PL00011381 . MR 1782150 . S2CID 206862305 .
• دنگ، ون جی. خو، جی هوان؛ لیو، پینگ (2002). "نصف دوره ای جریان های پایدار در نردبان های مزوسکوپی موبیوس". حروف فیزیک چینی 19 (7): 988-991. arXiv : cond-mat/0209421 . Bibcode : 2002ChPhL..19..988D . doi : 10.1088/0256-307X/19/7/333 . S2CID 119421223 .
• فلاپان، اریکا (1989). "تقارن نردبان موبیوس". Matheatische Annalen . 283 (2): 271-283. doi : 10.1007/BF01446435 . MR 0980598 . S2CID 119705062 .
• گروتشل، ام . یونگر، ام. Reinelt، G. (1985a). "روی پلی توپ زیرگراف غیر حلقوی". برنامه نویسی ریاضی . 33 : 28-42. doi : 10.1007/BF01582009 . MR 0809747 . S2CID 206798683 .
• گروتشل، ام. یونگر، ام. Reinelt، G. (1985b). "وجوه چند توپی نظم دهنده خطی". برنامه نویسی ریاضی . 33 : 43-60. doi : 10.1007/BF01582010 . MR 0809748 . S2CID 21071064 .
• گوبسر، بردلی اس (1996). "مشخصات نمودارهای تقریباً مسطح". ترکیبات، احتمال و محاسبات . 5 (3): 227-245. doi : 10.1017/S0963548300002005 . MR 1411084 . S2CID 7313209 .
• گای، ریچارد ک . هری، فرانک (1967). "روی نردبان موبیوس" . بولتن ریاضی کانادا 10 (4): 493-496. doi : 10.4153/CMB-1967-046-4 . MR 0224499 .
• یاکوبسون، دیمیتری؛ ریوین، ایگور (1999). "درباره برخی مشکلات افراطی در نظریه گراف" . arXiv : math.CO/9907050 . {{cite journal}}: مجله استناد نیاز دارد |journal=( کمک )
• لی، دی مینگ (2005). "توزیع جنس نردبان موبیوس". مجله ریاضی شمال شرق . 21 (1): 70-80. MR 2124859 .
• ماهاری، جان (2000). "مشخصات نمودارها بدون کوچکترین مکعب" . مجله تئوری ترکیبی . سری B. 80 (2): 179–201. doi : 10.1006/jctb.2000.1968 . MR 1794690 .
• مک سورلی، جان پی (1998). "شمارش سازه ها در نردبان موبیوس" . ریاضیات گسسته . 184 (1-3): 137-164. doi : 10.1016/S0012-365X(97)00086-1 . MR 1609294 .
• دی میر، آنا؛ نوی، مارک (2004). "روی نمودارهایی که توسط چند جمله ای های توت تعیین می شوند". نمودارها و ترکیبات . 20 (1): 105-119. doi : 10.1007/s00373-003-0534-z . MR 2048553 . S2CID 46312268 .
• میلا، فردریک؛ استافورد، کالیفرنیا؛ کاپونی، سیلوین (1998). "جریان های پایدار در یک نردبان موبیوس: آزمایش انسجام بین زنجیره ای الکترون های برهم کنش" (PDF) . بررسی فیزیکی B. 57 (3): 1457-1460. arXiv : cond-mat/9705119 . Bibcode : 1998PhRvB..57.1457M . doi : 10.1103/PhysRevB.57.1457 . S2CID 35931632 .
• نیومن، آلانتا؛ ومپالا، سانتوش (2001). "حصارها بیهوده هستند: در مورد آرامش برای مسئله نظم دهی خطی" . برنامه نویسی عدد صحیح و بهینه سازی ترکیبی: هشتمین کنفرانس بین المللی IPCO، اوترخت، هلند، 13 تا 15 ژوئن 2001، مجموعه مقالات . نکات سخنرانی در علوم کامپیوتر. جلد 2081. برلین: Springer-Verlag. صص 333-347. doi : 10.1007/3-540-45535-3_26 . MR 2041937 . بایگانی شده از نسخه اصلی در 2004-01-02 . بازیابی شده در 2006-10-08 .
• سیمون، جاناتان (1992). "گره ها و شیمی". کاربردهای علمی جدید هندسه و توپولوژی (بالتیمور، MD، 1992) . مجموعه مقالات سمپوزیوم در ریاضیات کاربردی. جلد 45. Providence, RI: American Mathematical Society . صص 97-130. MR 1196717 .
• والدز، ال (1991). "خواص افراطی درختان پوشا در نمودارهای مکعبی". مجموعه مقالات بیست و دومین کنفرانس جنوب شرقی در مورد ترکیبات، نظریه گراف و محاسبات (باتن روژ، لس آنجلس، 1991) . کنگره Numerantium. جلد 85. صص 143-160. MR 1152127 .
• واگنر، ک. (1937). "Über eine Eigenschaft der ebenen Komplexe". Matheatische Annalen . 114 : 570–590. doi : 10.1007/BF01594196 . MR 1513158 . S2CID 123534907 .
• والبا، دی. ریچاردز، آر. Haltiwanger، RC (1982). "سنتز کلی اولین نوار موبیوس مولکولی". مجله انجمن شیمی آمریکا . 104 (11): 3219-3221. doi : 10.1021/ja00375a051 .

پیوندهای خارجی [ ویرایش ]

• وایستاین، اریک دبلیو. "نردبان موبیوس" . دنیای ریاضی .

دسته بندی ها :

• خانواده پارامتری نمودارها
• نمودارهای منظم

https://en.wikipedia.org/wiki/M%C3%B6bius_ladder