گراف مکعب

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

همچنین یک گراف دو مکعبی یک گراف دو بخشی میباشد

The Petersen graph is a Cubic graph.

The complete bipartite graph $K_{3,3}$ is an example of a bicubic graph

تقارن

در سال 1932 Ronald M. Foster به دنبال جمع آوری گراف های مکعبی متقارن بود

نمونه هایی از گراف های مکعبی میتوان به : utility graph, Petersen graph, Heawood graph, Möbius–Kantor graph, the Pappus graph, Desargues graph, Nauru graph, Coxeter graph, Tutte–Coxeter graph, Dyck graph, Foster graph ,Biggs-Smith graph. W. T. Tutte که به عنوان دسته از گراف های مکعبی به شمار می آیند.

گراف های مکعبی نیمه متقارن شامل گراف های Gray graph ( که کوچکترین گراف مکعبی متقارن است ), Ljubljana graph و Tutte 12-cage میباشد .

Frucht graph یکی از دو گراف مکعبی متقارن میباشد . که این گراف شامل یک graph automorphismکه باعث شده هویت گراف های اتو مورفیسم را داشته باشد.

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

براساس تئوری بروکس هر گراف مکعبی همبند به جز دسته ی گراف های کامل K₄ میتواند با حداقل 3 رنگ رنگ آمیزی شود . پس هر گراف مکعبی همبند به جز گراف K₄ دارای یک مجموعه مستقل از حداقل n/3 راس ها میباشد که درواقع n تعداد راس های گراف هستند . به طور مثال بزرگترین کلاس رنگ 3 تایی دست کم این تعداد راس را دارا میباشند.

براساس تئوری ویزینگ هر گراف مکعبی نیازمند 3 یا 4 رنگ برای رنگ آمیزی یال ها میباشد . گراف هایی که نیازمند 3 رنگ برای رنگ آمیزی یال های آن هستیم به رنگ آمیزی تیت (tait) معروف هستند . حال براساس تئوری کونیگ هر گراف دوبخشی دارای رنگ آمیزی تیت میباشد .

گراف های کم یال مکعبی که رنگ آمیزی تیت را ندارند به نام اسنارک شناخته میشوند . به طور مثال میتوان به گراف پترسن , Blanuša snarks, flower snark, double-star snark, Szekeres snark وWatkins snark.تعداد نامحدودی از گراف های اسنارک موجود میباشد .

توپولوژی و هندسه

گراف های مکعبی به صورت طبینی در توپولوژِ در راه های مختلفی بوجود می آیند .به طور مثال اگر یک نفر تصمیم بگیرد یک گراف که یک بعدی باشد بسازد به راحتی میتواند این کار را انجام دهد .

قابلیت همیلتونی

تحقیقات زیادی بر بروی همیلتونی بودن گراف های مکعبی میباشد . در سال 1880 P.G. Tait حدس زد که هر گراف مکعبی پلی هدرال یک دور همیلتونی دارد . William Thomas Tutte مثال های زیادی برای رنگ امیزی با روش تیت و حدس های زده شده توسط پیتر زد.

گراف تیوت با 46 راس در سال 1946 و در 1971 تیوت حدس زد که تمام گراف های دوبخشی مکعبی همیلتونی هستند درصورتی که جوزف هورتون یک مثال با 96 راس زد .

بعدا Mark Ellingham دو مثال مانند هورتون پیدا کرد  : Ellingham-Horton graphs. Barnette's conjecture که این موارد ترکیبی از حدس های تیت و تیوت هستند که نشان میدهد هر گراف دو بخشی مکعبی پلی هدرال همیلتونی میباشد .
حال اگر یک گراف مکعبی به صورت رندوم انتخاب شود از بین n راس گراف های مکعبی آنگاه احتمال بسیار زیادی دارد که همیلتونی باشد : درواقع حد تعداد راس های گراف که n فرض شده اند از یک به بینهایت که به صورت زیر نمایش میدهیم : lim n و n به بینهایت میل میکند .
David Eppsteinحدس زد که هر گراف مکعبی با n راس دارای دست کم 2^n/3 مسیر همیلتونی هستند . و فراهم میکند مثال گراف های مکعبی با همون تعداد زیاد مسیر . که حال بیگ O این مقدار $O({1.276}^{n})$. میباشد.

خواص دیگر

طول مسیر تمام گراف هایی با n راس از سری گراف های مکعبی دست کم n/6 میباشد . درصورتی که بیشترین کران پایین طول مسیر گراف های مکعبی کمتر از 0.082n.
توسط handshaking lemma که توسط لئونارد اویلر اثبات شده است در سال 1736 به عوان قسمتی از صفحه اول دفتر ئوری گراف نوشته شده است که هر گراف مکعبی که تمام گراف های مکعبی دارای تعداد زوج راس میباشند.
تئوری پترسن نشان میدهد که همه ی گراف های مکعبی که دارای یال برشی هستند یک گراف با قابلیت matching هستند .
Lovász و Plummer حدس زندند که تمام گراف های مکعبی با یال برشی یک تعداد مشخص به صورتی نمایی از قابلیت perfect matching را دارا میباشند . آن امروزه اثبات شده است و نشان داده شده است که تمام گراف های مکعبی دارای یال برشی با دست کم n راس تعداد ^n/3656 قابلیت perfect matchings میباشند .

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

تحقیقات و مطالعات زیادی انجام شده درباره ی پیچیدگی زمان انجام یک الگوریتم که به گراف های مکعبی محدود شده اند . به طور مثال با ایجاد یک برنامه داینامیک برای تجزیه مسیر ( یا تفسیر مسیر ) گراف . قومین و هویه نشان دادند که چگونه مجموعه های مستقل آن هارو با زمانی که بیگ O آن (2^n/6 + o(n)) است پیدا کرد. حال مسئله پیر مرد دست فروش ما با سرعت (1.2312ⁿ) قابل حل میباشد .

تعداد زیاد مهمی از الگوریتم هایی برای بهینه کردن مشکلات گرافی وجود دارد که APX hard میباشند . که به معنی این میباش که برای آن ها الگوریتم های برای تقریب این مقدار وجود دارد که توسط یک مقدار دارای کران شده اند و آن ها دارای polynomial time approximation scheme که رشد آن ها به کمتر یک میباشد ندارند .
این مشکلات شامل پیدا کردن حداقل پوشش راس و بیشترین مجموعه مستقل و حداقل مجموعه های مربوطه و بیشترین برش میباشد هستند.
حال عدد گذرش ( که حداقل تعداد یال هایی میباشد که میتوان در یک گرافذ گذر کرد ) گراف های مکعبی یک NP-hardمیباشد که برای گراف های مکعبی ممکن است تقریب زده شده باشد . The Travelling Salesman Problem on cubic graphs has been proven to be NP-hard to approximate to within any factor less than 1153/1152.

اطلاعات بیشتر و مطالب مشابه

• Table of simple cubic graphs

لینک های خارجی

• Royle, Gordon. "Cubic symmetric graphs (The Foster Census)".
• Weisstein, Eric W. "Bicubic Graph". MathWorld.
• Weisstein, Eric W. "Cubic Graph". MathWorld.