سلام
کسی میتونه این سوالات ریاضیات گسسته رو حل کنه ؟ :
۱- فرض کنید گراف G بی طوقه ، همبند و بی سو باشد. علاوه بر این فرض کنید G مسطح باشد و ۳۵ ناحیه ایجاد کند که هر ناحیه ای ۵ یال در مرز خود داشته باشد. ثابت کنید p>=82 است.
۲- ثابت کنید در هر گراف مسطح ، همبند ، بی طوقه ، راسی وجود دارد که درجه ی آن کمتر از ۶ است.
۳- فرض کنید گراف G همبند و بی طوقه باشد که در آن p=>11 است ، ثابت کنید یا G یا متمم G نا مسطح است.
مرسی
سلام.
۱- هر ناحیه حداقل ۵ یال در مرزش داره. هر یال هم فقط میتونه مرز بین ۲ ناحیه باشه. پس به ازای هر دو ناحیه حداقل ۵ یال داریم.
یه قضیه داریم (فکر کنم اویلر) که برای گرافهای مسطح همبند با استقرا ثابت میشه: v-e+r=2 یعنی تعداد رئوس منهای تعداد یالها بعلاوه تعداد نواحی برابر ۲ خواهد بود. با توجه به این دو رابطه داریم:
[tex]v-e r=2[/tex]
[tex]5\times r \leq 2\times e[/tex]
با جایگزینی نسبت ناحیه ها بجای یالها نتیجه میگیریم:
[tex]v-e \frac{2\times e}{5}\geq 2[/tex]
[tex]v\geq 2 \frac{3\times e}{5}[/tex]
باتوجه به مقدار r=35 حداقل مقدار e برابر ۸۸ میشه و تعداد رئوس بزرگتریا مساوی ۵۵ میشه. شاید یه جایی اشتباه داشتم. مطمئنید تعداد نواحی ۵۳ نبود؟
۲- اگه قرار باشه هیچ راسی با درجه حداقل ۵ نداشته باشیم با فرض اینکه تعداد رئوسمون برابر v باشه، مجموع تعداد یالهامون حداقل برابر ۳v میشه. یکی از قضایایی که میشه از رابطه اویلر اثبات کرد اینه که توی هر گراف مسطح ساده رابطه e<=3v-6 برقراره. با جایگزاری حداقل مقدار e در رابطه به تناقض میرسیم. پس در هر گراف همبند حتماً باید راس با درجه کوچکتر از ۶ داشته باشیم.
۳- از همون رابطه در سوال ۲ میشه استفاده کرد. مجموع یالهای گراف G و متممش میشه به اندازه تعداد یالهای گراف کامل یعنی [tex]\binom{11}{2}=55[/tex]. مسلماً یا G و یا متممش حداقل ۲۸ یال دارن. با قرار دادن مقدار e=28 در رابطه سوال ۲ به تناقض میرسیم. در نتیجه حداقل یکی از این دو گراف مسطح نیستن.
اگه توضیحات کافی نبود بیشتر توضیح بدم.