: گرافهای k

||V{maketoc}||

^@#16:

!گرافهای{TEX()} {-k} {TEX}مکعب

گراف {TEX()} {-k} {TEX}مکعب گرافی است که رئوس آن دنباله های غیر تکراری {TEX()} {k} {TEX}تایی از 0 و 1 به صورت {TEX()} {(a_1,a_2,\cdots , a_k)} {TEX} باشد. و یالهای آن، میان رئوس رسم شوند که دقیقاً در یک جایگاه متفاوت باشند.

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

::{picture=img/daneshnameh_up/1/17/mco0060a.jpg}::

دقت کنید گراف مکعب همان{TEX()} {Q_3} {TEX} می باشد که گاهی به صورت زیر نیز رسم می گردد.

::{picture=img/daneshnameh_up/c/c7/mco0060b.jpg}::

دقت کنید{TEX()} {Q_3,Q_2,Q_1} {TEX} به ترتیب بیانگر فضاهای یک بعدی ( خط)، دو بعدی ( ((صفحه)) ) و سه بعدی (فضا ) بوده اند.

---

!قضیه

ثابت کنید گراف {TEX()} {-k} {TEX}مکعب همبند است.

کافی است به ازای هر دو راس {TEX()} {v,u} {TEX}با دنباله های زیر، مسیری میان آن دو بیابیم.

@@{TEX()} {u=(a_1,a_2,\cdots ,a_k)} {TEX}@@

@@{TEX()} {v=(b_1,b_2,\cdots ,b_k)} {TEX}@@

به طور خلاصه اگر اثبات را بیان کنیم داریم:

اگر{TEX()} {u} {TEX} با{TEX()} {v} {TEX} در {TEX()} {m} {TEX}جایگاه تفاوت داشته باشد، از{TEX()} {u} {TEX} نخست به راسی می رویم که با {TEX()} {u} {TEX} در جایگاه اول از آن{TEX()} {m} {TEX} جایگاه متفاوت باشد. سپس از آن به راسی می رویم که علاوه بر جایگاه اول در جایگاه دوم از آن{TEX()} {m} {TEX} جایگاه با {TEX()} {u} {TEX} متفاوت باشد و به همین ترتیب ادامه می دهیم تا به {TEX()} {v} {TEX} برسیم.

واضح است جنین مسیری وجود خواهد داشت.

---

!تمرین

تعداد یالهای گراف{TEX()} {-k} {TEX}مکعب را بدست آورید.

__حل__

برای این منظور نخست تعداد راسها را بدست می آوریم:

چون رئوس دنباله های متفاوت {TEX()} {k} {TEX} تایی از 0 و 1 می باشند پس بنابر اصل ضرب تعداد آنها {TEX()} {2^k} {TEX} تا می‌باشد. سپس درجه هر راس را بدست می آوریم:

از آنجا که به هر راس یک دنباله {TEX()} {k} {TEX} تایی از 0 و 1 متناظر شده و هر راس تنها به رئوسی متصل می گردد که دقیقاً در یک جایگاه با آن تفاوت دارند پس همسایه های هر راس عبارتند از :

راسی که فقط درجایگاه اول با آن تفاوت دارد

و راسی که فقط در جایگاه دوم با آن تفاوت دارد

و ...

تا راسی که فقط در جایگاه {TEX()} {k} {TEX}ام با آن تفاوت دارد.

و این یعنی درجه هر راس {TEX()} {k} {TEX} می باشد

پس

@@{TEX()} {=\frac{k\times 2^k}{2}=k2^{k-1}} {TEX}تعداد یالها@@

---

!!نتیجه

به راحتی دیده شد گراف {TEX()} {-k} {TEX}مکعب،{TEX()} {k} {TEX} منتظم می باشد.

---

!قضیه

ثابت کنید{TEX()} {Q_k} {TEX} گرافی دو بخشی می باشد.

برای این منظور بایستی رئوس آن را به دو بخش {TEX()} {B,A} {TEX} به گونه ای افراز کرد که یالی ما بین رئوس داخل یک بخش موجود نباشد:

بدین منظور:

رئوسی که دنباله آن تعداد زوجی عدد 1 دارند{TEX()} {A=} {TEX}

رئوسی که دنباله آن تعداد فردی عدد 1 دارند{TEX()} {B=} {TEX}

حال یالی میان رئوس {TEX()} {A} {TEX} وجود نخواهد داشت زیرا اگر وجود داشته باشد. و آن یال {TEX()} {uv} {TEX} باشد که {TEX()} {u,v\in A} {TEX} پس خواهیم داشت:

زیرا{TEX()} {v,u} {TEX} دقیقاً در یک جایگاه تفاوت دارند{TEX()} {\pm1 \rightarrow} {TEX} تعداد 1 های {TEX()} {=u} {TEX} تعداد 1 های {TEX()} {v} {TEX}

پس {TEX()} {v,u} {TEX} نمی توانند از لحاظ زوجیت و فردیت مانند هم باشند.

پس یالی که رئوس {TEX()} {A} {TEX} را به هم یا رئوس {TEX()} {B} {TEX} را به هم وصل کند وجود نداشته و گراف دو بخشی خواهد بود.

---

!مثال

:: {picture=img/daneshnameh_up/2/20/mco0060c.jpg}::

و اما آخرین و جذابترین خصوصیت گرافهای {TEX()} {-k} {TEX}مکعب همیلتونی بودن آنهاست. در این رابطه به قضیه زیر می پردازیم:

---

!قضیه

ثابت کنید که گراف {TEX()} {-k} {TEX}مکعب هامیلتونی است. {TEX()} {(k\ge 2)} {TEX}

__اثبات به استقرا__

برای {TEX()} {k=2} {TEX} که بدیهی است

::{picture=img/daneshnameh_up/2/2a/mco0060d.jpg}::

فرض می کنیم برای{TEX()} {-(m-1),k=m-1} {TEX} مکعب هامیلتونی باشد یعنی دنباله ای از رئوس به صورت

@@{TEX()} {u_1u_2u_3\cdots u_{2^{m-1}}u_1} {TEX}@@

وجود دارد که هر کدام به بعدی یال داشته و {TEX()} {u_{2^{m-1}}} {TEX} هم به {TEX()} {u_1} {TEX} یال داشته باشد.

می خواهیم برای {TEX()} {k=m} {TEX}، ثابت کنیم دنباله رئوسی به صورت

@@{TEX()} {v_1v_2\cdots v_{2^m}v_1} {TEX}@@

وجود دارد که{TEX()} {v_i=a_{i_1}a_{i_2}\cdots a_{i_m}} {TEX} و تشکیل یک دور هامیلتونی را بدهند.

از روی فرض استقرا دنباله {TEX()} {v_i} {TEX}ها را به صورت زیر می سازیم

{TEX()} {w_1w_2\cdots w_{2^{m-1}}X_{2^{m-1}}X_{2^{m-1}-1}\cdots X_2X_1\cdots w_1} {TEX}

که

یعنی به سر رشته {TEX()} {u_i} {TEX} یک 1 اضافه می کنیم {TEX()} {w_i=(1,u_i)\rightarrow} {TEX}

یعنی به سر رشته{TEX()} {u_i} {TEX} یک 10 اضافه می کنیم {TEX()} {X_i=(0,u_i)\rightarrow } {TEX}

واضح است که در این دنباله هر راس دقیقاً یکبار آمده . ولیکن باید ثابت کنیم هر دو راس متوالی مجاور نیز هستند.

برای اثبات آنکه هر دو راس متوالی، مجاورند حالات زیر را داریم:

1.رئوس متوالی {TEX()} {w_i,w_{i+1}} {TEX} باشند که واضح است چون

::{picture=img/daneshnameh_up/e/ec/mco0060e.jpg}::

2.رئوس متوالی{TEX()} {X_i,X_{i+1}} {TEX}باشند: مانند بالا

3.رئوس متوالی{TEX()} {w_{2^{m-1}},X_{2^{m-1}}} {TEX} باشندکه داریم

::{picture=img/daneshnameh_up/e/e4/mco0060f.jpg}::

4.رئوس متوالی {TEX()} {w_1,X_1} {TEX} باشند که مانند قبل داریم:

::{picture=img/daneshnameh_up/e/e4/mco0060g.jpg}::

لذا دنباله{TEX()} {w_1w_2\cdots w_{2^{m-1}}X_{2^{m-1}}X_{2^{m-1}-1}\cdots X_2X_1\cdots w_1} {TEX} معرف دور همیلتونی خواسته شده می باشد.

---

! پیوند های خارجی

[http://Olympiad.roshd.ir/computer/content/pdf/0078.pdf]

---

!همچنین ببینید

*((گرافهای پترسن ))

*((گرافهای ستاره ))

#@^

تفاوت با نگارش: 1

سرویس‌های رشد:

فهرست: