بیژن یک جهانگرد باسابقه است که برای گشت و گذار در کشورها روش مخصوصی دارد. او همیشه سفرش در یک کشور را از پایتخت آن شروع میکند و در انتهای سفر نیز به پایتخت باز میگردد. او دوست دارد علاوه بر سر زدن به همهی شهرهای یک کشور، از همهی جادههای آن نیز حداقل یکبار عبور کند. بیژن از آنجا که بودجهی محدودی دارد و چند بار عبور کردن از یک جاده برای او جذابیتی ندارد، میخواهد تعداد جادههایی که از آنها بیش از یکبار عبور میکند کمینه شود. هر کشور از تعدادی شهر و جاده تشکیل شده است. هر جاده دو شهر را به هم متصل میکند و دوطرفه است. در نقشهی یک کشور، شهرها به صورت دایرههای کوچک نمایش داده میشوند و شهر پایتخت دایرهی بزرگتری دارد. برای مثال، شکل زیر نقشهی یک کشور است که بیژن برای گشتن در آن، باید از حداقل یک جاده دو بار عبور کند.
بیژن میخواهد در اولین سفر امسالش به کشوری برود که نقشهاش به شکل زیر است. اگر او بخواهد با روش مخصوص خودش کل کشور را بگردد، از حداقل چند جاده باید بیش از یکبار عبور کند؟
پاسخ
گزینه (2) درست است.