گراف مکعب

در علم ریاضی گراف مکعبی، گرافی است که تمام رأس‌های آن دارای درجهٔ ۳ باشد یا به زبان دیگر می‌توان گفت گراف مکعبی یک گراف ۳-منتظم است.

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

The گراف پترسن is a Cubic graph.

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

تقارن

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

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

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

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

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

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

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

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

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

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

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

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

گراف تیوت با ۴۶ راس در سال ۱۹۴۶ و در ۱۹۷۱ تیوت حدس زد که تمام گراف‌های دوبخشی مکعبی همیلتونی هستند درصورتی که جوزف هورتون یک مثال با ۹۶ راس زد.

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

خواص دیگر

طول مسیر تمام گراف‌هایی با n راس از سری گراف‌های مکعبی دست کم n/6 می‌باشد. درصورتی که بیشترین کران پایین طول مسیر گراف‌های مکعبی کمتر از 0.082n.^[۴]
توسط handshaking lemma که توسط لئونارد اویلر اثبات شده‌است در سال ۱۷۳۶ به عوان قسمتی از صفحه اول دفتر ئوری گراف نوشته شده‌است که هر گراف مکعبی که تمام گراف‌های مکعبی دارای تعداد زوج راس می‌باشند.
تئوری پترسن نشان می‌دهد که همهٔ گراف‌های مکعبی که دارای یال برشی هستند یک گراف با قابلیت 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 که رشد آن‌ها به کمتر یک می‌باشد ندارند.
این مشکلات شامل پیدا کردن حداقل پوشش راس و بیشترین مجموعه مستقل و حداقل مجموعه‌های مربوطه و بیشترین برش می‌باشد هستند.^[۸]
حال عدد گذرش (که حداقل تعداد یال‌هایی می‌باشد که می‌توان در یک گرافذ گذر کرد) گراف‌های مکعبی یک ان‌پی سختمی‌باشد که برای گراف‌های مکعبی ممکن است تقریب زده شده باشد.^[۹][۱۰]

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

• Table of simple cubic graphs

منابع

1. Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math. , Univ. Melbourne, Melbourne, 1981.
2. Ellingham, M. N.; Horton, J. D. (1983), "Non-Hamiltonian 3-connected cubic bipartite graphs", Journal of Combinatorial Theory, Series B, 34 (3): 350–353, doi:10.1016/0095-8956(83)90046-1.
3. Gebauer, H. (2008), "On the number of Hamilton cycles in bounded degree graphs", Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08) (PDF)^{[پیوند مرده]}.
4. Fomin, Fedor V.; Høie, Kjartan (2006), "Pathwidth of cubic graphs and exact algorithms", Information Processing Letters, 97 (5): 191–196, doi:10.1016/j.ipl.2005.10.012.
5. Esperet, Louis; Kardoš, František; King, Andrew D.; Kráľ, Daniel; Norine, Serguei (2011), "Exponentially many perfect matchings in cubic graphs", Advances in Mathematics, 227 (4): 1646–1664, doi:10.1016/j.aim.2011.03.015.
6. Xiao, Mingyu; Nagamochi, Hiroshi (2013), "An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure", Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol. 7876, Springer-Verlag, pp. 96–107, doi:10.1007/978-3-642-38236-9_10, ISBN 978-3-642-38236-9.
7. Xiao, Mingyu; Nagamochi, Hiroshi (2012), An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure, arXiv:1212.6831.
8. Alimonti, Paola; Kann, Viggo (2000), "Some APX-completeness results for cubic graphs", Theoretical Computer Science, 237 (1–2): 123–134, doi:10.1016/S0304-3975(98)00158-3.
9. Hliněný, Petr (2006), "Crossing number is hard for cubic graphs", Journal of Combinatorial Theory, Series B, 96 (4): 455–471, doi:10.1016/j.jctb.2005.09.009.
10. Karpinski, Marek; Schmied, Richard (2013), Approximation Hardness of Graphic TSP on Cubic Graphs, arXiv:1304.6800.

پیوند به بیرون

• Royle, Gordon. "Cubic symmetric graphs (The Foster Census)". Archived from the original on 23 October 2011. Retrieved 26 June 2016.
• Weisstein, Eric W. "Bicubic Graph". MathWorld.
• Weisstein, Eric W. "Cubic Graph". MathWorld.