منو
 کاربر Online
527 کاربر online
تاریخچه ی: گرافهای بازه ای

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

Lines: 1-39Lines: 1-39
 ||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()} {S} {TEX} در آنجا اعداد حقیقی {TEX()} {R} {TEX} و به جای {TEX()} {C} {TEX}، تعدادی از بازه های اعداد حقیقی را قرار می دهیم. به این نوع گراف، گراف بازه ای می گوییم در بخش قبل با گرافهای اشتراکی آشنا شدید. حال به جای ((مجموعه)) ی {TEX()} {S} {TEX} در آنجا اعداد حقیقی {TEX()} {R} {TEX} و به جای {TEX()} {C} {TEX}، تعدادی از بازه های اعداد حقیقی را قرار می دهیم. به این نوع گراف، گراف بازه ای می گوییم
 ( یاد آوری: بازه ی{TEX()} {[a,b]} {TEX}، زیر مجموعه ای از {TEX()} {R} {TEX} است که: ( یاد آوری: بازه ی{TEX()} {[a,b]} {TEX}، زیر مجموعه ای از {TEX()} {R} {TEX} است که:
 {TEX()} {x \in [a,b] \Leftrightarrow a \le x \le b} {TEX} {TEX()} {x \in [a,b] \Leftrightarrow a \le x \le b} {TEX}
 بر خلاف گرافهای اشتراکی که برای هر گراف، یک ((گراف)) اشتراکی وجود داشت،‌ این امر برای گراف های بازه ای صادق نیست. یعنی گرافی می توان یافت که نتوان آن را به صورت یک گراف بازه ای تعریف کرد. پیدا کردن این گراف به صورت تمرین به عهده ی خواننده است. گراف {TEX()} {I} {TEX} که در زیر آمده مثالی از یک گراف بازه‌ای است: بر خلاف گرافهای اشتراکی که برای هر گراف، یک ((گراف)) اشتراکی وجود داشت،‌ این امر برای گراف های بازه ای صادق نیست. یعنی گرافی می توان یافت که نتوان آن را به صورت یک گراف بازه ای تعریف کرد. پیدا کردن این گراف به صورت تمرین به عهده ی خواننده است. گراف {TEX()} {I} {TEX} که در زیر آمده مثالی از یک گراف بازه‌ای است:
 ::{picture=img/daneshnameh_up/e/e6/mco0081a.jpg}:: ::{picture=img/daneshnameh_up/e/e6/mco0081a.jpg}::
 زیرا می توان فرض کرد که  زیرا می توان فرض کرد که
 ::{picture=img/daneshnameh_up/e/e2/mco0081b.jpg}:: ::{picture=img/daneshnameh_up/e/e2/mco0081b.jpg}::
 --- ---
 !!مثال !!مثال
 آیا گراف زیر می‌تواند یک گراف بازه ای باشد؟ آیا گراف زیر می‌تواند یک گراف بازه ای باشد؟
 ::{picture=img/daneshnameh_up/7/7c/mco0081c.jpg}:: ::{picture=img/daneshnameh_up/7/7c/mco0081c.jpg}::
 __حل__ __حل__
  برای جواب دادن به این سوال حالت کلی تر زیر را اثبات می کنیم.  برای جواب دادن به این سوال حالت کلی تر زیر را اثبات می کنیم.
 هر گراف که یک گراف القایی 4 راسی دوری داشته باشد نمی تواند بازه ای باشد. هر گراف که یک گراف القایی 4 راسی دوری داشته باشد نمی تواند بازه ای باشد.
 یعنی به بیان ساده تر در هر گراف اگر بتوان یک مربع ( چهار راسی که با چهار یال متوالیاً به هم وصل شده اند) یافت به قسمی که بین چهار راس آن بجز چهار یال مربع یال دیگری نباشد آن گراف الزاماً‌ نمی تواند بازه ای باشد. یعنی به بیان ساده تر در هر گراف اگر بتوان یک مربع ( چهار راسی که با چهار یال متوالیاً به هم وصل شده اند) یافت به قسمی که بین چهار راس آن بجز چهار یال مربع یال دیگری نباشد آن گراف الزاماً‌ نمی تواند بازه ای باشد.
 __اثبات__ __اثبات__
  چهار راس{TEX()} {u_4,u_3,u_2,u_1} {TEX} را در نظر بگیرید که با یالهای {TEX()} {e_4,e_3,e_2,e_1} {TEX} به شکل زیر به هم متصل شده اند.  چهار راس{TEX()} {u_4,u_3,u_2,u_1} {TEX} را در نظر بگیرید که با یالهای {TEX()} {e_4,e_3,e_2,e_1} {TEX} به شکل زیر به هم متصل شده اند.
 ::{picture=img/daneshnameh_up/2/2d/mco0081d.jpg}:: ::{picture=img/daneshnameh_up/2/2d/mco0081d.jpg}::
 به برهان خلف اگر این ((گراف)) بازه‌ای باشد داریم: به برهان خلف اگر این ((گراف)) بازه‌ای باشد داریم:
 بازه {TEX()} {u_1} {TEX} با {TEX()} {u_2} {TEX} اشتراک دارد پس شکلی مانند زیر دارند بازه {TEX()} {u_1} {TEX} با {TEX()} {u_2} {TEX} اشتراک دارد پس شکلی مانند زیر دارند
 ::{picture=img/daneshnameh_up/d/d8/mco0081e.jpg}:: ::{picture=img/daneshnameh_up/d/d8/mco0081e.jpg}::
 به طریق مشابه{TEX()} {u_3} {TEX} هم با {TEX()} {u_2} {TEX} اشتراک دارد ( به خاطر وجود یال{TEX()} {e_2=u_2u_3} {TEX} ) و از طرفی چون با{TEX()} {u_1} {TEX} یالی ندارد پس {TEX()} {u_3} {TEX} با {TEX()} {u_1} {TEX} اشتراکی ندارد. به طریق مشابه{TEX()} {u_3} {TEX} هم با {TEX()} {u_2} {TEX} اشتراک دارد ( به خاطر وجود یال{TEX()} {e_2=u_2u_3} {TEX} ) و از طرفی چون با{TEX()} {u_1} {TEX} یالی ندارد پس {TEX()} {u_3} {TEX} با {TEX()} {u_1} {TEX} اشتراکی ندارد.
 پس تنها حالتی که بتوان برای{TEX()} {u_3} {TEX} بازه ای فرض کرد که با بازه {TEX()} {u_2} {TEX} اشتراک داشته و با {TEX()} {u_1} {TEX} نداشته باشد به صورت زیر است پس تنها حالتی که بتوان برای{TEX()} {u_3} {TEX} بازه ای فرض کرد که با بازه {TEX()} {u_2} {TEX} اشتراک داشته و با {TEX()} {u_1} {TEX} نداشته باشد به صورت زیر است
 ::{picture=img/daneshnameh_up/9/97/mco0081f.jpg}::  ::{picture=img/daneshnameh_up/9/97/mco0081f.jpg}::
 حال نوبت پیدا کردن بازه {TEX()} {u_4} {TEX} است. دقت کنید{TEX()} {u_4} {TEX} هم به{TEX()} {u_1} {TEX} هم به {TEX()} {u_3} {TEX} یال دارد ولی به{TEX()} {u_2} {TEX} یالی ندارد پس باید بتوان در شکل بالا بازه ای برای آن یافت که هم با بازه{TEX()} {u_3} {TEX} ((اشتراک)) داشته باشد و هم با بازه {TEX()} {u_1} {TEX} اشتراک داشته باشد و از طرفی از محدوده بازه هم نگذرد! که واضح است چنین چیزی ممکن نیست. حال نوبت پیدا کردن بازه {TEX()} {u_4} {TEX} است. دقت کنید{TEX()} {u_4} {TEX} هم به{TEX()} {u_1} {TEX} هم به {TEX()} {u_3} {TEX} یال دارد ولی به{TEX()} {u_2} {TEX} یالی ندارد پس باید بتوان در شکل بالا بازه ای برای آن یافت که هم با بازه{TEX()} {u_3} {TEX} ((اشتراک)) داشته باشد و هم با بازه {TEX()} {u_1} {TEX} اشتراک داشته باشد و از طرفی از محدوده بازه هم نگذرد! که واضح است چنین چیزی ممکن نیست.
 لذا فرض باطل و ثابت می گردد که چهار راس{TEX()} {u_4,u_3,u_2,u_1} {TEX} نمی توانند بازه‌های مناسب اختیار کنند. لذا فرض باطل و ثابت می گردد که چهار راس{TEX()} {u_4,u_3,u_2,u_1} {TEX} نمی توانند بازه‌های مناسب اختیار کنند.
 --- ---
 ! پیوند های خارجی ! پیوند های خارجی
 [http://Olympiad.roshd.ir/computer/content/pdf/0075.pdf] [http://Olympiad.roshd.ir/computer/content/pdf/0075.pdf]
 --- ---
 !همچنین ببینید !همچنین ببینید
 *(( گرافهای دوبخشی )) *(( گرافهای دوبخشی ))
 *((گرافهای چندبخشی )) *((گرافهای چندبخشی ))
 #@^ #@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:28 ]   2   زینب معزی      جاری 
 یکشنبه 19 شهریور 1385 [12:39 ]   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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..