گراف پترسن یک گراف مکعب است.

گراف کامل دوبخشی {\ displaystyle K_ {3،3}}K_ {3،3} نمونه ای از نمودار دو مکعبی است

در ریاضی زمینه نظریه گراف ، یک گراف مکعبی است نمودار که در آن همه رئوس دارند درجه سه. به عبارت دیگر ، یک نمودار مکعبی یک نمودار 3- منظم است . نمودارهای مکعبی را نمودارهای سه ظرفیتی نیز می نامند .

نمودار دو مکعبی مکعب است گراف دو بخشی .

 

فهرست

تقارن [ ویرایش ]

در سال 1932 ، رونالد ام. فوستر شروع به جمع آوری نمونه هایی از نمودارهای متقارن مکعبی کرد و شروع سرشماری فاستر را تشکیل داد . [1] بسیاری از نمودارهای شناخته شده فردی مکعبی و متقارن هستند ، از جمله نمودار سودمندی ، نمودار پترسن ، نمودار Heawood ، نمودار Möbius – Kantor ، نمودار Pappus ، نمودار Desargues ، نمودار Nauru ، نمودار Coxeter ، نمودار نمودار Tutte – Coxeter ، نمودار Dyck ، نمودار Foster و نمودار Biggs-Smith. WT Tutte نمودارهای مکعب متقارن را بر اساس کوچکترین عدد صحیح s طبقه بندی کرده است به طوری که هر دو مسیر جهت دار از طول s را می توان دقیقاً با یک تقارن نمودار برای یکدیگر ترسیم کرد. او نشان داد که s حداکثر 5 است ، و نمونه هایی از نمودارها را با هر مقدار ممکن از s از 1 تا 5 ارائه داد. [2]

نمودارهای مکعب نیمه متقارن شامل نمودار خاکستری (کوچکترین نمودار مکعبی نیمه متقارن) ، نمودار لیوبلیانا و 12 قفس Tutte است .

نمودار Frucht یکی از پنج کوچکترین گرافهای مکعبی بدون هیچ تقارن است: [3] آن را دارای تنها یک های automorphism نمودار ، های automorphism هویت. [4]

مجموعه های رنگ آمیزی و مستقل [ ویرایش ]

با توجه به بروکس 'قضیه هر گراف مکعب متصل به غیر از گراف کامل K 4 می توان رنگی با حداکثر سه رنگ. بنابراین ، هر نمودار مکعبی متصل به غیر از K 4 دارای یک مجموعه مستقل از حداقل n / 3 رئوس است ، جایی که n تعداد رئوس نمودار است: به عنوان مثال ، بزرگترین کلاس رنگ در 3 رنگ حداقل این تعداد را دارد رگه ها.

طبق قضیه ویزینگ ، هر نمودار مکعبی برای رنگ آمیزی لبه به سه یا چهار رنگ نیاز دارد. رنگ آمیزی 3 لبه به عنوان رنگ آمیزی Tait شناخته می شود و پارتیشن لبه های نمودار را به سه تطابق کامل تبدیل می کند . با توجه به قضیه رنگ آمیزی Kőnig ، هر نمودار دو مکعبی دارای یک رنگ آمیزی Tait است.

نمودارهای مکعبی بدون پل که رنگ Tait ندارند به عنوان snark شناخته می شوند . آنها شامل نمودار Petersen ، نمودار Tietze ، snacks Blanuša ، snark flower ، snark دو ستاره ، snark Szekeres و snark Watkins هستند . تعداد نامحدود اسنارهای مشخص وجود دارد. [5]

توپولوژی و هندسه [ ویرایش ]

نمودارهای مکعبی به طور طبیعی در توپولوژی به چندین روش به وجود می آیند . به عنوان مثال ، اگر کسی یک نمودار را یک مجموعه CW 1 بعدی در نظر بگیرد ، نمودارهای مکعبی عمومی هستند زیرا بیشتر نقشه های پیوست 1 سلولی از اسکلت 0 نمودار جدا نیستند. نمودارهای مکعبی نیز به صورت نمودارهای چند وجهی ساده در سه بعد ، چند وجهی مانند دوازده ضلعی معمولی با خاصیتی که سه چهره در هر راس با هم ملاقات می کنند ، تشکیل می شوند.

نمایش تعبیه مسطح به عنوان یک نقشه رمزگذاری شده با نمودار

تعبیه گراف دلخواه بر روی یک سطح دو بعدی ممکن است به عنوان یک ساختار گرافیکی مکعبی شناخته شود که به عنوان نقشه رمزگذاری شده با نمودار شناخته می شود . در این ساختار ، هر راس از یک نمودار مکعب نشان دهنده یک پرچم تعبیه شده است ، یک سه گانه متقابل از یک راس ، لبه و صورت سطح. سه همسایه هر پرچم ، سه پرچمی هستند که ممکن است با تغییر سه گانه یکی از اعضای این حادثه متقابل و بدون تغییر دو عضو دیگر ، از آن به دست بیایند. [6]

همیلتونی [ ویرایش ]

تحقیقات زیادی در مورد همیلتون بودن نمودارهای مکعبی انجام شده است. در سال 1880 ، PG Tait حدس زد که هر نمودار چند وجهی مکعبی دارای مدار همیلتونین است . ویلیام توماس توته یک مثال مخالف برای حدس طایت ، نمودار 46 راس توت ، در سال 1946 ارائه داد. در سال 1971 ، توت حدس زد که همه نمودارهای دو مکعبی همیلتونی هستند. با این حال ، جوزف هورتون نمونه ای نمونه بر روی 96 راس ، نمودار هورتون ، ارائه داده است . [7] بعداً ، مارک الینگهام دو مثال دیگر ساخت: نمودارهای الینگام - هورتون . [8] [9] حدس بارنت ، ترکیبی کاملاً باز از حدس طایت و توت ، بیان می کند که هر نمودار چند وجهی دو مکعبی همیلتونی است. هنگامی که یک نمودار مکعبی همیلتونی است ، علامت گذاری LCF اجازه می دهد تا به طور خلاصه نشان داده شود.

اگر یک نمودار مکعبی به طور تصادفی از بین تمام نمودارهای مکعبی n- وارنس انتخاب شود ، به احتمال زیاد همیلتونی است: نسبت نمودارهای مکعبی n -vertex که هامیلتونی هستند ، در حالی که n به بی نهایت می رود ، به یک حد تمایل دارد . [10]

دیوید اپستین حدس زد که هر نمودار مکعب n- وورتکس دارای حداکثر 2 n / 3 (تقریباً 1.260 n ) چرخه مشخص هامیلتونی است و نمونه هایی از نمودارهای مکعبی با این تعداد چرخه ارائه داده است. [11] بهترین برآورد اثبات شده برای تعداد چرخه های مشخص هامیلتونی است{\ displaystyle O ({1.276} ^ {n})}O ({1.276} ^ {n}). [12]

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

مسئله حل نشده در ریاضیات :

بزرگترین مسیر ممکن یک{\ displaystyle n}nنمودار مکعب -ترکس؟

(مشکلات حل نشده بیشتر در ریاضیات)

طول مسیر هر نمودار مکعبی n- وورتکس حداکثر n / 6 است. بهترین شناخته شده پایین ترین حد در مسیر نمودارهای مکعبی 0.082 n است . مشخص نیست که چگونه می توان این شکاف بین این حد پایین و مرز n / 6 بالا را کاهش داد. [13]

از لمس دست دادن ، که توسط لئونارد اویلر در سال 1736 به عنوان بخشی از اولین مقاله در مورد تئوری نمودار ثابت شد ، نتیجه می شود که هر نمودار مکعبی تعداد راس های مساوی دارد.

قضیه پیترسن بیان می کند که هر نمودار مکعبی بدون پل مکعب مطابقت کاملی دارد . [14] لواسز و پلامر حدس زدند که هر نمودار مکعبی بدون پل دارای تعداد تصاویری از تطابق کامل است. حدس اخیراً اثبات شده است ، نشان می دهد که هر نمودار مکعبی بدون پل با n راس دارای حداقل 2 n / 3656 مطابقت کامل است. [15]

الگوریتم ها و پیچیدگی ها [ ویرایش ]

چندین محقق پیچیدگی الگوریتم های زمانی نمایی محدود به نمودارهای مکعبی را مطالعه کرده اند . به عنوان مثال ، با استفاده از برنامه ریزی پویا برای تجزیه مسیر نمودار ، Fomin و Høie نشان دادند که چگونه می توانند حداکثر مجموعه های مستقل خود را در زمان 2 n / 6 + o ( n ) پیدا کنند . [13] مسئله فروشنده دوره گرد در گرافهای مکعبی می تواند در زمان O (1.2312 حل N ) و فضای چند جمله ای. [16] [17]

چندین مسئله مهم بهینه سازی نمودار APX سخت است ، به این معنی که ، اگرچه آنها الگوریتم های تقریب دارند که نسبت تقریبی آنها با یک ثابت محدود می شود ، آنها دارای طرح های تقریب زمان چند جمله ای نیستند که نسبت تقریبی آنها به 1 گرایش داشته باشد مگر اینکه P = NP . اینها شامل مشکلات یافتن حداقل پوشش راس ، حداکثر مجموعه مستقل ، حداقل مجموعه غالب و حداکثر برش است . [18] تعداد تقاطع (تعداد حداقل از لبه که در هر عبور رسم ) از یک گراف مکعب است NP-hard استبرای نمودارهای مکعبی اما ممکن است تقریبی باشد. [19] فروشنده دوره گرد مشکل در نمودار مکعب ثابت شده است به NP-hard است برای تقریب به درون هر عامل کمتر از 1153/1152. [20]

منبع

https://en.wikipedia.org/wiki/Cubic_graph