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

تفاوت با نگارش: 2

Lines: 1-36Lines: 1-36
 ||V{maketoc}|| ||V{maketoc}||
-||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد یی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__|| +||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد کمپیو رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
 ^@#16: ^@#16:
 !همبندی !همبندی
 در اینجا می خواهیم مفاهیم و تعریف کلی همبندی را بیان کنیم. در اینجا می خواهیم مفاهیم و تعریف کلی همبندی را بیان کنیم.
 به طول کامل تر در مباحث بعدی به خصوصیات و کاربردها خواهیم پرداخت. به طول کامل تر در مباحث بعدی به خصوصیات و کاربردها خواهیم پرداخت.
 --- ---
 !تعریف !تعریف
 گراف {TEX()} {G} {TEX}را همبند نامیم اگر به ازای هر دو راس {TEX()} {v,u} {TEX} از آن مسیری ما بین {TEX()} {v,u} {TEX} وجود داشته باشد. ( به عبارت ساده تر بتوان از {TEX()} {v} {TEX} به {TEX()} {u} {TEX} رسید) گراف {TEX()} {G} {TEX}را همبند نامیم اگر به ازای هر دو راس {TEX()} {v,u} {TEX} از آن مسیری ما بین {TEX()} {v,u} {TEX} وجود داشته باشد. ( به عبارت ساده تر بتوان از {TEX()} {v} {TEX} به {TEX()} {u} {TEX} رسید)
 •همبندی یک رابطه هم ارزی می باشد ( چرا؟ خصوصیات روابط ((هم ارزی)) را درباره همبندی امتحان کنید ) •همبندی یک رابطه هم ارزی می باشد ( چرا؟ خصوصیات روابط ((هم ارزی)) را درباره همبندی امتحان کنید )
 لذا رئوس یک گراف دلخواه {TEX()} {G} {TEX} را به دسته های هم ارزی افراز می کند که اگر {TEX()} {v,u} {TEX} متعلق به یک دسته باشند مسیری میان آنها وجود خواهد داشت. لذا رئوس یک گراف دلخواه {TEX()} {G} {TEX} را به دسته های هم ارزی افراز می کند که اگر {TEX()} {v,u} {TEX} متعلق به یک دسته باشند مسیری میان آنها وجود خواهد داشت.
 زیر گراف های القایی مربوط به هر دسته هم ارزی را یک مولفه همبندی از((گراف)){TEX()} {G} {TEX}می نامیم. زیر گراف های القایی مربوط به هر دسته هم ارزی را یک مولفه همبندی از((گراف)){TEX()} {G} {TEX}می نامیم.
 به عبارت دیگر مولفه همبندی بخشی از گراف را که همبند باشد گویند به عبارت دیگر مولفه همبندی بخشی از گراف را که همبند باشد گویند
 مانند مثال زیر که 3 مولفه همبندی دارد. مانند مثال زیر که 3 مولفه همبندی دارد.
 ::{picture=img/daneshnameh_up/d/d0/mco0052a.jpg}:: ::{picture=img/daneshnameh_up/d/d0/mco0052a.jpg}::
 •گرافی که همبند باشد دقیقاً یک مولفه همبندی و گراف ناهمبند بیش از یک مولفه همبندی دارد. •گرافی که همبند باشد دقیقاً یک مولفه همبندی و گراف ناهمبند بیش از یک مولفه همبندی دارد.
 --- ---
 !تمرین !تمرین
  برای تسلط بیشتر ثابت کنید اگر {TEX()} {G} {TEX} ناهمبند باشد {TEX()} {\overline{G}} {TEX} همبند است.  برای تسلط بیشتر ثابت کنید اگر {TEX()} {G} {TEX} ناهمبند باشد {TEX()} {\overline{G}} {TEX} همبند است.
 این سوال در ابتدا شاید کمی سخت به نظر برسد ولیکن داریم: این سوال در ابتدا شاید کمی سخت به نظر برسد ولیکن داریم:
 چون {TEX()} {G} {TEX}ناهمبند است پس دو راس{TEX()} {v,u} {TEX} از آن وجود دارند که مسیری بین خود ندارند. چون {TEX()} {G} {TEX}ناهمبند است پس دو راس{TEX()} {v,u} {TEX} از آن وجود دارند که مسیری بین خود ندارند.
 پس به ازای هر راس دیگر مانند {TEX()} {w} {TEX} از رئوس {TEX()} {G} {TEX}، {TEX()} {w} {TEX} به حداکثر یکی از {TEX()} {v,u} {TEX}متصل است ( چرا؟ )  پس به ازای هر راس دیگر مانند {TEX()} {w} {TEX} از رئوس {TEX()} {G} {TEX}، {TEX()} {w} {TEX} به حداکثر یکی از {TEX()} {v,u} {TEX}متصل است ( چرا؟ )
 حال{TEX()} {\overline{G}} {TEX}را در نظر می گیریم و ثابت می کنیم تمام رئوس به {TEX()} {u} {TEX} متصل می باشند زیرا:  حال{TEX()} {\overline{G}} {TEX}را در نظر می گیریم و ثابت می کنیم تمام رئوس به {TEX()} {u} {TEX} متصل می باشند زیرا:
 ::||{picture=img/daneshnameh_up/6/68/mco0052b.jpg}:: ::||{picture=img/daneshnameh_up/6/68/mco0052b.jpg}::
 ::لااقل یکی از این دو متصل است||:: ::لااقل یکی از این دو متصل است||::
 ::|| {picture=img/daneshnameh_up/0/0f/mco0052c.jpg}::  ::|| {picture=img/daneshnameh_up/0/0f/mco0052c.jpg}::
 ::حداکثر یکی از این دو می‌تواند متصل باشد||:: ::حداکثر یکی از این دو می‌تواند متصل باشد||::
 اولاً چون در{TEX()} {uv\notin E} {TEX} نیست. پس در{TEX()} {\overline{G}} {TEX}، {TEX()} {u} {TEX} به{TEX()} {v} {TEX} متصل است. حال به ازای هر راس{TEX()} {w} {TEX}همانطور که  اولاً چون در{TEX()} {uv\notin E} {TEX} نیست. پس در{TEX()} {\overline{G}} {TEX}، {TEX()} {u} {TEX} به{TEX()} {v} {TEX} متصل است. حال به ازای هر راس{TEX()} {w} {TEX}همانطور که
 گفته شد حداکثر در {TEX()} {G} {TEX} می تواند به یکی از{TEX()} {u} {TEX} و{TEX()} {v} {TEX} متصل باشد و این یعنی در {TEX()} {\overline{G}} {TEX} لااقل به یکی از {TEX()} {v,u} {TEX} متصل است که خود {TEX()} {v,u} {TEX} هم به هم متصلند پس{TEX()} {w} {TEX} مسیری به طول حداکثر 2 به{TEX()} {u} {TEX} دارد. گفته شد حداکثر در {TEX()} {G} {TEX} می تواند به یکی از{TEX()} {u} {TEX} و{TEX()} {v} {TEX} متصل باشد و این یعنی در {TEX()} {\overline{G}} {TEX} لااقل به یکی از {TEX()} {v,u} {TEX} متصل است که خود {TEX()} {v,u} {TEX} هم به هم متصلند پس{TEX()} {w} {TEX} مسیری به طول حداکثر 2 به{TEX()} {u} {TEX} دارد.
 --- ---
 !همچنین ببینید !همچنین ببینید
 *((زیر گرافها )) *((زیر گرافها ))
 *((گرافهای یکریخت )) *((گرافهای یکریخت ))
 #@^ #@^

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