گراف k-مکعب

درمیان گرافهای دو بخشی، k – مکعب‌ها از اهمیت خاصی برخوردار دارند.

تعریف

گراف k- مکعب الگو:نشان گرافی است که رئوس آن دنباله‌های غیر تکراری k تایی از 0 و 1 به صورت (a₁, a_k, … , a₁) باشد. و یالهای آن، میان رئوس رسم شوند که دقیقاً در یک جایگاه متفاوت باشند.

این گراف‌ها را که با Q_k نمایش می‌دهند خصوصیت‌های جالبی دارند که پس از چند مثال به خواص آن‌ها می‌پردازیم.

پرونده:Graph-k1.jpg

دقت کنید گراف مکعب همان Q₃ می‌باشد که گاهی به صورت زیر نیز رسم می‌گردد.

پرونده:Graph-k2.jpg

دقت کنید Q₃,Q₂,Q₁ به ترتیب بیانگر فضاهای یک بعدی (خط)، دو بعدی (صفحه) و سه بعدی (فضا) بوده‌اند.

قضیه اول(همبندی)

ثابت کنید گراف k- مکعب همبند است.الگو:سخ کافی است به ازای هر دو راس v,u با دنباله‌های زیر، مسیری میان آن دو بیابیم.

u=(a₁, a₂, … , a_k)الگو:سخ v=(b₁, b₂, … , b_k)الگو:سخ

به‌طور خلاصه اگر اثبات را بیان کنیم داریم:الگو:سخ اگر u با v در m جایگاه تفاوت داشته باشد، از u نخست به راسی می رویم که با u در جایگاه اول از آن m جایگاه متفاوت باشد.سپس از آن به راسی می رویم که علاوه بر جایگاه اول در جایگاه دوم از آن m جایگاه با u متفاوت باشد و به همین ترتیب ادامه می دهیم تا به v برسیم. واضح است چنین مسیری وجود خواهد داشت.

تمرین(تعداد یال ها)

تعداد یالهای گراف k- مکعب را بدست آورید.

حل

برای این منظور نخست تعداد راسها را بدست می آوریم:الگو:سخ چون رئوس دنباله‌های متفاوت k تایی از 0 و 1 می‌باشند پس بنابر اصل ضرب تعداد آن‌ها 2^k تا می‌باشد.سپس درجه هر راس را بدست می آوریم: از آنجا که به هر راس یک دنباله k تایی از 0 و 1 متناظر شده و هر راس تنها به رئوسی متصل می‌گردد که دقیقاً در یک جایگاه با آن تفاوت دارند پس همسایه‌های هر راس عبارتند از:الگو:سخ راسی که فقط درجایگاه اول با آن تفاوت داردالگو:سخ و راسی که فقط در جایگاه دوم با آن تفاوت داردالگو:سخ و...الگو:سخ تا راسی که فقط در جایگاه k ام با آن تفاوت دارد.الگو:سخ و این یعنی درجه هر راس k می‌باشدالگو:سخ پسالگو:سخ تعداد یالها = $\frac{k\times 2^k}{2}=k{2}^{k-1}$

نتیجه

به راحتی دیده شد گراف k- مکعب، k منتظم می‌باشد.

قضیه دوم(دو بخشی)

ثابت کنید Q_k گرافی دو بخشی می‌باشد.

پرونده:Graph-k2.jpg

مثال: در Q₃، رئوس آبی متعلق به یک بخش و رئوس سیاه متعلق به بخش دیگر گراف دو بخشی خواهند بود

برای این منظور بایستی رئوس آن را به دو بخش A، B به گونه‌ای افراز کرد که یالی ما بین رئوس داخل یک بخش موجود نباشد: بدین منظور:

رئوسی که دنباله آن تعداد زوجی عدد 1 دارند = Aالگو:سخ رئوسی که دنباله آن تعداد فردی عدد 1 دارند = B

حال یالی میان رئوس A وجود نخواهد داشت زیرا اگر وجود داشته باشد. و آن یال uv باشد که v,u ∈ A پس خواهیم داشت:الگو:سخ زیرا v,u دقیقاً در یک جایگاه تفاوت دارند $⟶$ 1± تعداد 1های u = تعداد 1های vالگو:سخ پس v,u نمی‌توانند از لحاظ زوجیت و فردیت مانند هم باشند.الگو:سخ پس یالی که رئوس A را به هم یا رئوس B را به هم وصل کند وجود نداشته و گراف دو بخشی خواهد بود.(مثال)

قضیه سوم(همیلتونی)

ثابت کنید که گراف k- مکعب همیلتونی است (k≥2).

اثبات با استقرا

برای k=2 که بدیهی است:

پرونده:Graph-k4.jpg

فرض می کنیم برای m-1) ,k=m-1)- مکعب همیلتونی باشد یعنی دنباله‌ای از رئوس به صورت u₁u₂u₃ … u_2^m-1u₁ وجود دارد که هر کدام به بعدی یال داشته و u_2^m-1 هم به u₁ یال داشته باشد.الگو:سخ می خواهیم برای k=m، ثابت کنیم دنباله رئوسی به صورت

u₁u₂u₃ … u_2^mu₁

وجود دارد که v_i = a_i1a_i2 … a_im و تشکیل یک دور همیلتونی را بدهند.

از روی فرض استقرا دنباله v_iها را به صورت زیر می سازیم: الگو:سخ

w₁w₂ … w_2^m-1X_2^m-1X_2^m-1-1 … X₂X₁ … w₁

کهالگو:سخ

یعنی به سر رشته u_i یک 1 اضافه می کنیم $⟶$ w_i = (1,u_i)الگو:سخ یعنی به سر رشته u_i یک 10 اضافه می کنیم $⟶$ X_i = (0,u_i)

واضح است که در این دنباله هر راس دقیقاً یکبار آمده. ولیکن باید ثابت کنیم هر دو راس متوالی مجاور نیز هستند.الگو:سخ برای اثبات آنکه هر دو راس متوالی، مجاورند حالات زیر را داریم:الگو:سخ 1. رئوس متوالی w_i, w_i+1 باشند که واضح است چون

پرونده:Graph-k5.jpg

2. رئوس متوالی X_i, X_i+1 باشند(مانند بالا)الگو:سخ 3. رئوس متوالی w_2^m-1, X_2^m-1 باشند که داریم:

پرونده:Graph-k6.jpg

4. رئوس متوالی w₁, X₁ باشند که مانند قبل داریم:

پرونده:Graph-k7.jpg

لذا دنباله w₁w₂… w_2^m-1X_2^m-1X_2^m-1-1 … X₂X₁ … w₁ معرف دور همیلتونی خواسته شده می‌باشد.

پانویس‌ها

1. الگو:پاورقیcubic graph

منابع

• http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/defEx.htm
• http://en.wikipedia.org/wiki/Cubic_graph
• http://mathworld.wolfram.com/CubicGraph.html
• https://web.archive.org/web/20090617103702/http://powerpoint.pnu.ac.ir/dbs/Mathematics/Nazareye%20Geraf%20Va%20Karbordhaye%20an/Bijhan%20Roohi/Nazariyeye%20Geraf(Roohi).ppt