سوال سوم (۴۸ نمره)
درخت ۱۴۰۳ رأسی $T$ را در نظر بگیرید که درجهی هر رأس در آن، حداکثر ۳ است. البرز و بیتا میخواهند روی این درخت، یک بازی انجام دهند، به این صورت که البرز یکی از رأسهای درخت $T$ به نام $u$ را مخفیانه انتخاب میکند و بیتا باید این رأس را پیدا کند. در این بازی، بیتا میتواند تنها یک پرسش از البرز انجام دهد، به این شکل که دنبالهای از رأسها مانند $\langle v_1, v_2, \dots, v_k \rangle$ را انتخاب کند و بهصورت یکجا به البرز بدهد. البرز نیز در پاسخ به او، اطلاعاتی را در قالب $k$ جمله به شکل زیر ارائه میدهد:
| جملات البرز |
|---|
| فاصله بین $u$ و $v_1$ برابر $d_1$ است. |
| فاصله بین $u$ و $v_2$ برابر $d_2$ است. |
| $\vdots$ |
| فاصله بین $u$ و $v_k$ برابر $d_k$ است. |
لازم به یادآوری است که فاصله بین دو رأس در یک گراف، تعداد یالهای کوتاهترین مسیر میان آن دو رأس است. همچنین، توجه نمایید که تنها چیزی که بیتا نمیداند، رأس $u$ است، و او نیز مانند البرز، از ساختار درخت $T$ اطلاع کامل دارد. بر همین اساس، بیتا برای طراحی پرسش خود از البرز، الگوریتم زیر را ابداع کرده است:
- درخت $T$ را از یکی از برگهایش (یکی از رأسهای با درجهی یک) که آن را ریشه مینامیم، آویزان میکنیم.
- با آویزان شدن درخت از ریشه، تعاریف زیر را داریم:
- ریشه در بالاترین سطح قرار داده میشود و رأسهای دیگر، متناسب با فاصله از ریشه، در سطحهای پایینتر قرار میگیرند.
- رأس $y$ را جدّ رأس $x$ مینامیم اگر مسیر ریشه به $x$، رأس $y$ را نیز شامل شود.
- رأس $y$ را فرزند رأس $x$ مینامیم اگر $y$ با $x$ مجاور باشد ولی جدّ $x$ نباشد (با توجه به کران بالای ۳ برای درجهی رأسهای $T$، هر رأس حداکثر دو فرزند دارد).
- به رأسی که دقیقاً دو فرزند دارد، دوشاخه میگوییم.
- یک رأس دوشاخه را ساده مینامیم اگر جدّ هیچ رأس دوشاخهی دیگری نباشد.
- رأس ریشه را رنگ میکنیم.
- تمامی رأسهای دوشاخهی ساده در درختِ آویزانشده را پیدا میکنیم.
- بهازای هر رأس دوشاخهی ساده، دقیقاً یکی از دو فرزندش را به دلخواه، انتخاب و آن را رنگ میکنیم.
- رأسهای رنگشده را به عنوان پرسش $\langle v_1, v_2, \dots, v_k \rangle$ به البرز میدهیم.
به عنوان مثال، شکل زیر درختی ۷ رأسی را نشان میدهد که از رأس ۱ آویزان شده است. با این شرایط، رأسهای ۲ و ۳ (که با دو دایره مشخص شدهاند)، رأسهایی دوشاخه هستند. رأس ۳ یک رأس دوشاخهی ساده است، چرا که بهجز خودش، هیچ یک از رأسهایی که جدشان است (رأسهای ۵، ۶ و ۷)، دوشاخه نیستند؛ ولی رأس ۲ یک رأس دوشاخهی ساده نیست، چون جدّ رأس دوشاخهی ۳ است. بنابراین، خروجی الگوریتم بیتا در این مثال، یکی از دنبالههای $\langle 1, 5 \rangle$ یا $\langle 1, 6 \rangle$ خواهد بود و در نتیجه، دنبالهی خروجی الگوریتم بیتا در این مثال دقیقاً ۲ رأس خواهد داشت.
- الف) ثابت کنید دنبالهی خروجی الگوریتم بیتا، حداکثر ۳۵۱ رأس دارد. (۱۶ امتیاز)
- ب) ثابت کنید که بهازای هر درخت $T$ (درختی ۱۴۰۳ رأسی که درجهی رأسهای آن، حداکثر ۳ باشد)، اگر بیتا الگوریتم خود را روی درخت $T$ اجرا کند و خروجی آن را به عنوان پرسش، به البرز دهد، همواره میتواند رأس $u$ را بر اساس پاسخ البرز پیدا کند. (۱۶ امتیاز)
- ج) یک درخت $T$ (درختی ۱۴۰۳ رأسی که درجهی رأسهای آن، حداکثر ۳ باشد) مثال بزنید که برای آن، هیچ پرسشی با اندازهی حداکثر ۳۵۰ رأس وجود نداشته باشد که همواره با جواب آن پرسش، بتوان رأس $u$ را با قطعیت پیدا کرد. (۱۶ امتیاز)