Results 1 to 3 of 3

Math Help - Chinese Postman Problem

  1. #1
    Newbie
    Joined
    Jun 2009
    Posts
    2

    Chinese Postman Problem

    Hi,

    does anybody know how to solve chinese postman problem as maximal network flow problem?

    thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by rory1982 View Post
    Hi,

    does anybody know how to solve chinese postman problem as maximal network flow problem?

    thanks!
    I have never heard of "chinese postman problem".
    It is anything like the american postman problem?

    Is is possible for you to state the problem?
    It is clear that you want the result to be a "maximal network flow" approach.
    Last edited by aidan; June 4th 2009 at 07:21 PM. Reason: found definition using internet search
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2009
    Posts
    2
    I don't know 'cause i never heard of american postman problem

    Chinese postman problem:
    A postman has to deliver mail along all the streets in the town. Assume that on one-way street the mail boxes are all on one side of the street, whereas for two-way streets, there are mail boxes on both sides of street. The postman wishes to minimize the distance he has to travel in order to deliver all the mail and return home to his starting point.

    So, we can model the problem by a directed graph and a weight function, where set of vertices are intersection of streets, and arcs model the streets. A 2-cycle corresponds to a two-way street. The weight of an arc corresponds to the lenght of the corresponding street. Optimal route corresponds to a closed walk which traverses each arc at least once.

    So it can be solved as a minimum cost problem. But i don't know how to draw a network with source and sink and how to solve it as maximal flow problem?

    thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese Rem. Thm.
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: August 3rd 2012, 01:37 AM
  2. Basic Chinese Remainder Theorem Problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 22nd 2010, 09:27 AM
  3. Chinese Remainder Theorem Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 21st 2009, 01:49 PM
  4. Chinese Math PRoblem
    Posted in the Algebra Forum
    Replies: 4
    Last Post: March 31st 2009, 04:25 PM
  5. chinese remainder
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 29th 2008, 09:20 AM

Search Tags


/mathhelpforum @mathhelpforum