تاریخچه ی:
همبندی
تفاوت با نگارش: 2
| | ||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} دارد. |
| | --- | | --- |
| | !همچنین ببینید | | !همچنین ببینید |
| | *((زیر گرافها )) | | *((زیر گرافها )) |
| | *((گرافهای یکریخت )) | | *((گرافهای یکریخت )) |
| | #@^ | | #@^ |
