• اگر سمپادی هستی همین الان عضو شو :
    ثبت نام عضویت

ایده های گراف

  • شروع کننده موضوع
  • #1

erfan_ashorian

کاربر حرفه‌ای
ارسال‌ها
396
امتیاز
1,235
نام مرکز سمپاد
2
شهر
تهران
دانشگاه
_ان شا الله قوزاباد
رشته دانشگاه
_علوم کامپیوتر(البته در این
یه چیزی هست به اسم median orderعاقا ایده خیلی سادست ببینید میایم راس های یه تورنمنت و جوری میچینیم به ترتیب که تعداد یال هایی که به عقب میان مینیمم بشن..یعنی تعداد یال های از چپ به راست ماکسیمم باشند
همین الان دو تا ویژگی توپ داریم که بدیهیه فرض کنید راس های ۱ و۲ و .... n مدین اوردر باشن
الان داریم :
۱)هر تکه ای مثل : i , i+1 , i+2 , .... j خودشون به تنهایی یه median order از زیر تورنمنت راسی های i تا j اد
۲)هر راس مثله i به حداقل نصف راس های i+1 تا j یال جهت دار داره یعنی از i میریم به اونا!


خو بریم سوال :
۱)ثابت کنید هر تورنمنت با 2k راسی یک کپی از هر branching عهk+1راسی داره
۲)ثابت کنید راس ابتدایی هر median order یک کینگ است


(در حال لود شدن . . . )
 

مهدی

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,110
امتیاز
7,342
نام مرکز سمپاد
علامه‌حلی
شهر
تهران
مدال المپیاد
کامپیوتر
دانشگاه
دانشگاه تهران. :دی
رشته دانشگاه
آمار. :دی
پاسخ : ایده های گراف

1- زشته بیاد مدیر انجمن جواب سوال رو بده بیاید این سوالو حل کنید :D
2- بعدش باز هم سوالات ایده خور میذاریم برای این تاپیک
 
بالا