المپدیا

به ستاره‌ی $n$ راسی (درختی که درجه‌ی یک راس آن $n-1$ است) دقت کنید. به نظر شما چند سوال نیاز است تا مشخص کنیم درخت ستاره است؟

درختی مثل $T$ بیابید که برای تشخیص فرق ستاره و $T$ نیاز به حداقل $\lfloor \frac{n}{2} \rfloor$ پرسش داشته باشیم.

اگر ستاره‌ی $n-1$ راسی را در نظر بگیریم و یک راس به یکی از برگ‌های آن متصل کنیم، چند پرسش برای تشخیص تفاوت آن با ستاره‌ی $n$ راسی داریم؟

بنا به تعداد پرسش‌هایی که می‌توان انجام داد، خوب است یک راس را کنار بگذاریم و مابقی را به دسته‌های دو‌تایی افراز کنیم. اما چه افرازی می‌تواند درخت را برای ما مشخص کند؟ آن یک راس که قرار نیست در افراز بیاید کیست؟

شاید اگر درخت را از $centroid$ ریشه دار کنید، راحت‌تر بتوان به مسئله فکر کرد. ($centroid$ راسی از درخت است که با حذف آن از درخت $n$ راسی، تعداد راس‌های هر مولفه‌ی باقی‌مانده حداکثر $\frac{n}{2}$ باشد.)

خاصیت $centroid$ در این مسئله، چنین است که حال می‌توان هر راس از هر یک از زیردرخت‌های فرزندان $centroid$ را با یکی از رئوسی که در زیر‌درخت فرزند متفاوتی از آن قرار دارد، دسته بندی کرد و بدین صورت، راس‌ها به تعدادی زوج افراز خواهند شد.

از نتیجه‌ی این پرسش‌ها، آیا می‌توان تشخیص داد چه رئوسی برگ هستند؟

اگر برگ‌ها را نادیده بگیریم و باقی پاسخ‌ها را نگاه کنیم،‌ آیا می‌توان برگ‌های جدید را پیدا کرد؟

بنا بر راهنمایی ۵، امکان استفاده از استقرا وجود دارد؟

حال که اثبات انجام شده، به عنوان تمرین، آیا می‌توانید $centroid$ را از فرایند حل سوال کنار بگذارید؟