- شروع کننده موضوع
- #1
erfan_ashorian
کاربر حرفه‌ای
- ارسال‌ها
- 397
- امتیاز
- 1,241
- نام مرکز سمپاد
- 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 یک کینگ است
(در حال لود شدن . . . )
همین الان دو تا ویژگی توپ داریم که بدیهیه فرض کنید راس های ۱ و۲ و .... n مدین اوردر باشن
الان داریم :
۱)هر تکه ای مثل : i , i+1 , i+2 , .... j خودشون به تنهایی یه median order از زیر تورنمنت راسی های i تا j اد
۲)هر راس مثله i به حداقل نصف راس های i+1 تا j یال جهت دار داره یعنی از i میریم به اونا!
خو بریم سوال :
۱)ثابت کنید هر تورنمنت با 2k راسی یک کپی از هر branching عهk+1راسی داره
۲)ثابت کنید راس ابتدایی هر median order یک کینگ است
(در حال لود شدن . . . )
