منو
 کاربر Online
847 کاربر online
تاریخچه ی: همبندی

نگارش: 2



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


همبندی

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

تعریف

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

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

تمرین

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

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

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

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






تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:24 ]   3   زینب معزی      جاری 
 یکشنبه 19 شهریور 1385 [10:26 ]   2   زینب معزی      v  c  d  s 
 یکشنبه 19 شهریور 1385 [06:23 ]   1   زینب معزی      v  c  d  s 


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