منظور از غیر مستقیم چیه؟ اگه من با ۳ واسطه یک نفر رو برده باشم غیر مستقیم حساب میشه؟
2014-06-10 05:23:17 -0600 فامیل دورآمار پرسش:
- پرسیده شده: 2014-06-10 04:55:39 -0600
- مشاهده شده: 264 بار
- بروز شده: 2014-06-10 05:57:31 -0600
پرسش‌های مشابه:
پیدا کردن گراف دوبخشی کامل یکرنگ
حداکثر تعداد یال‌های گراف بدون مثلث
اثبات همبند بودن مکمل گراف ناهمبند
همه را با تلفن خبر کنید - دوره ی 05 - مرحله ی 1
رنگ‌آمیزی صفحه بخش‌بندی شده توسط دایره‌ها با دو رنگ
پیدا کردن مولفه های قویا همبند گراف جهت دار
انگور، آن هم از نوع «درختی» - آزمون دوم آزمایشی شاززز
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
شرط وجود 2 کینگ در گراف کامل جهت دار
در سری مسابقات فوتبال دهه فجر ما تعدادی تیم با هم به رقابت پرداختند، در این مسابقات امکان تساوی وجود نداشت و همه ی تیم ها با هم مسابقه دادند. در پایان بازی ها هیچ یک از تیم ها همه ی تیم های رقیب را نبرده بود ثابت کنید در این صورت حداقل 2 تیم هستند که بقیه تیم ها را یا به طور مستقیم یا به طور غیر مستقیم برده اند.
به بیان دیگر: ثابت کنید اگر در گراف کامل جهت دار کینگ همه را به طور مستقیم نبرده باشد حتما حداقل 2 کینگ داریم.
2014-06-10 04:55:39 -0600
عقب مونده 189 ● 4 ● 8 ● 17
نظرات
1 پاسخ
فرض كنيد در گراف هيچ راسي همه را نبرده باشد. حال بديهي است كه گراف كينگ دارد . يكي از كينگ ها را در نظر بگيريد. ثابت ميكنيم حداقل يك كينگ ديگر هم داريم.
مجموعه راس هايي كه از كينگ برده اند را در نظر بگيريد. طبق فرض مساله اين گراف ناتهي است.پس كينگ دارد. ثابت ميكنيم اين راس كينگ گراف اصلي هم هست كه حكم مساله را نتيجه ميدهد.
اما اين هم بديهي است چرا كه اين راس از كينگ ديگر برده، پس از همه كساني كه كينگ آنها را برده با دو فاصله برده. از طرفي چون در مجموعه كساني كه كينگ ديگر را برده اند كينگ است پس در اين مجموعه هم همه را با حداكثر دو فاصله برده پس طبق تعريف كينگ اين راس هم كينگ است پس دو كينگ داريم.
2014-06-10 05:25:54 -0600
ابر لرد 288 ● 5 ● 12 ● 22