درجات رئوس

[broslee]

منظور اشتباهاتی ست که ممکن است بعضی ها را به اشتباه بیندازد.وجود اشتباه در یک کتاب به معنی نقص آن نیست.در یک کتاب هزار تا تست هست پس ممکنه بعضی اشتباهات وجود داشته باشه.

1.گسسته / خیلی سبز / گراف . دنباله درجات رئوس ص 39 سوال 73

در گراف G
p=13
بزرگترین درجه = 8
کوچکترین درجه 2

است.گراف G حداکثر چند یال دارد؟

جواب خیلی سبز:
اگر شرط کوچکترین درجه برابر 2 نبود میگفتیم باید تمام درجه راس ها برابر 8 باشد تا به بیشترین اندازه برسیم.اما حتما یک راس درجه 2 لازم است.پس 12 تا درجه 8 و یک راس درجه 2 در نظر میگیریم. پس q=49


جواب من :
ابتدا گرافی که تمامی راس های آن درجه 8 هستند را در نظر میگیریم.گراف قابل قبول(ساده) است.

حال یک راس را به درجه 2 تبدیل میکنیم.بدین منظور باید 6 یال از یک راس برداریم (تا از 8 به 2 تبدیل شود).با این کار 6 راس به درجه 7 تبدیل میشوند.

حال 6 راس درجه 7 داریم
.... 6 راس درجه 8
.... 1 راس درجه 2

2q=92
q = 46

در این سوال خیلی سبز نکته ای حل کرده در حالی که ما راه حل رو رفتیم.
از این تیپ دو سه تا دیگه آورده اونارو هم اشتباه حل کرده. @sina @LeftBehind

[Phenotype_2]

میتونی نشون بدی گرافی از مرتبه 13 با 12 راس درجه 8 و ی راس درجه 2 وجود نداره؟ @broslee

[Phenotype_2]

میتونی نشون بدی گرافی از مرتبه 13 با 12 راس درجه 8 و ی راس درجه 2 وجود نداره؟ @broslee

همه گرافهای مرتبه 13 با 12 راس درجه 8 و ی راس درجه 2 در صورت وجود یک ریختن. این به این معنیه که من میتونم از دمباله درجات روس ی گراف یکی از جمله رو حزف کنم و به اندازه درجه اون راس، از همون تعداد راس 1 واحد کم کنم. اگه دمباله جدید بتونه دمباله درجات ی گراف باشه، پس گراف اولی هم وجود داره. پس روال تشخص گراف بودن اینه:
1. یه جمله دمباله رو حزف کنیم.
2. به تعداده درجه ای ک حزف کردید از، از جملات دلخاه دیگه 1 واحد کم کنید.
3. دو مرحله قبل رو انقت تکرار کنید ک به دمباله ساده ای برسید ک از وجود داشتن یا نداشتن گراف نظیرش مطین باشید.
4. از روی وجود داشتن یا نداشتن دمباله درجات مرحله 3، موجود بودن یا نبودن گراف اولیه رو نتیجه بگیرید.
فرض کنیم گرافی با 12 راس درجه 8 و ی راس درجه 2 وجود داره. پس باید دمباله زیر دمباله درجات ی گراف باشه
8،8،8،8،8،8،8،8،8،8،8،8،2
اگه من 4 راس درجه 8 اول رو حزف میکنم باید از 32 درجه از 9 راس باقی مانده کم کنم(از هر جمله حد اکثر 4 تا باید کم کنم چون 4 راس رو دارم حزف میکنم) میتونم این کار با کم کردن 4 واحد از 8 راس درجه 8 انجام بدم. پس میرسیم به دنباله:
4،4،4،4،4،4،4،4،2
اگه 4 راس درجه 4 اول رو حزف کنم باید 4 درجه از 4 راس دیگه کم کنم. میرسیم به دنباله:
2
واضحه که گرافی با 1 راس درجه 2 وجود نداره. پس گرافی با 12 راس درجه 8 و 1 راس درجه 2 وجود نداره.
در حالت کلی اگه بعدا از حزف جملات صفر به نباله 1،1 رسیدید، گراف اولیه وجود داره در غیر ان صورت گراف اولیه وجود نداره(با فرض اینکه دمباله اقلا ی راس درجه غیر صفر داره)

[صادق خان]

کتاب زیست الگو سال سوم .
تو فصل سه تو درسنامش گفته که در اون پروانه هه که روی شاخکاش گیرنده شیمیایی حساس به بوی جانور مادر داره
نر مادرو انتخاب میکنه
که اشتباهه