صفحه‌ها: ۱ ۲
قانونش اینه که بدون تلاقی بتونی روی یک صفحه رسمش کنی! احتمالاً کارهایی در این زمینه شده و ما بی‍خبریم
باید بتونید گراف رو سه بعدی تجسم کنید. یالها رو به صورت کش تصور کنید یالی که به یه سری راس وصله رو نمیشه از رئوس جدا کرد اما میشه همه رو با هم جابه جا مثل اون مثالی که حل شد.میخوام با مگنت مغناطیسی شبیه گرافها رو درست کنم ببینم روش خاصی واسه حل سر جلسه به ذهنم میشرسه یا نه؟!
یه راه حل کلی برای بررسی مسطح بودن یک گراف:
قضیه:در گراف ساده و همبند و مسطح اگر v>=3 باشد و کوهتاترین دور در گراف طولش برابر n باشد آنگاه [tex]\sum deg\left( Ri \right )= 2*e[/tex]
R:تعداد نواحی که یک گراف همبند ایجاد میکنه که طبق فرمول اویلر برابر است با:
R=E-v+2
توجه:جمع درجات نواحی برابر است با ۲e
با توجه به توضیحات بالا اگر نامعادله زیر برقرار باشه گراف مسطح و در غیر اینصورت غیر مسطح:
[tex]2*e\geq n*R[/tex]
بررسی گزینه های سوال علوم کامپیوتر ۸۲:
گزینه ۱: v=5 e=10 n=3 در نتیجه [tex]2\left( 10 \right )\geq 3\left( 10-5 2 \right )\Rightarrow 20\geq 21\Rightarrow no[/tex]
گزینه ۲: v=6 e=9 n=4 در نتیجه[tex]2\left( 9 \right )\geq 4\left( 9-6 2 \right )\Rightarrow 18\geq 20\Rightarrow no[/tex]
گزینه ۳: v=6 e=10 n=3 در نتیجه [tex]2\left( 10 \right )\geq 3\left( 10-6 2 \right )\Rightarrow 20\geq 18\Rightarrow yes[/tex]
گزینه ۴:v=6 e=12 n=3 و در نتیجه [tex]2\left( 12 \right )\geq 3\left( 12-6 2 \right )\Rightarrow 24\geq 24\Rightarrow yes[/tex]
شکل‌ها با توجه به پوران پس گزینه ۳ و ۴ درسته