奇偶點圖作業法

介紹

奇偶點圖作業法(graphical method based on an odd-even-point approach)求最優郵遞路線的 一種方法.其特點是:對有奇點的街道，方法是求郵 遞員遞送郵件的路線為最短.設在某條路線中的邊 w, , v;〕上重複走了幾次，在v;,v，之間增加幾條邊， 令每條邊的權和原來的權相等，並把新增加的邊稱 為重複邊.這樣，就把原問題變為:在一個有奇點的 圖中，要求增加一些重複邊，使新圖不含奇點，並且 重複邊的總權為最小.把使新圖不含奇點而增加的 重複邊，簡稱可行(重複邊)方案.使總權最小的可行 方案稱為最優方案。

轉變方法

1.第一個可行方案的確定方法.若圖中有奇點，則把它配成對，每一對奇點之間必有一條鏈，把這條鏈的所有邊作為重複邊加到圖中去，新圖中必無奇點.便給出了第一個可行方案.

2.調整可行方案，使重複邊總長度下降.當邊w,,v;]上有兩條或兩條以上的重複邊時，從中去掉偶數條，得到一個總長度較小的方案.於是，有:

1)在最優方案中，圖的每條邊上最多有一條重複邊.

2)在最優方案中，圖中每個圈上的重複邊的總權不大於該圈總權的一半.

3.判斷最優方案的標準一個最優方案一定是滿足上述1)和2)的可行方案.反之，一個可行方案若滿足上述1)和2)，則這個可行方案一定是最優方案.

根據判斷標準，對給定的可行方案，檢查它是否滿足上述條件1)和2).若滿足，所得方案即為最優方案;若不滿足，則對方案進行調整，直至上述條件1)和2)均得到滿足時為止.