سلام

ادعا: برای هر درخت $n$ رأسی به $n-2$ مرحله نیاز داریم.

برای $n=3$ که واضحه.

حالا بیاید فرض کنید ادعای من غلط باشه و برای بعضی $n$ بشه با کمتر از $n-2$ مرحله درخت رو به طور کامل تشخیص داد.

کوچکترین $n$ که این جوری باشه را در نظر بگیرید.

در تشخیص درخت برای اولین مرحله هیچ استراتژی‌ای وجود نداره! شما دو رأس $u$ و $v$ به دلخواه انتخاب می‌کنید. بعد ممکنه که یکی از این دو تا رأس $(u)$ برگ باشه و رأس دیگر $(v)$ همسایه آن برگ! در این حالت تحلیل جوابی که دستگاه می‌دهد این است:

1. $u$ یک برگ است و با $v$ همسایه است.
2. با حذف $u$، بقیه رئوس یک درخت $n-1$ رأسی تشکیل می‌دهند که هیچ اطلاعات بیشتری در مورد آن نداریم. دقت کنید که هیچ اطلاعاتی نداریم!

حالا مطابق فرضی که داشتیم می‌توانیم با $n-۴$ مرحله دیگر درخت اصلی را تشخیص بدهیم.

ادعا: حضور یا عدم حضور $u$ در این مراحل هیچ تأثیری ندارد:

1. در هر مرحله ورودی $v$ و $k$ همهٔ اطلاعاتی که ورودی $u$ و $k$ به ما می‌دهد را می‌دهد.
2. در مجموعه رئوسی که دستگاه اعلام می‌کند همیشه $u$ هست اگر و تنها اگر $v$ باشد. پس حضور $u$ هیچ اطلاع خاصی به ما نمی‌دهد.

در نتیجه تونستیم در $n-4$ مرحله درخت $n-1$ رأسی را تشخیص بدیم که تناقضه.

پس ادعای اول من درسته!

الگوریتم با حداقل 1400 حرکت که درخت رو تشخیص داد : لم1 : اگر یه درخت n راسی داشته باشیم و ریشه ش رو هم بدونیم , با n-2 جرکت درخت پیدا می شه . اثبات : فرض کنید راس ریشه شمارش 1 و بقیه راس ها 2 و 3 و .....و n هستن راس 1 رو با تمام n-1 راس دیگه به جز راس با شماره n با دستگاه چک می کنیم فرض کنبید راس 1 رو با i زدیم َ#می تونین بفهمیم چه راس هایی توی زیر درخت i قرار گرفتن و چه راس هایی بین iو1 ان ( اشتراک جواب های 1وi می شه راس های بینشون ) فر ض کنید راس n اصلا وجود نداره یعنی از هر جوابی که n توش هست , n رو ازش حذف کنید ( فرض کنید پدر n شمارش p هست) یه درخت n-1 راسی در میاد حالا تمام رعوسی که n توی جوابشون تومده بود رو در نظر بگیرید با استفاده از # می شه فهمید که توی جواب چه راس هایی راس n بین اون رعوس و 1 بوده یا زیر درختی از اون راس شکل یه مسیر می شه که اخرش می شه چندتا تا درخت با استدلال های ریز به این نتیجه می شه راس n اونجایی قرار داره که این مسیر به چندتا درخت افراز می شه پس فهمیدیم n هم کجا درخت بوده پس کل درخت بدست اومد , لم1 اثبات شد ....................................................................................................................................................................................................................................................................................................................................................................................................... استقرا می زنیم , برای درخت کمتر مساوری n-1 راس فرض می کنیم با n-3 می شه برای n راسی و n-2 حرکت اثبات می کنیم برای مسعله دوتا راس رندم مثل 1 و 2 رو با هم چک کنین سه دسته راس بدست میاد , بین 1 و 2 , زیر درخت 1 یا زیردرخت 2 فرض کنید سایز هاشون به ترتیب x , y , z ( ایکس برای بین 1و2 ) طبق لم1 و # می دونیم چه راس هایی توی زیر درخت 1 قرار دارن و با y-1 حرکت بدست میان همینطور برای زیر درخت 2 و z-1 حرکت
رعوس بین 1و2 همه همنبد اند (چرا؟) پس درختش با x-2 حرکت در میاد(فرض استقرا) + 2 حرکت که 1و2 کجا این درختن مجموعا تمام حرکاتمون شد : x + y + z و چونکه x + y + z = n-2 درخت به صورت کامل یافت شد