مسئله پستچی چینی

نمونه گرافی برای درک بهتر راه حل مسئله پستچی چینی

مسئله پستچی چینی نخستین بار از سوی ریاضیدان چینی به نام Mei Ko Kwan در سال ۱۹۶۰ طرح شد. یک پستچی می‌خواهد تمامی نامه‌ها را به مقصد آنها برساند؛ در حالی که مسافت طی‌شده کمینه باشد و بعد از پایان کار به نقطه آغاز برگردد. در این کار، باید هر خیابان را حداقل یک‌بار طی کند و اگر مجبور شود که از مسیری دوبار عبور کند، باید مسیری با کوتاه‌ترین مسافت را انتخاب کند.

راه حل

این مسئله را می‌توان با یک گراف وزن‌دار فرمول‌بندی کرد. در این گراف، رأس‌ها متناظر با مقاصد نامه‌ها و یال‌ها، متناظر با مسیرهای مواصلاتی بین این مقاصد است و وزن هر یال نیز متناظر با فاصله بین مقاصد است؛ بنابراین، باید مسیری بسته پیدا کرد که از هر یال دست‌کم یک بار عبور کرده و در مجموع، کمترین وزن را داشته باشد. واضح است اگر گراف اویلری باشد، آنگاه هر مسیر اویلری جواب مسئله است؛ ولی اگر گراف اویلری نباشد، حل مسئله مشکل‌تر خواهد بود و از حوصله این بحث خارج است. برای حالت خاص، فرض کنید گراف متناظر یک گراف شبه اویلری باشد و دو رأس از درجه فرد را با A ،B نشان م دهید. ابتدا، کوتاه‌ترین مسیر از A به B را بیابید. سپس، با اضافه کردن این مسیر به مسیر شبه اویلری گراف، جواب مسئله به دست می‌آید. برای توصیف بیشتر، گراف شبه اویلری زیر را در نظر بگیرید:

کوتاه‌ترین مسیر از (رأس‌ها از درجه فرد) عبارت است از: B ،A ،F ،E و طول این مسیر (مجموع وزن‌های مسیر) ۱۳= ۶+۴+۳ است.

همچنین، مسیر شبه اویلری عبارت است از: B ،C ،D ،E ،F ،A ،B ،F ،C ،E و طول این مسیر شبه اویلری ۶۴ است.

پس کوتاه‌ترین مسیر برای مسئله پستچی در گراف فوق عبارت است از: B ،C ،D ،E ،F ،A ،B ،F ،C ،E ،F ،A ،B و طول کل آن ۷۷ = ۶۴+۱۳ است.

منابع

• Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, pp. 640–642, ISBN 9781420099829
• Kwan, Mei-ko (1960), "Graphic programming using odd or even points", Acta Mathematica Sinica (به چینی), 10: 263–266, MR 0162630. Translated in Chinese Mathematics 1: 273–277, 1962.
• Pieterse, Vreda; Black, Paul E., eds. (September 2, 2014), "Chinese postman problem", Dictionary of Algorithms and Data Structures, مؤسسه ملی فناوری و استانداردها, retrieved 2016-04-26
• Grötschel, Martin; Yuan, Ya-xiang (2012), "Euler, Mei-Ko Kwan, Königsberg, and a Chinese postman" (PDF), Optimization stories: 21st International Symposium on Mathematical Programming, Berlin, August 19–24, 2012, Documenta Mathematica, Extra: 43–50, MR 2991468, archived from the original (PDF) on 8 August 2016, retrieved 5 October 2019.
• Edmonds, J.; Johnson, E.L. (1973), "Matching Euler tours and the Chinese postman problem" (PDF), Mathematical Programming, 5: 88–124, doi:10.1007/bf01580113
• Guan, Meigu (1984), "On the windy postman problem", Discrete Applied Mathematics, 9 (1): 41–46, doi:10.1016/0166-218X(84)90089-1, MR 0754427.</ref><ref name = "Complexity">Lenstra, J.K.; Rinnooy Kan, A.H.G. (1981), "Complexity of vehicle routing and scheduling problems", Networks, 11 (2): 221–227, doi:10.1002/net.3230110211