منو
 کاربر Online
942 کاربر online
تاریخچه ی: حذف و انقباض

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

Lines: 1-26Lines: 1-26
 ||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-e} {TEX} گراف است که تنها یال {TEX()} {e} {TEX}از آن حذف شده باشد و مشابه آن {TEX()} {G-V} {TEX} گراف {TEX()} {G} {TEX} است که راس{TEX()} {v} {TEX} و تمام یالهای واقع بر آن حذف شده باشد. همانطور که در قبل گفته شد گراف حاصل از{TEX()} {G-e} {TEX} گراف است که تنها یال {TEX()} {e} {TEX}از آن حذف شده باشد و مشابه آن {TEX()} {G-V} {TEX} گراف {TEX()} {G} {TEX} است که راس{TEX()} {v} {TEX} و تمام یالهای واقع بر آن حذف شده باشد.
 اما انقباض یال{TEX()} {e} {TEX} الزاماً گرافی که زیر گراف {TEX()} {G} {TEX} هم باشد به ما نمی دهد زیرا در انقباض یال {TEX()} {e=vw} {TEX} که به صورت{TEX()} {G\setminus e} {TEX} نشان می دهیم، گراف حاصل گرافی است که در آن نه تنها یال {TEX()} {e} {TEX} حذف شده باشد بلکه دو انتهای آن یعنی {TEX()} {w,v} {TEX} را هم بر هم منطبق کرده باشیم. ({TEX()} {w,v} {TEX} را یک راس می گیریم و هر یالی که به یکی از این دو متصل می شد را به این راس متصل می کنیم) اما انقباض یال{TEX()} {e} {TEX} الزاماً گرافی که زیر گراف {TEX()} {G} {TEX} هم باشد به ما نمی دهد زیرا در انقباض یال {TEX()} {e=vw} {TEX} که به صورت{TEX()} {G\setminus e} {TEX} نشان می دهیم، گراف حاصل گرافی است که در آن نه تنها یال {TEX()} {e} {TEX} حذف شده باشد بلکه دو انتهای آن یعنی {TEX()} {w,v} {TEX} را هم بر هم منطبق کرده باشیم. ({TEX()} {w,v} {TEX} را یک راس می گیریم و هر یالی که به یکی از این دو متصل می شد را به این راس متصل می کنیم)
 دقت کنید با انجام این عمل روی یک گراف ساده، آن گراف به یک ((گراف)) چند گانه تبدیل خواهد شد (چرا؟ ) که در این صورت گاهی در گراف حاصل از انقباض اگر ساده بودن آن اهمیت داشته باشد یالهای چندگانه احتمالی بوجود آمده را یکی فرض می کنند. دقت کنید با انجام این عمل روی یک گراف ساده، آن گراف به یک ((گراف)) چند گانه تبدیل خواهد شد (چرا؟ ) که در این صورت گاهی در گراف حاصل از انقباض اگر ساده بودن آن اهمیت داشته باشد یالهای چندگانه احتمالی بوجود آمده را یکی فرض می کنند.
 حال به نظر می آید این موضوع که {TEX()} {G\setminus e} {TEX} الزاماً زیر گراف{TEX()} {G} {TEX} نمی باشد بدیهی تر به نظر بیاید. آیا شما می توانید در این زمینه مثالی بزنید؟ حال به نظر می آید این موضوع که {TEX()} {G\setminus e} {TEX} الزاماً زیر گراف{TEX()} {G} {TEX} نمی باشد بدیهی تر به نظر بیاید. آیا شما می توانید در این زمینه مثالی بزنید؟
 --- ---
 !تعریف !تعریف
  انقباض از {TEX()} {G} {TEX}یک گراف{TEX()} {G^\prime} {TEX}را انقباضی از {TEX()} {G} {TEX}می نامیم اگر با انقباض متوالی یالهایی از{TEX()} {G} {TEX} به وجود آمده باشد. واضح است اگر {TEX()} {G^\prime} {TEX} انقباضی از {TEX()} {G} {TEX} باشد آنگاه{TEX()} {V(G^\prime ) <V(G)} {TEX} و{TEX()} {E(G^\prime )<E(G)} {TEX}   انقباض از {TEX()} {G} {TEX}یک گراف{TEX()} {G^\prime} {TEX}را انقباضی از {TEX()} {G} {TEX}می نامیم اگر با انقباض متوالی یالهایی از{TEX()} {G} {TEX} به وجود آمده باشد. واضح است اگر {TEX()} {G^\prime} {TEX} انقباضی از {TEX()} {G} {TEX} باشد آنگاه{TEX()} {V(G^\prime ) <V(G)} {TEX} و{TEX()} {E(G^\prime )<E(G)} {TEX}
 به عنوان نمونه {TEX()} {K_5} {TEX} انقباضی از ((گراف پترسن)) می باشد. زیرا کافی است در شکل زیر روی یالهای قرمز انقباض بزنید. به عنوان نمونه {TEX()} {K_5} {TEX} انقباضی از ((گراف پترسن)) می باشد. زیرا کافی است در شکل زیر روی یالهای قرمز انقباض بزنید.
 ::{picture=img/daneshnameh_up/3/32/mco0054a.jpg}:: ::{picture=img/daneshnameh_up/3/32/mco0054a.jpg}::
 به مثالهایی از حذف و انقباض رئوس و یالها و تفاوت آنها توجه کنید. به مثالهایی از حذف و انقباض رئوس و یالها و تفاوت آنها توجه کنید.
 ::{picture=img/daneshnameh_up/9/97/mco0054b.jpg}:: ::{picture=img/daneshnameh_up/9/97/mco0054b.jpg}::
 ::{picture=img/daneshnameh_up/9/9d/mco0054c.jpg}:: ::{picture=img/daneshnameh_up/9/9d/mco0054c.jpg}::
 --- ---
 ! پیوند های خارجی ! پیوند های خارجی
 [http://Olympiad.roshd.ir/computer/content/pdf/0087.pdf] [http://Olympiad.roshd.ir/computer/content/pdf/0087.pdf]
 --- ---
 !همچنین ببینید !همچنین ببینید
 *((اجتماع دو گراف )) *((اجتماع دو گراف ))
 *((اعمال اولیه )) *((اعمال اولیه ))
 #@^ #@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:33 ]   3   زینب معزی      جاری 
 یکشنبه 19 شهریور 1385 [10:39 ]   2   زینب معزی      v  c  d  s 
 یکشنبه 19 شهریور 1385 [06:26 ]   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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..