||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
^@#16:
!همبندی و مولفه های همبندی
با مفهوم همبندی و برقراری ارتباط میان رئوسی آشنا شده ایم. حال به طور تخصصی تر به مباحث مربوطه می پردازیم.
•یاد آوری می کنیم، گراف{TEX()} {G} {TEX}را همبند می گوییم اگر به ازای هر دو راس{TEX()} {v,u} {TEX} از آن مسیری بین {TEX()} {v,u} {TEX} موجود باشد.
•در یک گراف{TEX()} {G} {TEX}،‌ زیر گراف های همبند مجزای آن را مولفه های همبندی {TEX()} {G} {TEX}می نامیم.
---
!قضیه
نشان دهید که {TEX()} {G} {TEX} همبند است، اگر و تنها اگر به ازای هر افراز {TEX()} {V} {TEX} به دو مجموعه ناتهی{TEX()} {v_2,v_1} {TEX} ،‌ یالی با یک انتها در {TEX()} {v_1} {TEX} و یک انتها در{TEX()} {v_2} {TEX} موجود باشد.
__اثبات__
نخست به برهان خلف ثابت می کنیم اگر به ازای دو مجموعه ناتهی {TEX()} {v_2,v_1} {TEX} یالی با یک انتها در{TEX()} {v_1} {TEX}و یک انتها در {TEX()} {v_2} {TEX} موجود نباشد آنگاه گراف ناهمبند خواهد شد زیرا از رئوس {TEX()} {v_1} {TEX}هیچگاه نمی توان به رئوس {TEX()} {v_2} {TEX} رفت.
اما بالعکس باید ثابت کنیم اگر به ازای هر افراز {TEX()} {v} {TEX}به {TEX()} {v_2,v_1} {TEX}، یالی میان {TEX()} {v_2,v_1} {TEX}موجود باشد آنگاه ((گراف)) همبند است.
اگر به ازای هر افراز {TEX()} {v_2,v_1} {TEX} شرط برقرار باشد و {TEX()} {v=\{u_1,u_2,\cdots ,u_n \}} {TEX}
آنگاه نخست فرض می کنیم{TEX()} {v_2=v-\{u_1 \},v_1={u_1 \}} {TEX} لذا {TEX()} {u_1} {TEX}به راسی مانند {TEX()} {u_i} {TEX} متصل خواهد بو د حال {TEX()} {v_2=v-v_1,v_1=\{u_1,u_i \}} {TEX} را در نظر می گیریم،‌ مانند قبل راسی مانند {TEX()} {u_i2}} {TEX} به راسی از رئوس {TEX()} {v_1} {TEX} یال دارد و چون {TEX()} {v_1} {TEX} یک دسته همبندی است {TEX()} {u_{i2}} {TEX} هم به آن دسته اضافه می گردد. ملاحظه می گردد با ادامه این روش همواره {TEX()} {v_1} {TEX} یک دسته همبندی باقی مانده و بزرگتر می گردد تا آنجا که {TEX()} {v_1=v} {TEX} گشته و این یعنی کل گراف همبند است.
---
!تمرین
#@
@#16:
ثابت کنید در ((گراف ساده)) {TEX()} {G} {TEX} اگر{TEX()} {|E(G)|>{{|V|-1}\choose 2}} {TEX} ‌آنگاه {TEX()} {G} {TEX}همبند است.
__جواب__
به راحتی اثبات می کنیم هر گراف ناهمبند،‌ حداکثر{TEX()} {{|V|-1}\choose 2} {TEX} یال دارد. زیرا گراف{TEX()} {G} {TEX} اگر ناهمبند باشد رئوس آن را می توان به دو دسته رئوس {TEX()} {v_2,v_1} {TEX} افراز کرد که یالی میان{TEX()} {v_2,v_1} {TEX} نباشد. اگر تعداد رئوس {TEX()} {v_!} {TEX} را {TEX()} {m} {TEX} و تعداد کل رئوس را {TEX()} {|V|} {TEX} بگیریم آنگاه داریم:
@@حداکثر تعداد یالهای{TEX()} {+v_1} {TEX} حداکثر تعداد یالهای{TEX()} {=v_2} {TEX} حداکثر تعداد یالهای {TEX()} {G} {TEX}@@
@@{TEX()} {=\frac{(|V|-m)(|V|-m-1)}{2}+\frac{m(m-1)}{2}=\frac{|V^2|-2m|V|-|V|+m^2+m+m^2-m}{2}} {TEX}@@
@@{TEX()} {=\frac{|V^2|-2|V|m+2m^2-|V|}{2}=\frac{|V|(|V|-1)+2m^2-2|V|m}{2}} {TEX}@@
و چون {TEX()} {2m^2-2|V|m \ge 0} {TEX}
@@{TEX()} {\le \frac{|V|(|V|-1)}{2}} {TEX}حداکثر تعداد یالهای{TEX()} {\Rightarrow G} {TEX} @@
پس اگر تعداد یالها از این تعداد بیشتر باشد آنگاه گراف همبند خواهد بود
---
!قضیه
اگر{TEX()} {G(v_1,v_2)} {TEX} یک گراف دو بخشی باشد،‌ طول هر مدار آن زوج است.
__برهان__
تمام رئوس متعلق به {TEX()} {v_1} {TEX} را سفید و تمام رئوس متعلق به {TEX()} {v_2} {TEX} را سیاه می کنیم.
هر دور آن را که به صورت{TEX()} {v_1v_2\cdots v_mv_1} {TEX} در نظر بگیریم به قرینه فرض می کنیم {TEX()} {v_1\in V_1} {TEX} آنگاه {TEX()} {v_1} {TEX} سفید بوده و در گام بعد الزاماً باید به رئوس{TEX()} {v_2} {TEX} برویم که سیاه می باشند و در گام بعد الزاماً‌ باید به رئوس {TEX()} {V_1} {TEX} برگردیم که سفیدند و این حرکت های یک در میان سفید و سیاه را ادامه می دهیم تا به {TEX()} {v_m} {TEX} برسیم که الزاماً‌ سیاه است ( چرا؟ ) پس تعداد کل سفیدها و سیاه ها برابر بوده و این یعنی تعداد رئوس مدار زوج بوده و یعنی طول آن زوج است: {TEX()} {m=2k,k\in Z} {TEX}
---
!قضیه
#@
@#16:
اگر{TEX()} {G} {TEX} گراف ساده {TEX()} {n} {TEX} راسی و دارای{TEX()} {k} {TEX} مولفه همبندی باشد و {TEX()} {|E|} {TEX} تعداد یالهای آن باشد ثابت کنید.
@@{TEX()} {n-k \le |E| \le \frac{1}{2} (n-k)(n-k+1)} {TEX}@@
اولاً{TEX()} {|E| \le \frac{1}{2} (n-k)(n-k+1)} {TEX}‌زیرا در بدترین حالت تمام مولفه ها کامل هستند. حال فرض می‌کنیم {TEX()} {G_j,G_i} {TEX}دو مولفه با {TEX()} {n_j,n_i} {TEX} راسی باشند که {TEX()} {n_i \ge n_j} {TEX}،‌با تغییر یک راس از {TEX()} {G_j} {TEX} به {TEX()} {G_i} {TEX} تعداد یالها در مجموع افزایش خواهد یافت زیرا
@@{TEX()} {=\Bigg( \frac{n_i(n_i-1)}{2}+\frac{n_j(n_j-1)}{2} \Bigg)- \Bigg( \frac{ (n_i+1)n_i}{2}+\frac{(n_j-1)(n_j-2)}{2} \Bigg)=\cdots =n_i-n_j+1 >0} {TEX}تفاوت تعداد یالها در حالت قدیم و جدید@@
پس با ادامه این فرآیند، بیشترین تعداد یالهای ممکن زمانی خواهد بود که{TEX()} {k-1} {TEX} مولفه، یک راسی و یک مولفه {TEX()} {n-k+1} {TEX} راسی باشد پس:
@@{TEX()} {|E| \le \frac{1}{2} (n-k)(n-k+1)} {TEX}@@
برای اثبات{TEX()} {(n-k)\le |E|} {TEX} نخست باید لم زیر را ثابت کنیم:
---
!!لم1
در هر گراف همبند {TEX()} {m} {TEX} راسی حداقل{TEX()} {(m-1)} {TEX} یال وجود خواهد داشت.
__اثبات به ((استقرا))__
برای {TEX()} {m=1} {TEX} که بدیهی است.
فرض می کنیم برای {TEX()} {m=k} {TEX} گراف همبند {TEX()} {k} {TEX} راسی لااقل {TEX()} {k-1} {TEX} یال داشته باشد.
برای{TEX()} {m=k+1} {TEX}،‌ اگر راس با درجه 1 وجود داشته باشد که آن را و یال مربوطه را حذف می کنیم برای{TEX()} {k} {TEX} راس باقی مانده ،‌همبندی بر هم نمی خورد پس بنابر فرض لااقل{TEX()} {k-1} {TEX}یال دارند که با یال حذف شده کلاً‌ {TEX()} {k} {TEX} یال می شود.
#@
@#16:
و اگر راس با درجه 1 نداشته باشیم پس تمام رئوس درجه بزرگتر یا مساوی با 2 داشته پس
@@{picture=img/daneshnameh_up/0/02/mco0062a.jpg}@@
تعداد یالها
لذا حکم ثابت می باشد:
حال به اثبات قضیه می پردازیم،‌لم 1 به این صورت نیز می تواند تعبیر شود که در هر مولفه یالها حداقل یکی کمتر از راسها می باشند پس اگر {TEX()} {k} {TEX} مولفه داشته باشیم جمعاً حداقل تعداد یالها {TEX()} {n-k} {TEX} خواهد شد که حکم ثابت می گردد.
---
!قضیه
نشان دهید که در هر گراف همبند {TEX()} {G} {TEX}، دو تا طولانیترین مسیر آن لااقل یک راس مشترک دارند.
__اثبات__
به برهان خلف
اگر دو مسیر {TEX()} {u_1u_2\cdots u_n , v_1v_2\cdots v_m} {TEX}
دو طولانیترین مسیر {TEX()} {G} {TEX} باشند که هیچ راس مشترکی ندارند آنگاه داریم:
چون گراف همبند است پس مسیری میان یکی از رئوس اولی مانند {TEX()} {v_i} {TEX} به یکی از رئوس دومی مانند {TEX()} {u_j} {TEX} وجود دارد که بجز {TEX()} {u_i,v_i} {TEX} هیچ راسی از این دو مسیر در آن ظاهر نشده باشند و به قرینه فرض کنید {TEX()} {i>j} {TEX} باشد آنگاه
@@{TEX()} {v_1v_2v_3\cdots v_iv_{i+1}\cdots v_m} {TEX}@@
@@{TEX()} {u_1u_2\cdots u_ju_{j+1}\cdots u_n} {TEX}@@
و مسیر بین{TEX()} {u_j,v_i} {TEX} را {TEX()} {\overline{w}} {TEX} بنامیم.
مسیر{TEX()} {v_1v_2\cdots v_i \overline{w}u_ju_{j+1} \cdots u_n} {TEX} را در نظر بگیرید.
واضح است طول آن از {TEX()} {min(m,n)} {TEX} بزرگتر است و این یعنی دو مسیر اولی دو طولانیترین مسیرها نبودند و این یعنی تناقض.
---
#@
@#16:
•تعریف می کنیم فاصله رئوس {TEX()} {v,u} {TEX}:
فاصله دو راس {TEX()} {v,u} {TEX} را که با{TEX()} {d(u,v)} {TEX}نمایش می دهیم طول کوتاهترین مسیر موجود در میان آنها تعریف می کنیم و اگر{TEX()} {u} {TEX} به {TEX()} {v} {TEX}مسیر نداشت،‌ {TEX()} {d(u,v)} {TEX}را برابر بی نهایت! می گیریم.
---
!قضیه
به ازای هر سه راس{TEX()} {u,v,w \in V} {TEX} ثابت کنید:
@@{TEX()} {d(u,v)+d(v,w) \ge d(u,w)} {TEX}@@
واضح است زیرا به برهان اگر{TEX()} {d(u,w)>d(u,v)+d(v,w)} {TEX} آنگاه برای رفتن از{TEX()} {u} {TEX} به {TEX()} {w} {TEX} نخست با طول{TEX()} {d(u,v)} {TEX} به{TEX()} {v} {TEX}رفته و سپس از آن با طول{TEX()} {d(v,w)} {TEX} به {TEX()} {w} {TEX} می رویم پس جمعاً طول{TEX()} {d(u,v)+d(v,w)} {TEX} را پیموده ایم و این یعنی مسیر کوتاهتری یافته ایم. تناقض!
---
!قضیه
ثابت کنید گراف {TEX()} {G} {TEX} دو بخشی است اگر و تنها اگر دور فرد نداشته باشد.
اینکه تمام دورهای یک گراف دو بخشی زوج می باشد را قبلاً‌ اثبات نموده ایم حال باید ثابت کنیم هر گراف که دور فرد نداشته باشد دو بخشی است.
در هر مولفه آن یک راس مانند {TEX()} {u} {TEX} را در نظر می گیریم و رئوس را به دو بخش زیر افراز می کنیم.
@@{TEX()} {A=\{v\in V|d(u,v)=2n \ ; \ n\in N \}} {TEX}@@
@@{TEX()} {B=\{v\in V|d(u,v)=2n+1 \ ; \ n\in N} {TEX}@@
حال ثابت می کنیم هیچ یالی که هر دو سر آن متعلق به {TEX()} {A} {TEX}یا هر دو سر آن متعلق به {TEX()} {B} {TEX}باشد وجود ندارد.
__برهان خلف__
اگر داشته باشیم{TEX()} {xy\in E} {TEX} که {TEX()} {y\in A,x\in A} {TEX}
::{picture=img/daneshnameh_up/d/db/mco0062b.jpg}::
حال ثابت می کنیم دور فردی وجود دارد زیرا از {TEX()} {u} {TEX} با مسیری به طول زوج {TEX()} {d(u,x)} {TEX} به {TEX()} {x} {TEX} رفته و از آن با یک یال به{TEX()} {y} {TEX}رفته و دوباره از {TEX()} {y} {TEX} با مسیری به طول زوج {TEX()} {d(y,u)} {TEX} به{TEX()} {u} {TEX} باز می گردیم پس جمعاً فرد خانه پیموده ایم و این خلف فرض سوال می باشد.
برای زمانی که {TEX()} {y,x} {TEX} را عضو{TEX()} {b} {TEX} نیز فرض کنیم مشابه بالا دور فرد وجود خواهد داشت. پس بخش بندی داده شده معتبر بوده و گراف 2 بخشی می باشد.
#@
@#16:
---
!تمرین
ثابت کنید هر راس {TEX()} {v} {TEX} و هر یال{TEX()} {e} {TEX} متعلق به یک گذر بسته،‌ در لااقل یک دور از{TEX()} {G} {TEX} نیز،‌ظاهر می شوند.
---
!تمرین
کمر{TEX()} {G} {TEX} را طول کوتاهترین دور در {TEX()} {G} {TEX} تعریف می کنیم. حداقل کمر و حداکثر کمر ممکن برای {TEX()} {n} {TEX} راس چه می تواند باشد؟
---
!قضیه
اگر{TEX()} {\delta \ge 2} {TEX} باشد ثابت کنید گراف لااقل یک دور دارد.
__اثبات__
به سادگی از یک راس دلخواه شروع می کنیم و به دلخواه روی یکی از یالهای آن حرکت می‌کنیم پس از آن به هر راس که رسیدیم، یکی از یالهای غیر تکراری آن را بر می گزینیم و راه خود را ادامه می دهیم چون هر راس لااقل 2 یال دارد پس تا زمانی که به یک راس تکراری نرسیم،‌ این الگوریتم ادامه خواهد داشت و چون کل یالها متناهی می باشد پس حتماً الگوریتم پایان خواهد پذیرفت و یعنی به راس تکراری می رسیم و این یعنی وجود یک گشت بسته و این هم یعنی وجود لااقل یک دور.
---
!قضیه
اگر{TEX()} {\delta \ge 2} {TEX} باشد ثابت کنید دور آن لااقل طول {TEX()} {\delta +1} {TEX} دارد. ({TEX()} {\delta} {TEX}کوچکترین درجه می باشد)
!!لم 1
بزرگترین مسیر گراف فوق لااقل طول {TEX()} {\delta} {TEX} دارد.
__اثبات__
به برهان خلف.
فرض کنیم بزرگترین مسیر آن{TEX()} {v_!v_2\cdots v_m (m\le \delta )} {TEX} باشد{TEX()} {v_m} {TEX} را در نظر می گیریم،‌ چون لااقل درجه آن {TEX()} {\delta} {TEX} می باشد و تعداد رئوس این مسیر بجز خودش حداکثر {TEX()} {\delta -1} {TEX} می باشد پس به یک راس مانند {TEX()} {v_{m+1}} {TEX}از رئوس دیگر متصل است که در این صورت مسیر {TEX()} {v_1v_2\cdots v_mv_{m+1}} {TEX} مسیر طولانی تری خواهد بود و این یعنی تناقض
حال به اثبات باز می گردیم،‌در گراف داده شده بزرگترین مسیر آن را در نظر می گیریم و فرض می‌کنیم به صورت{TEX()} {u_1u_2\cdots u_m} {TEX} باشد که ثابت کردیم{TEX()} {m \ge \delta +1} {TEX} ، حال راس {TEX()} {u_1} {TEX} را در نظر بگیرید،‌{TEX()} {u_1} {TEX} نمی‌تواند به راسی بجز رئوس این مسیر یال داشته باشد چون مسیر طولانیتری ساخته خواهد شد (چرا؟ )
در داخل این رئوس نیز راسی مانند {TEX()} {u_j} {TEX} که{TEX()} {j \ge \delta +1} {TEX} باشد وجود خواهد داشت که {TEX()} {u_1} {TEX} به آن متصل است (چرا؟ ) حال دنباله{TEX()} {u_1u_2\cdots u_ju_i} {TEX} دور به طول{TEX()} {\delta +1} {TEX}خواهد بود.
---
#@
@#16:
__یادآوری__
تا کنون در اثبات بعضی قضایا سعی می کردیم خصوصیتی را ماکسیمم یا مینیمم کرده و سپس درباره آن صحبت کنیم مانند اثبات اینکه در گراف{TEX()} {G} {TEX} با{TEX()} {\delta \ge 2} {TEX} لااقل یک مسیر با طول بزرگتر از {TEX()} {\delta +1} {TEX} وجود دارد که بزرگترین مسیر آن را در نظر گرفته و روی آن بحث کردیم.
به این فن اثبات اکسترمال گیری می گویند،‌ که با این فن در حقیقت،‌ به فرضیات سوال، فرضیات دلخواهی را می افزاییم.
برای تسلط به این روش قضایای زیر را با هم اثبات می کنیم.
---
!قضیه
فرض کنیم {TEX()} {G} {TEX} گراف ساده با{TEX()} {|E| \ge 1} {TEX} باشد. اگر فرض کنیم{TEX()} {G} {TEX} دوری نداشته باشد ثابت کنید {TEX()} {G} {TEX} دارای یک راس از درجه 1 می باشد.
چون{TEX()} {G} {TEX} ساده است،‌هر مسیر آن متناهی است و بین تمام مسیرها این بار نیز بزرگترین مسیر آن را در نظر می گیریم. فرض کنیم {TEX()} {u} {TEX} یکی از رئوس انتهایی آن باشد،‌ چون این مسیر بزرگترین مسیر در {TEX()} {G} {TEX} می باشد پس تمام همسایه های {TEX()} {u} {TEX} باید در داخل مسیر باشند و گرنه مسیر بزرگتری بوجود خواهد آمد.
::{picture=img/daneshnameh_up/1/13/mco0062c.jpg}::
از طرفی {TEX()} {u} {TEX} به هیچ یک از رئوس مسیر بجز راس قبلی آن نمی تواند یال داشته باشد چون دور بوجود می آید. پس {TEX()} {u} {TEX}، الزاما‌ً درجه 1 خواهد بود.
---
!تمرین
گراف ساده {TEX()} {G} {TEX} را در نظر بگیرید که دور ندارد. و دارای {TEX()} {k} {TEX} مولفه همبندی که هر مولفه لااقل 2 راس دارد. می باشد.
ثابت کنید لااقل {TEX()} {2k} {TEX} راس درجه 1 دارد.
__اثبات__
در هر مولفه همبندی بزرگترین مسیر آن را در نظر می گیریم.
فرض می کنیم{TEX()} {v_1v_2\cdots v_m} {TEX} باشد چون این مسیر بزرگترین مسیر می باشد نه {TEX()} {v_1} {TEX} نه {TEX()} {v_m} {TEX} نمی توانند به هیچ کدام از رئوس{TEX()} {G} {TEX} بجز رئوس این مسیر متصل باشند از طرفی اگر به رئوس داخلی این مسیر هم متصل باشند دور بوجود می آید و این خلاف فرض است پس هر دو الزاماً‌ درجه 1 می باشند. پس به ازای هر مولفه لااقل 2 راس درجه 1 داریم پس جمعاً لااقل {TEX()} {2k} {TEX} راس درجه 1 خواهیم داشت.
•ایده اکسترمال گیری به همین سادگی می باشد و لیکن کاربردهای فراوانی و شکل های متفاوتی دارد که براساس ابداع خود شما می باشد گاهی روی مسیر ماکسیمم بحث می کنید گاهی روی زیر گراف ماکسیممی که خصوصیت {TEX()} {X} {TEX}را داشته باشد یا دور ماکزیمم و یا ... در ادامه مباحث به نمونه های بسیاری از این دست خواهیم خورد.
#@
@#16:
•به طور کلی سه روش ((استقرا))،‌ اکسترمال و برهان خلف پر کاربرد ترین روشهای اثبات در مسائل ((گراف)) می باشند.
---
!قضیه
هر گراف با {TEX()} {n} {TEX}راس و {TEX()} {k} {TEX}یال دارای حداقل{TEX()} {n-k} {TEX} مولفه است.
__اثبات__
فرض کنیم تعداد مولفه ها {TEX()} {m} {TEX} باشد و تعداد یالها را هم با {TEX()} {|E|} {TEX} نمایش می دهیم ثابت کرده بودیم:
@@{TEX()} {|E| \ge n-m \qquad (1)} {TEX}@@
حال به برهان خلف اگر{TEX()} {<n-k)} {TEX} تعداد مولفه ها ) باشد آنگاه:
@@{TEX()} {m<n-|E|} {TEX}@@
@@{TEX()} {\Rightarrow |E| <n-m \qquad (2)} {TEX}@@
که 1 با 2 در تناقض می باشد لذا ((گراف)) حداقل {TEX()} {n-k} {TEX} مولفه دارد.
---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0094.pdf]
---
!همچنین ببینید
*((پل های کوینگسبرگ ))
*((گرافهای اویلری ))
#@^