آمار پرسش:
- پرسیده شده: 2019-04-25 11:31:16 -0600
- مشاهده شده: 518 بار
- بروز شده: 2019-04-25 11:54:50 -0600
پرسش‌های مشابه:
سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشته‌ی نزدیک
بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳
وزنه‌ها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳
گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳
انتقال مهره‌های گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳
یافتن کوچکترین پیچ و مهره با مقایسه آنها
دنباله و جادوگر - دوره ی 24 - مرحله ی 2
مسئله ی مسیر و شبکه - مرحله ی 2 – دوره ی 23
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
هدیه معین - مرحله ۲ سال ۱397 - روز دوم - سوال 1
سوال اول تشریحی سال 1397 روز دوم هدیه ی معین
متن سوال:
2019-04-25 11:31:16 -0600
صفر و یک 979 ● 8 ● 15 ● 20
1 پاسخ
برای این سوال میشه گفت برای اینکه یال های گراف زیاده بیایم و گراف مکملشو بررسی کنیم
اول میگیم که چون درجات گراف کامل فرده پس اگه بخوایم یه راه برای فرد کردن گراف وجود داشته باشه اون حالته که مجبور باشیم به گراف کامل برسونیمش
حالا گراف مکمل رو که ببینیم میخوایم از یه گراف(گراف مطلوبی که مکملش جوابه و اسمشو میذاریم G :) ) با تعدادی یال یه سری یال حذف کنیم که هیچ یالی از گراف باقی نمونه و درطی حذف کردن درجه هر راس گراف زوج نشه
لم:در گراف G دور نداریم
فرض خلف میکنیم که داریم ؛ و میدونیم که در طی حذف کردن یالهای G به گرافی نرسیدیم که هر راسش درجه زوج داشته باشه
حالا اگه یه دور رو در نظر بگیریم میشه اون دور رو حذف کرد و به گرافی رسید که همه درجاتش زوجه که تناقضه چون میدونیم گراف بعدی که درجاتش زوجه گرافیه که 0 یال داره
پس حداکثر یالهاش n-1 هست که گراف مکملش میشه انتخاب 2 از n-1 :)))))
2019-04-25 11:52:07 -0600
صفر و یک 979 ● 8 ● 15 ● 20
نظرات