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

حذف و انقباض

چاپ
علوم ریاضی > علو م رایانه



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


حذف و انقباض

همانطور که در قبل گفته شد گراف حاصل از گراف است که تنها یال از آن حذف شده باشد و مشابه آن گراف است که راس و تمام یالهای واقع بر آن حذف شده باشد.
اما انقباض یال الزاماً گرافی که زیر گراف هم باشد به ما نمی دهد زیرا در انقباض یال که به صورت نشان می دهیم، گراف حاصل گرافی است که در آن نه تنها یال حذف شده باشد بلکه دو انتهای آن یعنی را هم بر هم منطبق کرده باشیم. ( را یک راس می گیریم و هر یالی که به یکی از این دو متصل می شد را به این راس متصل می کنیم)
دقت کنید با انجام این عمل روی یک گراف ساده، آن گراف به یک گراف چند گانه تبدیل خواهد شد (چرا؟ ) که در این صورت گاهی در گراف حاصل از انقباض اگر ساده بودن آن اهمیت داشته باشد یالهای چندگانه احتمالی بوجود آمده را یکی فرض می کنند.
حال به نظر می آید این موضوع که الزاماً زیر گراف نمی باشد بدیهی تر به نظر بیاید. آیا شما می توانید در این زمینه مثالی بزنید؟

تعریف

انقباض از یک گرافرا انقباضی از می نامیم اگر با انقباض متوالی یالهایی از به وجود آمده باشد. واضح است اگر انقباضی از باشد آنگاه و
به عنوان نمونه انقباضی از گراف پترسن می باشد. زیرا کافی است در شکل زیر روی یالهای قرمز انقباض بزنید.
img/daneshnameh_up/3/32/mco0054a.jpg

به مثالهایی از حذف و انقباض رئوس و یالها و تفاوت آنها توجه کنید.
img/daneshnameh_up/9/97/mco0054b.jpg

img/daneshnameh_up/9/9d/mco0054c.jpg


پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0087.pdf

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





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


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