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

همبندی

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



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


همبندی

در اینجا می خواهیم مفاهیم و تعریف کلی همبندی را بیان کنیم.
به طول کامل تر در مباحث بعدی به خصوصیات و کاربردها خواهیم پرداخت.

تعریف

گراف را همبند نامیم اگر به ازای هر دو راس از آن مسیری ما بین وجود داشته باشد. ( به عبارت ساده تر بتوان از به رسید)
•همبندی یک رابطه هم ارزی می باشد ( چرا؟ خصوصیات روابط هم ارزی را درباره همبندی امتحان کنید )
لذا رئوس یک گراف دلخواه را به دسته های هم ارزی افراز می کند که اگر متعلق به یک دسته باشند مسیری میان آنها وجود خواهد داشت.
زیر گراف های القایی مربوط به هر دسته هم ارزی را یک مولفه همبندی ازگرافمی نامیم.
به عبارت دیگر مولفه همبندی بخشی از گراف را که همبند باشد گویند
مانند مثال زیر که 3 مولفه همبندی دارد.
img/daneshnameh_up/d/d0/mco0052a.jpg

•گرافی که همبند باشد دقیقاً یک مولفه همبندی و گراف ناهمبند بیش از یک مولفه همبندی دارد.

تمرین

برای تسلط بیشتر ثابت کنید اگر ناهمبند باشد همبند است.
این سوال در ابتدا شاید کمی سخت به نظر برسد ولیکن داریم:
چون ناهمبند است پس دو راس از آن وجود دارند که مسیری بین خود ندارند.
پس به ازای هر راس دیگر مانند از رئوس ، به حداکثر یکی از متصل است ( چرا؟ )
حالرا در نظر می گیریم و ثابت می کنیم تمام رئوس به متصل می باشند زیرا:
img/daneshnameh_up/6/68/mco0052b.jpg
لااقل یکی از این دو متصل است

img/daneshnameh_up/0/0f/mco0052c.jpg
حداکثر یکی از این دو می‌تواند متصل باشد

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

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





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


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