یک گراف کامل ۱۱ رأسی با رأس‌های ۰، ۱، … و ۱۰ داریم. روی یال بین رأس‌های $i$ و $j$ مقدار باقی‌مانده‌ی $i+j$ در تقسیم بر ۱۱ را نوشته‌ایم. عدد یک مسیر را کم‌ترین عدد در میان یال‌های آن مسیر می‌نامیم. دو رأس دل‌خواه در نظر بگیرید. بیشینه‌ی عدد مسیر را در میان مسیر‌های بین این دو رأس، میزان دوستی این دو رأس می‌نامیم. می‌خواهیم یک زیرگراف فراگیر از گراف داده شده انتخاب کنیم، طوری که میزان دوستی هر دو رأس در زیرگراف برابر با میزان دوستی‌شان در گراف اصلی باشد. کمینه‌ی ممکن مجموع اعداد یال‌های این زیرگراف چیست؟
پاسخ
گزینه (۳) درست است.
درخت پوشا با وزن بیشینه را در نظر بگیرید. این درخت می‌تواند با الگوریتمی شبیه الگوریتم کروسکال (اگر با آن آشنا نیستید، مطالعه کنید) به دست آید؛ به عبارتی کافی است یال‌ها را به جای از کم‌وزن به پروزن، از پروزن به کم‌وزن مرتّب و الگوریتم را اجرا کنیم. این درخت یک پاسخ برای مسئله است، زیرا به ازای هر دو رأس، عدد هر مسیری بین آن دو از عدد مسیرشان در درخت بیش‌تر نیست (اثبات مانند بهینگی الگوریتم کروسکال). از طرفی مجموع وزن یال‌های یک زیرگراف معتبر نمی‌تواند کم‌تر باشد، زیرا با مرتّب کردن یال‌ها از پروزن به کم‌وزن و بررسی آن‌ها به ترتیب مانند الگوریتم کروسکال، هرگاه یالی از یک وزن باید در درخت بیاید، سازنده‌ی عدد یک مسیر نیز هست و باید بیاید. پس پاسخ برابر مجموع وزن یال‌های این درخت یا همان ۹۵ است.