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

راس برشی و یال برشی و k - همبندی

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



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


راس برشی و یال برشی و همبندی

اکنون می خواهیم با مفاهیمی که بیان کننده میزان همبندی یک گراف می باشند آشنا شویم.
نخست راس و یال برشی را تعریف می کنیم.
یک راس برشی و یا یک یال برشی می باشد اگر با حذف آن راس یا یال،‌ تعداد مولفه های همبندی افزایش یابد.
مثلاً‌ در شکل مقابل برشی می باشند.
img/daneshnameh_up/5/55/mco0067a.jpg

نتیجه رئوس تنهای و رئوس درجه 1 برشی نمی باشند.

تعریف

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

تعریف

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

قضیه

هر گراف همبند با بیش از 2 راس که یک یال برشی داشته باشد لااقل یک راس برشی نیز دارد.
اثبات
فرض کنیم یال برشی مفروض باشد.
img/daneshnameh_up/e/ef/mco0067b.jpg

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



قضیه

یال یک یال برشی می باشد اگر و فقط اگر در هیچ مسیر موجود نباشد.
برهان خلف
اگر با مسیر دیگری بجز به هم متصل باشند همانطور که در شکل واضح است دیگر برشی نخواهد بود زیرا ارتباط بجز از مسیر دیگری نیز برقرار می باشد.
img/daneshnameh_up/7/7c/mco0067c.jpg


قضیه

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

قضیه

اگر راس برشی باشد ثابت کنید راس برشی نخواهد بود.
فرض می کنیم راس برشی هم هم باشد پس با حذف آن هم ناهمبند می شود هم پس هم به دو دسته افراز می گردد که هیچ یالی بین نیست هم رئوس به دو دسته افراز می گردد که هیچ یالی بین با وجود ندارد.
حال فرض کنید و
آنگاه که چنین چیزی ممکن نیست.
img/daneshnameh_up/b/b0/mco0067d.jpg


قضیه



هر گراف ساده همبند حداقل دو راس دارد که برشی نیستند.
اثبات
بزرگترین مسیر آن را در نظر می گیریم. ثابت می کنیم رئوس ابتدایی و انتهایی این مسیر برشی نیستند.
برهان خلفاگر یکی از آنها مثلاً‌ راس اول بزرگترین مسیر برشی باشد،پس لااقل به یکی از رئوس غیر از این دور مسیری داشته و این یعنی مسیری طولانیتر از مسیر بزرگترین فرض کرده وجود دارد و این یعنی تناقض.
img/daneshnameh_up/1/10/mco0067e.jpg

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

تعریف

گراف همبند یالی. گراف را همبند یالی گویند اگر لااقل یال باید از گراف حذف شوند تا گراف همبندی خود را از دست دهد.
به بیان دیگر،‌ تا کمتر از یال اگر به هر ترتیبی حذف کنیم همبندی بر هم نمی خورد.

مثال

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

مثال

ثابت کنید نمی تواند، همبند یالی باشد.
حل
به سادگی تمام یال منتهی به یک راس را حذف کنید. همبندی بر هم می خورد.

تعریف



گرافهمبند. مشابه قبل گرافرا همبند گویند اگر برای ناهمبند کردن آن لااقل راس باید از گراف حذف شوند.
به بیان دیگر به هر شکل که راس را از آن حذف کنیم همبندی پابرجا می ماند.

مثال

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

گرافهای 2- همبند

با مشخص ساختن گرافهای 2- همبند آغاز می کنیم. دو مسیر درونی مجزا هستند اگر هیچکدام شامل نقطه پایانی راسی از دیگری نباشد.

قضیه

یک گراف بیسوی که دارای حداقل سه راس باشد،‌ 2-همبند است اگر،‌ و فقط اگر، هر جفت به وسیله یک جفت مسیر درونی – مجزا در به هم وصل شوند.
اثبات
هنگامی که دارای مسیرهای درونی مجزا باشد،‌ حذف یک راس نمی تواند را از جدا کند. چون این مطلب برای هر جفت در نظر گرفته شده است،‌ از این رو شرط کافی است. برعکس،‌ فرض کنیم که ، 2- همبند است. با استقرا روی، ثابت می کنیم که دارای دو مسیر درونی – مجزا می باشد.
هنگامی که، گراف همبند است،‌زیرا
یک مسیر در درونی – مجزا در است که از مسیر متشکل از خود یال باشد.
برای گام استقرا،‌ را در نظر می گیریم و فرض کنیم که دارای مسیرهای درونی– مجزا می باشد، هر گاه فرض کنیم راس پیش از روی یک کوتاهترین مسیر باشد. داریم و از این رو بنابر فرض استقرا دارای مسیرهای درونی – مجزا است. چون همبند است،‌ شامل یک مسیر مانند است. اگر این مسیر از یا اجتناب کند،‌ به پایان کار رسیده ایم،‌ اما ممکن است در راسهای درونی با هر دوی شریک باشد. فرض کنیم آخرین راس از باشد که به متعلق است. بنابر تقارن،‌ می توانیم فرض کنیم . زیر مسیر از را با زیر مسیر از ترکیب می کنیم تا یک مسیر درونی- مجزا از به دست می آوریم.
img/daneshnameh_up/f/fa/mco0067f.jpg


لم. ( بسط لم )



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

قضیه

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



تعریف

زیر تقسیم یک یال از یک گراف بیسوی عبارت است از عمل حذف و افزودن یک مسیر میان یک راس جدید .
img/daneshnameh_up/a/ac/mco0067g.jpg

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


img/daneshnameh_up/9/93/mco0067h.jpg


قضیه

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

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

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




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


ارسال توضیح جدید
الزامی
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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..