تعریف عملی
همهٔ رأسها آمدهاند؟ هیچ رأس تکرار نشده؟ هر دو رأس پیاپی یال دارند؟ در دور، ابتدا و انتها مجاورند؟
۱. مسیر چهاررأسی
گراف با یالهای AB,BC,CD یک مسیر همیلتونی دارد؟
پاسخ
بله؛ A-B-C-D.
۲. دور مربع
یالهای AB,BC,CD,DA یک دور همیلتونی بساز.
پاسخ
A-B-C-D-A؛ چهار رأس پیش از بازگشت دقیقاً یک بار آمدهاند.
۳. ستاره چهاربرگ
گراف با مرکز O و یالهای OA,OB,OC,OD مسیر همیلتونی دارد؟
پاسخ
خیر؛ برای عبور میان بیش از دو برگ باید مرکز چند بار تکرار شود.
۴. مربع با قطر
یالهای AB,BC,CD,DA,AC هستند. یک مسیر همیلتونی متفاوت از دور پیرامونی بنویس.
پاسخ
B-A-C-D یک مسیر معتبر است.
۵. رأس درجه یک
اگر گراف یک رأس درجهٔ یک داشته باشد، آیا آن رأس میتواند در میانهٔ مسیر همیلتونی باشد؟
پاسخ
خیر؛ در میانه به دو یال مسیر نیاز دارد. اگر مسیر وجود داشته باشد، چنین رأسی باید یکی از دو سر باشد.
۶. دو رأس درجه یک
اگر گراف دقیقاً دو رأس درجهٔ یک دارد و مسیر همیلتونی موجود است، دو سر مسیر کداماند؟
پاسخ
همان دو رأس درجهٔ یک.
۷. دور و درجه یک
آیا گراف دارای رأس درجهٔ یک میتواند دور همیلتونی داشته باشد؟
پاسخ
خیر؛ هر رأس روی دور باید دو یال دور داشته باشد.
۸. تفاوت با اویلری
گراف مثلث با یک یال آویزان CD را در نظر بگیر: AB,BC,CA,CD. آیا مسیر همیلتونی دارد؟
پاسخ
بله؛ D-C-A-B یک مسیر همیلتونی است. معیار آن بازدید رأسهاست، حتی اگر همهٔ یالها مصرف نشوند.
خودتصحیح
| معیار | امتیاز |
|---|---|
| پوشش همهٔ رأسها | ۸ |
| عدم تکرار و مجاورت | ۸ |
| تفکیک مسیر و دور | ۴ |
فهرست مسیر را با فهرست رأسها خطبهخط تطبیق بده. درسنامه در راهنمای همیلتونی آمده است.