آمار پرسش:
- پرسیده شده: 2019-07-22 11:31:49 -0600
- مشاهده شده: 678 بار
- بروز شده: 2022-05-04 08:42:26 -0600
پرسش‌های مشابه:
سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشته‌ی نزدیک
بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳
وزنه‌ها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳
گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳
انتقال مهره‌های گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳
یافتن کوچکترین پیچ و مهره با مقایسه آنها
دنباله و جادوگر - دوره ی 24 - مرحله ی 2
مسئله ی مسیر و شبکه - مرحله ی 2 – دوره ی 23
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
دور های مرتبط - مرحله ۲ سال ۱۳۹۶ - روز دوم - سوال چهارم
n یک عدد طبیعی بزرگ تر از 5 است
یک گراف n راسی داریم که هر دو دور آن دست کم در یک نقطه اشتراک دارند
بیشینه تعداد یال های این گراف را بدست آورید
2019-07-22 11:31:49 -0600
مرشد 336 ● 3 ● 3 ● 12
2 پاسخ
میایم کوچک ترین دور داخل گراف در نظر میگیریم ادعا میکنیم باید 3 باشه اول برسی کنیم اگه 3 باشه چی میشه
اگه کم ترین دور طولش 3 باشه میایم همه n - 3 تای باقی مونده رو به 3 ضلع دور وصل میگنیم بدیهیه که شکل ساخته شده تمام خاصیت های خواسته شده سوال رو داره
حالا میایم حساب میکنیم این شکل که ساختیم چند تا یال داره 3 * n - 3 میشه 3n-9 حالا 3 تا یال هم که از اول داشتیم میشه 3n-6 پس اگه کوتاه ترین دور 3 باشه جواب میشه
حالا فرض میکنیم کم ترین دور طولش k هست که k > 3 میایم میگیم از n - k راس باقی مونده هیچ کدوم به بیشتر از یکی از k تا وصل نیست چون اگه باشه دوری به طول کمتر از k میسازه و در فرض ما k > 3 کمترین دور هست
پس یعنی حد اکثر یال ها در اون حالت برابر
n - k + k + n - k = 2n - k
پس میشه گفت در حالتی که کوچک ترین دور 3 نباشه تعداد یال ها 2n - 4 هاست
از اونجایی که n > 5 پس 3n -6 > 2n - 4
پس اثبات میشه ماکسیمم یال ها 3n - 6 هست
2019-07-22 11:32:13 -0600
مرشد 336 ● 3 ● 3 ● 12
نظرات
فکر میکنم دور به طول ۴ رو باید جداگونه بررسی بشه چون هر کس از بیرون میتونه به دوتاش یال داشته باشه .
2022-05-04 08:42:26 -0600
محمدعرفان گونه 21 ● 1 ● 3 ● 5