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

گرافهای بازه ای

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)



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


گراف های بازه ای

در بخش قبل با گرافهای اشتراکی آشنا شدید. حال به جای مجموعه ی در آنجا اعداد حقیقی و به جای ، تعدادی از بازه های اعداد حقیقی را قرار می دهیم. به این نوع گراف، گراف بازه ای می گوییم
( یاد آوری: بازه ی، زیر مجموعه ای از است که:

بر خلاف گرافهای اشتراکی که برای هر گراف، یک گراف اشتراکی وجود داشت،‌ این امر برای گراف های بازه ای صادق نیست. یعنی گرافی می توان یافت که نتوان آن را به صورت یک گراف بازه ای تعریف کرد. پیدا کردن این گراف به صورت تمرین به عهده ی خواننده است. گراف که در زیر آمده مثالی از یک گراف بازه‌ای است:
img/daneshnameh_up/e/e6/mco0081a.jpg

زیرا می توان فرض کرد که
img/daneshnameh_up/e/e2/mco0081b.jpg


مثال

آیا گراف زیر می‌تواند یک گراف بازه ای باشد؟
img/daneshnameh_up/7/7c/mco0081c.jpg

حل
برای جواب دادن به این سوال حالت کلی تر زیر را اثبات می کنیم.
هر گراف که یک گراف القایی 4 راسی دوری داشته باشد نمی تواند بازه ای باشد.
یعنی به بیان ساده تر در هر گراف اگر بتوان یک مربع ( چهار راسی که با چهار یال متوالیاً به هم وصل شده اند) یافت به قسمی که بین چهار راس آن بجز چهار یال مربع یال دیگری نباشد آن گراف الزاماً‌ نمی تواند بازه ای باشد.
اثبات
چهار راس را در نظر بگیرید که با یالهای به شکل زیر به هم متصل شده اند.
img/daneshnameh_up/2/2d/mco0081d.jpg

به برهان خلف اگر این گراف بازه‌ای باشد داریم:
بازه با اشتراک دارد پس شکلی مانند زیر دارند
img/daneshnameh_up/d/d8/mco0081e.jpg

به طریق مشابه هم با اشتراک دارد ( به خاطر وجود یال ) و از طرفی چون با یالی ندارد پس با اشتراکی ندارد.
پس تنها حالتی که بتوان برای بازه ای فرض کرد که با بازه اشتراک داشته و با نداشته باشد به صورت زیر است
img/daneshnameh_up/9/97/mco0081f.jpg

حال نوبت پیدا کردن بازه است. دقت کنید هم به هم به یال دارد ولی به یالی ندارد پس باید بتوان در شکل بالا بازه ای برای آن یافت که هم با بازه اشتراک داشته باشد و هم با بازه اشتراک داشته باشد و از طرفی از محدوده بازه هم نگذرد! که واضح است چنین چیزی ممکن نیست.
لذا فرض باطل و ثابت می گردد که چهار راس نمی توانند بازه‌های مناسب اختیار کنند.

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

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

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




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


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