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

نمایش گراف مسطح با خطوط راست

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



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


نمایش گراف مسطح با خطوط راست

گراف زیر یک گراف مسطح است. راه های متفاوتی برای رسم گراف زیر روی صفحه وجود دارند که هیچ دو یالی هم دیگر را قطع نکنند. مانند آنهایی که در شکل می بینید.
img/daneshnameh_up/3/34/mco0071a.jpg

اگر راس های یک گراف را نیز جابجا کنیم بعضی اوقات می توانیم نمایشی از گراف مسطح بسازیم که همه ی یالهای آن خطوط راست باشند مانند شکل زیر:
img/daneshnameh_up/9/95/mco0071b.jpg

در سالی 1936، واگنر اثبات کرد که چنین خاصیتی برای هر گراف مسطح وجود دارد. این نتیجه توسط فری نیز به طور مستقل اثبات شد. یعنی قضیه ی زیر برقرار است.

قضیه

هر گراف مسطح یک نمایش روی صفحه دارد به قسمی که هر یال آن یک خط راست است.
به چنین نمایشی – یعنی هر نمایش گراف که در آن یالها خطوطی راست اند،‌ یک نمایش گویند- به هر گرافی که نمایش داشته باشد یک گراف گوییم. در واقع واگنر ثابت کرد که هر گراف مسطح یک گراف است. وجه از گراف را محدب گوییم هر گاه بین هر دو نقطه داخل یا روی این وجه پاره خطی رسم کنیم،‌ پاره خط به طور کامل داخل وجه بیافتد. در شکل وجه های محدب و غیر محدب را می بینید:
اثبات
اثبات به استقرا روی تعداد راس های گراف صورت می پذیرد. پایه ی استقرا گراف است. براحتی برای و زیر گراف های آن دیده می شود که همگی هستند.
حال فرض کنید که گرافی با راس باشد که و همه ی گراف های با کمتر از راس باشند. اگر یک گراف ماکسیمال مسطح نباشد، به قدری به آن یال اضافه می کنیم که تبدیل به یک گراف ماکسیمال مسطح شود. پس می توان را گرافی ماکسیمال مسطح فرض کرد بدون اینکه از مساله چیزی کم شود. حال طبق قضیه گراف حداقل دارای 4 راس از درجه کوچکتر یا مساوی 5 است.
img/daneshnameh_up/8/89/mco0071c.jpg

همه ی درجه های گراف به دلیل ماکسیمال مسطح بودن،‌ از جمله وجه بیرونی گراف، به صورت مثلث اند. یعنی وجه بیرونی گراف سه راس دارد،‌ پس یکی از چهار راسی که حداکثر درجه آنها 5 می باشد روی این وجه نیست. این راس را می نامیم.
از آنجا که راس دارای درجه ای برابر با سه، چهار و یا پنج می باشد،‌ همان طور که در سطرهای اول و دوم در شکل زیر می بینید،‌این راس محل برخورد سه،‌ چهار و یا پنج مثلث است. حال گراف را در نظر گیرید (سطر سوم شکل ).
گراف مسطح است و تعداد راس های آن از کمتر است. یعنی طبق فرض استقرا ،، است همان گونه که در سطر چهارم شکل می بینید. پس را با خطوط راست روی صفحه رسم می کنیم که یک وجه ( همان وجهی که در سطر چهارم شکل مشخص شده ) به نام را شامل می شود و سه ضلعی،‌ چهار ضلعی و یا پنج ضلعی است- اگر یک شکل محدب باشد آن گاه راس را در داخل می کشیم و سپس یالهای حذف شده را نیز دوباره رسم می کنیم ( سطر پنجم شکل )- اما اگر محدب نباشد،‌ باید راس را در ناحیه ی هاشور خورده مشخص شده در سطر ششم شکل برای چهار ضلعی ها و سطرهای هفتم تا نهم شکل برای پنجم ضلعی ها انتخاب کنیم. استقرا کامل شده و حکم اثبات می گردد.
img/daneshnameh_up/d/d2/mco0071d.jpg

img/daneshnameh_up/a/a9/mco0071e.jpg

img/daneshnameh_up/b/bf/mco0071f.jpg

img/daneshnameh_up/a/a3/mco0071g.jpg


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

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

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



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


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