Code: Select all
1
/ \ \
/ \ \
2 \ \
\-----3-- 4
\
\
\
5
Moderator: Board moderators
Code: Select all
1
/ \ \
/ \ \
2 \ \
\-----3-- 4
\
\
\
5
Think a bit deeper. In a minimum cost matching, no two shortest paths can have a common edge. (See figure 6.16 on this page.)in Chinese postman you can run a min-cost matching on a general graph with vertices the odd degree vertices in the original graph and cost the shortest path between the vertices because you are allowed to count the cost of any edge more than once or twice - here you can only count the cost of an edge once.
Code: Select all
1
/|\
/ | \
/ | \
/ | \
/ | \
/ | \
3------2------4
\___________/
A graph *never* has an odd number of odd vertices, since that would imply that total degree is odd.since the graph is connected and so there must be an odd number of odd vertices