از ویکیپدیا، دانشنامه آزاد
یک نمودار مکعبی با 14 راس که روی یک چنبره تعبیه شده است
نمودار هیوود و نقشه مربوطه در چنبره تعبیه شده است.
در زمینه ریاضی نظریه گراف , گراف حلقوی گرافی است که می توان آن را روی چنبره تعبیه کرد . به عبارت دیگر، رئوس و یالهای گراف را میتوان روی یک چنبره قرار داد که هیچ یالی قطع نشود، مگر در رأسی که به هر دو تعلق دارد.
مثالها [ ویرایش ]
هر نموداری که بتوان در یک صفحه جاسازی کرد، می تواند در یک چنبره نیز جاسازی شود، بنابراین هر گراف مسطحی نیز یک گراف حلقوی است. یک گراف حلقوی که نمی تواند در یک صفحه جاسازی شود، دارای جنس 1 است.
گراف هیوود ، نمودار کامل K 7 (و از این رو K 5 و K 6 )، گراف پترسن (و از این رو نمودار دو بخشی کامل K 3,3 ، از آنجایی که گراف پترسن شامل زیربخشی از آن است)، یکی از بلانوشا snarks ، [1] و تمام نردبان های موبیوس حلقوی هستند. به طور کلی، هر نموداری با شماره 1 حلقوی است. برخی از نمودارها با اعداد متقاطع بزرگتر نیز حلقوی هستند: برای مثال، نمودار موبیوس-کانتور دارای تلاقی شماره 4 و حلقوی است. [2]
خواص [ ویرایش ]
هر گراف حلقوی حداکثر دارای عدد کروماتیک 7 است .
هر نمودار حلقوی بدون مثلث حداکثر دارای عدد رنگی 4 است. [5]
با نتیجه ای مشابه با قضیه فری ، هر گراف حلقوی را می توان با یال های مستقیم در یک مستطیل با شرایط مرزی تناوبی رسم کرد . [6] علاوه بر این، آنالوگ قضیه بهار توته در این مورد کاربرد دارد. [7] نمودارهای حلقوی همچنین دارای جاسازی کتاب با حداکثر 7 صفحه هستند. [8]
موانع [ ویرایش ]
بر اساس قضیه رابرتسون-سیمور ، یک مجموعه محدود H از گراف های غیر حلقوی حداقل وجود دارد ، به طوری که یک گراف حلقوی است اگر و فقط اگر گراف جزئی در H نداشته باشد . یعنی H مجموعه مینورهای ممنوعه را برای نمودارهای حلقوی تشکیل می دهد. مجموعه کامل H مشخص نیست، اما حداقل 17523 نمودار دارد. از طرف دیگر، حداقل 250815 نمودار غیر حلقوی وجود دارد که در ترتیب جزئی توپولوژیکی حداقل هستند . یک گراف حلقوی است اگر و فقط اگر هیچ یک از این نمودارها را به عنوان مینور توپولوژیکی نداشته باشد. [9]
گالری [ ویرایش ]
دو نمودار کیلی ایزومورف از گروه کواترنیون .
نمودار Cayley از گروه کواترنیون تعبیه شده در چنبره.
ویدئوی گراف کیلی از گروه کواترنیون تعبیه شده در چنبره.
نمودار پاپوس و نقشه مربوطه در چنبره تعبیه شده است.
همچنین ببینید [ ویرایش ]
یادداشت ها [ ویرایش ]
- ^ اوربانیچ و همکاران. (2004) .
- ↑ ماروسیچ و پیسانسکی (2000) .
- ↑ هیوود (1890) .
- ↑ چارتراند و ژانگ (2008) .
- ↑ کرونک و وایت (1972) .
- ↑ کوکای، نیلسون و شیپوفسکی (2001) .
- ↑ گورتلر، گوتسمن و ترستون (2006) .
- ^ اندو (1997) .
- ↑ Myrvold & Woodcock (2018) .
منابع [ ویرایش ]
- چارتراند، گری ؛ ژانگ، پینگ (2008)، نظریه گراف رنگی ، مطبوعات CRC، ISBN 978-1-58488-800-0.
- اندو، توشیکی (1997)، "تعداد صفحه نمودارهای حلقوی حداکثر هفت است"، ریاضیات گسسته ، 175 (1–3): 87–96، doi : 10.1016/S0012-365X(96)00144-6 ، MR 1475.
- گورتلر، استیون جی. گوتسمن، کریگ؛ Thurston، Dylan (2006)، "تک فرم های گسسته در مش ها و برنامه های کاربردی برای پارامترسازی مش سه بعدی" (PDF) ، طراحی هندسی به کمک کامپیوتر ، 23 (2): 83-112، doi : 10.1016/j.cagd.2005.05. , MR 2189438 , S2CID 135438.
- هیوود، پی جی (1890)، "قضیه های رنگ آمیزی نقشه"، فصلنامه ریاضیات ، سری اول، 24 : 322-339.
- کوکای، دبلیو. نیلسون، دی. Szypowski, R. (2001), "Drawing graphs on the torus" (PDF) , Ars Combinatoria , 59 : 259–277, MR 1832459 , بایگانی شده از نسخه اصلی (PDF) در 2004-12-24 , بازیابی شده در 2002-12-24 06.
- کرونک، هادسون وی. White, Arthur T. (1972)، "یک قضیه 4 رنگ برای نمودارهای حلقوی"، مجموعه مقالات انجمن ریاضی آمریکا ، انجمن ریاضی آمریکا، 34 (1): 83-86، doi : 10.2307/2037902 ، M37902 ، M37902 0291019 .
- ماروسیچ، دراگان ؛ پیسانسکی، توماز (2000)، "گراف پترسن تعمیم یافته قابل توجه G (8،3)"، ریاضی. Slovaca ، 50 : 117–121، CiteSeerX 10.1.1.28.7183 ، hdl : 10338.dmlcz/133137 ، MR 1763113 ، Zbl 0984.05044.
- میروولد، وندی ؛ وودکاک، جنیفر (2018)، "مجموعه بزرگی از انسدادهای چنبره و نحوه کشف آنها"، مجله الکترونیکی ترکیبیات ، 25 (1): P1.16، doi : 10.37236/3797
- نوفلد، یوجین؛ Myrvold، Wendy (1997)، "تست عملی toroidality" ، مجموعه مقالات هشتمین سمپوزیوم سالانه ACM-SIAM در الگوریتم های گسسته ، صفحات 574-580، ISBN 978-0-89871-390-9.
- اوربانیچ، آلن؛ پیسانسکی، توماز ؛ رندیچ، میلان ؛ Servatius، Brigitte (2004)، "Blanuša double" (PDF) ، ریاضی. اشتراک. , 9 (1): 91–103, CiteSeerX 10.1.1.361.2772.
https://en.wikipedia.org/wiki/Toroidal_graph
در این وبلاگ به ریاضیات و کاربردهای آن و تحقیقات در آنها پرداخته می شود. مطالب در این وبلاگ ترجمه سطحی و اولیه است و کامل نیست.در صورتی سوال یا نظری در زمینه ریاضیات دارید مطرح نمایید .در صورت امکان به آن می پردازم. من دوست دارم برای یافتن پاسخ به سوالات و حل پروژه های علمی با دیگران همکاری نمایم.در صورتی که شما هم بامن هم عقیده هستید با من تماس بگیرید.