منو
 کاربر Online
464 کاربر online

همبندی و مولفه های همبندی

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)



این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


همبندی و مولفه های همبندی

با مفهوم همبندی و برقراری ارتباط میان رئوسی آشنا شده ایم. حال به طور تخصصی تر به مباحث مربوطه می پردازیم.
•یاد آوری می کنیم، گرافرا همبند می گوییم اگر به ازای هر دو راس از آن مسیری بین موجود باشد.
•در یک گراف،‌ زیر گراف های همبند مجزای آن را مولفه های همبندی می نامیم.

قضیه

نشان دهید که همبند است، اگر و تنها اگر به ازای هر افراز به دو مجموعه ناتهی ،‌ یالی با یک انتها در و یک انتها در موجود باشد.
اثبات
نخست به برهان خلف ثابت می کنیم اگر به ازای دو مجموعه ناتهی یالی با یک انتها درو یک انتها در موجود نباشد آنگاه گراف ناهمبند خواهد شد زیرا از رئوس هیچگاه نمی توان به رئوس رفت.
اما بالعکس باید ثابت کنیم اگر به ازای هر افراز به ، یالی میان موجود باشد آنگاه گراف همبند است.
اگر به ازای هر افراز شرط برقرار باشد و
آنگاه نخست فرض می کنیم لذا به راسی مانند متصل خواهد بو د حال را در نظر می گیریم،‌ مانند قبل راسی مانند به راسی از رئوس یال دارد و چون یک دسته همبندی است هم به آن دسته اضافه می گردد. ملاحظه می گردد با ادامه این روش همواره یک دسته همبندی باقی مانده و بزرگتر می گردد تا آنجا که گشته و این یعنی کل گراف همبند است.

تمرین



ثابت کنید در گراف ساده اگر ‌آنگاه همبند است.
جواب
به راحتی اثبات می کنیم هر گراف ناهمبند،‌ حداکثر یال دارد. زیرا گراف اگر ناهمبند باشد رئوس آن را می توان به دو دسته رئوس افراز کرد که یالی میان نباشد. اگر تعداد رئوس را و تعداد کل رئوس را بگیریم آنگاه داریم:
حداکثر تعداد یالهای حداکثر تعداد یالهای حداکثر تعداد یالهای



و چون
حداکثر تعداد یالهای

پس اگر تعداد یالها از این تعداد بیشتر باشد آنگاه گراف همبند خواهد بود

قضیه

اگر یک گراف دو بخشی باشد،‌ طول هر مدار آن زوج است.
برهان
تمام رئوس متعلق به را سفید و تمام رئوس متعلق به را سیاه می کنیم.
هر دور آن را که به صورت در نظر بگیریم به قرینه فرض می کنیم آنگاه سفید بوده و در گام بعد الزاماً باید به رئوس برویم که سیاه می باشند و در گام بعد الزاماً‌ باید به رئوس برگردیم که سفیدند و این حرکت های یک در میان سفید و سیاه را ادامه می دهیم تا به برسیم که الزاماً‌ سیاه است ( چرا؟ ) پس تعداد کل سفیدها و سیاه ها برابر بوده و این یعنی تعداد رئوس مدار زوج بوده و یعنی طول آن زوج است:

قضیه



اگر گراف ساده راسی و دارای مولفه همبندی باشد و تعداد یالهای آن باشد ثابت کنید.

اولاً‌زیرا در بدترین حالت تمام مولفه ها کامل هستند. حال فرض می‌کنیم دو مولفه با راسی باشند که ،‌با تغییر یک راس از به تعداد یالها در مجموع افزایش خواهد یافت زیرا
تفاوت تعداد یالها در حالت قدیم و جدید

پس با ادامه این فرآیند، بیشترین تعداد یالهای ممکن زمانی خواهد بود که مولفه، یک راسی و یک مولفه راسی باشد پس:

برای اثبات نخست باید لم زیر را ثابت کنیم:

لم1

در هر گراف همبند راسی حداقل یال وجود خواهد داشت.
اثبات به استقرا
برای که بدیهی است.
فرض می کنیم برای گراف همبند راسی لااقل یال داشته باشد.
برای،‌ اگر راس با درجه 1 وجود داشته باشد که آن را و یال مربوطه را حذف می کنیم برای راس باقی مانده ،‌همبندی بر هم نمی خورد پس بنابر فرض لااقلیال دارند که با یال حذف شده کلاً‌ یال می شود.


و اگر راس با درجه 1 نداشته باشیم پس تمام رئوس درجه بزرگتر یا مساوی با 2 داشته پس
img/daneshnameh_up/0/02/mco0062a.jpg

تعداد یالها
لذا حکم ثابت می باشد:
حال به اثبات قضیه می پردازیم،‌لم 1 به این صورت نیز می تواند تعبیر شود که در هر مولفه یالها حداقل یکی کمتر از راسها می باشند پس اگر مولفه داشته باشیم جمعاً حداقل تعداد یالها خواهد شد که حکم ثابت می گردد.

قضیه

نشان دهید که در هر گراف همبند ، دو تا طولانیترین مسیر آن لااقل یک راس مشترک دارند.
اثبات
به برهان خلف
اگر دو مسیر
دو طولانیترین مسیر باشند که هیچ راس مشترکی ندارند آنگاه داریم:
چون گراف همبند است پس مسیری میان یکی از رئوس اولی مانند به یکی از رئوس دومی مانند وجود دارد که بجز هیچ راسی از این دو مسیر در آن ظاهر نشده باشند و به قرینه فرض کنید باشد آنگاه


و مسیر بین را بنامیم.
مسیر را در نظر بگیرید.
واضح است طول آن از بزرگتر است و این یعنی دو مسیر اولی دو طولانیترین مسیرها نبودند و این یعنی تناقض.



•تعریف می کنیم فاصله رئوس :
فاصله دو راس را که بانمایش می دهیم طول کوتاهترین مسیر موجود در میان آنها تعریف می کنیم و اگر به مسیر نداشت،‌ را برابر بی نهایت! می گیریم.

قضیه

به ازای هر سه راس ثابت کنید:

واضح است زیرا به برهان اگر آنگاه برای رفتن از به نخست با طول بهرفته و سپس از آن با طول به می رویم پس جمعاً طول را پیموده ایم و این یعنی مسیر کوتاهتری یافته ایم. تناقض!

قضیه

ثابت کنید گراف دو بخشی است اگر و تنها اگر دور فرد نداشته باشد.
اینکه تمام دورهای یک گراف دو بخشی زوج می باشد را قبلاً‌ اثبات نموده ایم حال باید ثابت کنیم هر گراف که دور فرد نداشته باشد دو بخشی است.
در هر مولفه آن یک راس مانند را در نظر می گیریم و رئوس را به دو بخش زیر افراز می کنیم.


حال ثابت می کنیم هیچ یالی که هر دو سر آن متعلق به یا هر دو سر آن متعلق به باشد وجود ندارد.
برهان خلف
اگر داشته باشیم که
img/daneshnameh_up/d/db/mco0062b.jpg

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



تمرین

ثابت کنید هر راس و هر یال متعلق به یک گذر بسته،‌ در لااقل یک دور از نیز،‌ظاهر می شوند.

تمرین

کمر را طول کوتاهترین دور در تعریف می کنیم. حداقل کمر و حداکثر کمر ممکن برای راس چه می تواند باشد؟

قضیه

اگر باشد ثابت کنید گراف لااقل یک دور دارد.
اثبات
به سادگی از یک راس دلخواه شروع می کنیم و به دلخواه روی یکی از یالهای آن حرکت می‌کنیم پس از آن به هر راس که رسیدیم، یکی از یالهای غیر تکراری آن را بر می گزینیم و راه خود را ادامه می دهیم چون هر راس لااقل 2 یال دارد پس تا زمانی که به یک راس تکراری نرسیم،‌ این الگوریتم ادامه خواهد داشت و چون کل یالها متناهی می باشد پس حتماً الگوریتم پایان خواهد پذیرفت و یعنی به راس تکراری می رسیم و این یعنی وجود یک گشت بسته و این هم یعنی وجود لااقل یک دور.

قضیه

اگر باشد ثابت کنید دور آن لااقل طول دارد. (کوچکترین درجه می باشد)

لم 1

بزرگترین مسیر گراف فوق لااقل طول دارد.
اثبات
به برهان خلف.
فرض کنیم بزرگترین مسیر آن باشد را در نظر می گیریم،‌ چون لااقل درجه آن می باشد و تعداد رئوس این مسیر بجز خودش حداکثر می باشد پس به یک راس مانند از رئوس دیگر متصل است که در این صورت مسیر مسیر طولانی تری خواهد بود و این یعنی تناقض
حال به اثبات باز می گردیم،‌در گراف داده شده بزرگترین مسیر آن را در نظر می گیریم و فرض می‌کنیم به صورت باشد که ثابت کردیم ، حال راس را در نظر بگیرید،‌ نمی‌تواند به راسی بجز رئوس این مسیر یال داشته باشد چون مسیر طولانیتری ساخته خواهد شد (چرا؟ )
در داخل این رئوس نیز راسی مانند که باشد وجود خواهد داشت که به آن متصل است (چرا؟ ) حال دنباله دور به طولخواهد بود.



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

قضیه

فرض کنیم گراف ساده با باشد. اگر فرض کنیم دوری نداشته باشد ثابت کنید دارای یک راس از درجه 1 می باشد.
چون ساده است،‌هر مسیر آن متناهی است و بین تمام مسیرها این بار نیز بزرگترین مسیر آن را در نظر می گیریم. فرض کنیم یکی از رئوس انتهایی آن باشد،‌ چون این مسیر بزرگترین مسیر در می باشد پس تمام همسایه های باید در داخل مسیر باشند و گرنه مسیر بزرگتری بوجود خواهد آمد.
img/daneshnameh_up/1/13/mco0062c.jpg

از طرفی به هیچ یک از رئوس مسیر بجز راس قبلی آن نمی تواند یال داشته باشد چون دور بوجود می آید. پس ، الزاما‌ً درجه 1 خواهد بود.

تمرین

گراف ساده را در نظر بگیرید که دور ندارد. و دارای مولفه همبندی که هر مولفه لااقل 2 راس دارد. می باشد.
ثابت کنید لااقل راس درجه 1 دارد.
اثبات
در هر مولفه همبندی بزرگترین مسیر آن را در نظر می گیریم.
فرض می کنیم باشد چون این مسیر بزرگترین مسیر می باشد نه نه نمی توانند به هیچ کدام از رئوس بجز رئوس این مسیر متصل باشند از طرفی اگر به رئوس داخلی این مسیر هم متصل باشند دور بوجود می آید و این خلاف فرض است پس هر دو الزاماً‌ درجه 1 می باشند. پس به ازای هر مولفه لااقل 2 راس درجه 1 داریم پس جمعاً لااقل راس درجه 1 خواهیم داشت.
•ایده اکسترمال گیری به همین سادگی می باشد و لیکن کاربردهای فراوانی و شکل های متفاوتی دارد که براساس ابداع خود شما می باشد گاهی روی مسیر ماکسیمم بحث می کنید گاهی روی زیر گراف ماکسیممی که خصوصیت را داشته باشد یا دور ماکزیمم و یا ... در ادامه مباحث به نمونه های بسیاری از این دست خواهیم خورد.


•به طور کلی سه روش استقرا،‌ اکسترمال و برهان خلف پر کاربرد ترین روشهای اثبات در مسائل گراف می باشند.

قضیه

هر گراف با راس و یال دارای حداقل مولفه است.
اثبات
فرض کنیم تعداد مولفه ها باشد و تعداد یالها را هم با نمایش می دهیم ثابت کرده بودیم:

حال به برهان خلف اگر تعداد مولفه ها ) باشد آنگاه:


که 1 با 2 در تناقض می باشد لذا گراف حداقل مولفه دارد.

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

http://Olympiad.roshd.ir/computer/content/pdf/0094.pdf

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






تعداد بازدید ها: 17694


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..