سوال

روباتی روی خطوط یک جدول 3×3 با خطوط افقی و عمودی حرکت میکند. طی کردن هر پاره خط به طول 1 افقی 1 ثانیه و هر پاره خط به طول 1 عمودی 2 ثانیه طول میکشد. میخواهیم روبات را به گونه ای برنامه ریزی کنیم که از یک نقطه شروع کنید , از روی تمامی پاره خط های جدول عبور کند (میتواند از مسیرهای تکراری هم عبور کند ) و به جای اولش برگردد. انجام این کار حداقل چند ثانیه طول میکشد ؟  (مثلا در شکل زیر طی کردن مسیر مشخص شده 5 ثانیه طول میکشد.)

پاسخ

تعداد پاره خط های افقی 12 و نیز تعداد پاره خط های عمودی نیز 12 میباشد بنابراین اگر از هر پاره خط  فقط یک بار عبور کنیم مدت زمان لازم  2 × 12 + 1 × 12 ؛ یعنی 36 خواهد بود. اما شرط لازم برای آن که بتوان یک گراف را بدون برداشتن قلم از روی کاغذ و با عبور از هر یال دقیقا یک بار چنان رسم کرد که نقطه پایان همان نقطه شروع باشد, آن است که درجه همه رئوس  آن زوج باشد که در گراف رسم شده درجه 8 راس ؛ یعنی رئوس B , C , E , H , I , L , N و O فرد بوده و به ازای هر دو راس فرد که به یکدیگر وصل هستند

یک حرکت اضافی لازم است. اگر حرکت به صورت زیر باشد , مدت زمان لازم 42 ثانیه خواهد بود.

A - B - F - G - C - B - C - D - H - G - K - L - H - L - P - O - K - J - N - O - N - M - I - J - F - E - I - E - A