به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+1 امتیاز
1,147 بازدید
در دبیرستان و دانشگاه توسط OXIDE (681 امتیاز)
ویرایش شده توسط erfanm

ثابت کنید اگر در یک گراف ساده، دور به طول $m \geq 4$ بدون قطر وجود داشته باشد گراف بازه ای نیست.

گراف بازه ای گرافی است که راس ها با بازه های اعداد حقیقی برچسب گذاری شده اند به طوری که وجود یال بین دو راس معادل وجود اشتراک بین بازه ی متناظر آنهاست.

1 پاسخ

+1 امتیاز
توسط erfanm (13,866 امتیاز)

فرض کنید دورری به طول بیش از $3$ داشته باشیم که بدون کرد (قطر) باشد. لذا داریم: $( v_{1} , v_{2} , v_{3} ,..., v_{n} , v_{1} )$ از برهان خلف فرض میکنیم که این گراف گراف بازه ای باشد لذا بدون کاستن از کلیت میتوان فرض کرد که $v_{1} =(a,b) $و$v_{2} =(c,d) $و$ v_{3} =(e,f) $ حال از اینکه $ v_{1} =(a,b) $ و $v_{2} =(c,d) $ مجاور هستند لذا این دو بازه اشتراک دارند(دقت کنید که $(c,d) ‎\nsubseteq‎ (a,b) $ چون در غیر اینصورت از اشتراک $ v_{2} =(c,d) $و$ v_{3} =(e,f) $ نتیجه می شود که باید $ v_{1} =(a,b)$ با$ v_{3} =(e,f) $ مجاور باشد و لی قطر نداریم. بطور مشابه$(a,b) ‎\nsubseteq‎ (c,d)$ ) پس یا $a < c < b < d $ را داریم یا $c < a < d < b $

بدون کاستن از کلیت فرض $ a < c < b < d $ را داشته باشیم و با استدلالی مشابه بالا برای $v_{2} =(c,d) $و$ v_{3} =(e,f) $ یا $ c < e < d < f $ را داریم یا $ e < c < f < d $ اما با توجه به اینکه $ a < c < b < d $ بود بذا حالت $ e < c < f < d $ امکان پذیر نیست.وگرنه $v_{1} =(a,b) $با $v_{3} =(e,f) $ اشتراک خواهند داشت. پس با توجه به اشتراک نداشتن این دو در کل رابطه ی زیر برقرار خواهد بود $ a < c < b < e < d < f$ و با ادامه همین روند اگر $ v_{n} =(a_{0} , b_{0} ) $ آنگاه باید $ a < c < b < e < a_{0}$ یعنی $ v_{n} =(a_{0} , b_{0} ) $ با $ v_{1} =(a,b)$ نمیتواند اشتراک داشته باشد و این تناقض است.


حمایت مالی

کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...