1 2 3 4 5 6 7 8 9 10 11 12 Contents
不幸的是，並非每一個圖或每一個街道圖都存在尤拉迴圈。前述的街道圖，藍點的秩皆為奇數，所以此圖沒有尤拉迴圈：
然而信還是得送，如何才能有效率的完成這件事？顯然有幾條街非得走不只一次才行；為了節省時間，我們當然希望這些重覆走的街道長度愈短愈好。我們先考慮一個比較簡單的情況，假設每一條街道的長度都一樣長，那麼剛剛的問題就變成重覆走過的邊數愈少愈好。這一類的問題最先是由華裔數學家管梅谷所提出，因此被稱為“中國郵差問題”。
解決中國郵差問題的方法即是將一個圖尤拉化（eulerizing）：
所謂將一個圖尤拉化是在圖中加上一些邊，使得新圖中會存在尤拉迴圈。對應於實際問題，這些加上的邊是指重覆走的邊，因此若想在兩點間加上一條邊，必須是這兩點間原本就有的邊才行。
如何將一個圖尤拉化呢？從尤拉的定理得知，我們需要找出秩為奇數的點。這樣的點一定為偶數個，因為所有點的秩的和一定是偶數（所有點的秩的和是所有邊數的兩倍）。我們找出這些點之後，將它們兩兩分組，然後在同一組中的兩點間加一條路徑連接它們，而這路徑必須是沿著圖中原本就有的邊走，而且當然經過的邊是愈少愈好，如下圖：
然而如何找到最好的尤拉化，也就是如何加最少的邊產生一個尤拉圖更是一道難題。有系統地尋找最佳尤拉化的方法的確存在，但是相當複雜，而這一類的問題其實和圖論中的配對問題是相關的。在這裡，我們就舉個例子來作解釋：
剛剛我們也提到奇數秩的點必須是偶數個（如上圖有A, B, C, D四點），所以可以兩兩成對；而且因為是連通圖，因此這些點中的任何一對都存在路徑相連。接著，對於任意一對點，我們必須找出這兩點間的一條最短路徑。下面兩個圖都在A, B兩點間加了一條路徑，當然還有很多其他的走法，但是顯而易見地，右圖中的路徑是A, B間的最短路徑。
最後就剩下如何將這些點適當的配對以得到一組路徑，使得這些路徑的長度總和為最短。如圖，不論是分成A, B和C, D兩對，或是分成A, C和B, D兩對，增加的路徑長度總和都為6條邊。
但是若分成A, C和B, D這兩對，增加的路徑長度總和就變成12條邊。
因此，此圖最佳的尤拉化應是上面那兩個圖。
