گراف ساده و وزن‌دار ‎$G=(V,E)$‎ را در نظر بگیرید. وزن همه‌ی یال‌های این گراف نامنفی است. می‌دانیم که ‎$M$‎ زیردرختی فراگیر با کم‌ترین وزن در این گراف است. هم‌چنین می‌دانیم که ‎$P$‎ کوتاه‌ترین مسیر بین دو رأس ‎$u$‎ و ‎$v$‎ است.

حالا فرض کنید که به جای وزن هر یال، مجذورِ وزن آن را قرار می‌دهیم؛ مثلاً، اگر وزن یالی ‎$3$‎ بوده وزن آن را ‎$9$‎ می‌کنیم. به هر یک از دو سؤال زیر پاسخ دهید.

1. آیا در گراف جدید، همان ‎$P$‎ قبلی لزوماً کوتاه‌ترین مسیر بین ‎$u$‎ و ‎$v$‎ است؟
2. آیا در گراف جدید، همان ‎$M$‎ قبلی لزوماً زیردرخت فراگیر با کمترین وزن است؟

‎ در هر مورد، اگر جواب مثبت است آن را اثبات کنید و اگر جواب منفی است یک مثال نقض ارائه کنید.

• سوال بعد
• سوال قبل