سوال ۱

فرض کنید گراف وزن‌دار $G$ با وزن یال‌های مثبت به ما داده شده است. به ازای یک راس $s$ به یک زیر درخت فراگیر در $G$، درخت کوتاه‌ترین مسیر یا SPST می‌گوییم، اگر وزن کوتاه‌ترین مسیر از $s$ به هر راس دیگری برابر با وزن مسیر $s$ به آن راس در ‍SPST باشد. در این سوال می‌خواهیم SPST و MST را با یک‌دیگر مقایسه کنیم. اگر خروجی یکی از این دو درخت اشتباها به جای دیگری به‌ کار رود حداکثر چه مقدار خطا ممکن است رخ دهد؟

دو تابع خطای $f$ و $g$ را به این شکل تعریف می‌کنیم:

• تابع $f(G)$ برابر است با حداکثر مجموع وزن یال‌های SPST، تقسیم بر مجموع وزن یال‌های MST. (خطای SPST هنگامی که به جای MST به کار رود)
• تابع $g(G)$ برابر است با حداکثر مجموع وزن مسیرهای از راس $s$ به بقیه رئوس در درخت MST تقسیم بر مجموع وزن مسیرهای از راس $s$ به بقیه رئوس در SPST. (خطای MST هنگامی که به جای SPST به کار رود)

1. از میان تمام گراف‌های $n$ راسی، گرافی که بیشترین $f(G)$ را دارد در نظر بگیرید. ثابت کنید $f(G)$ برای این گراف از $\Theta(n)$ است.
2. از میان تمام گراف‌های $n$ راسی، گرافی که بیشترین $g(G)$ را دارد در نظر بگیرید. ثابت کنید $g(G)$ برای این گراف از $\Theta(n)$ است.

• سوال بعد