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

این مسئله را می‌توان با یک گراف وزن‌دار فرمول‌بندی کرد. در این گراف، رأس‌ها متناظر با مقاصد نامه‌ها و یال‌ها، متناظر با مسیرهای مواصلاتی بین این مقاصد است و وزن هر یال نیز متناظر با فاصله بین مقاصد است؛ بنابراین، باید مسیری بسته پیدا کرد که از هر یال دست‌کم یک بار عبور کرده و در مجموع، کمترین وزن را داشته باشد. واضح است اگر گراف اویلری باشد، آنگاه هر مسیر اویلری جواب مسئله است؛ ولی اگر گراف اویلری نباشد، حل مسئله مشکل‌تر خواهد بود و از حوصله این بحث خارج است. برای حالت خاص، فرض کنید گراف متناظر یک گراف شبه اویلری باشد و دو رأس از درجه فرد را با 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