سوالم اینه که گراف مسطح رو چه طور میشه تشخیص داد؟ به غیر از اینکه ایزومورف با k3,3 باشه یا k5 ! بعضی وقت ها اینا جواب نمیده! چی کار میشه کرد؟
یکیش هم این :
۲v-4>=eباشه گراف مسطح هست اگر حداقل دورهاش برابر ۴باشه
مرسی از راهنماییتون
سلام. البته حالت کلیش همون بدست آوردن زیرگراف k3,3 یا k5 هست. این شروط، شرط کافی هستن. گرافهایی هستن که این رابطه نمیتونه تشخیص بده اونا مسطح نیستن.
یکی از نودهای یه درخت با ۱۰ راس رو به k5 وصل کنید. فرمول جواب نمیده.
(۲۵ دى ۱۳۹۱ ۰۱:۲۵ ق.ظ)Jooybari نوشته شده توسط: یکی از نودهای یه درخت با ۱۰ راس رو به k5 وصل کنید. فرمول جواب نمیده.درسته این فرمول ها جواب نمیده! اول باید بگردیم حداقل دور رو حساب کنیم. اما منظورتون رو نفهمیدم میشه بیشتر توضیح بدید؟
شرط لازم و کافی برای مسطح نبودن همون زیر گراف k3,3 و k5 هست. شرطهایی مثل v-e+d=2 و مشتقاتش شرط کافی هستن. اگه برقرار باشه مسطح نیست ولی اگه برقرار نباشه چیزی نمیتونیم بگیم.
دوستان من این نکته رو ندیده بودم
منظورش تعداد دور یا طول دور؟
آگه منظورتون v-e+d=2 هست منظور از d تعداد نواحیه. اگه قصد دارید از معادله این مقدار رو حذف کنید، به یه استدلال نیاز داریم: هر ناحیه بین حداقل ۳ یاله و هر یال مرز بین دو ناحیه میشه. یعنی ۲e<=3d با این استدلال مقدار d حذف شده و مساوی به نامساوی تبدیل میشه. اگه توی مسئله یه شرطی داشته باشیم که گرافمون هیچ دوری با طول کمتر از ۵ نداره میتونیم بگیم هر ناحیه بین حداقل ۵ یاله و هر یال مرز بین دو ناحیست و ۲e<=5d.