Results 1 to 5 of 5

Thread: Chinese postman problem

  1. #1
    Newbie
    Joined
    Jul 2016
    From
    Athens
    Posts
    2

    Chinese postman problem

    Hey everybody!

    I am no maths student, I am studying business administration and for logistics we have an exercise which i can't even begin with so i would appreciate any help. I have to say that the professor never even told us about this problem but somehow we have to figure this out on or own. Thanks in advance!

    We have a network 8x8 of a big chessboard. The 81 grid points are the crossroads. The crossroads are linked with the neighboring crossroads through edges of 1 m length horizontally and vertically. The horizontal streets can be crossed in both directions. The vertical 1st, 3rd, 5th, 7th and 9th streets from up to down and the 2nd, 4th, 6th, 8th from down to up. In this described graph can only the four fields in the centre of the chessboard turn clockwise to 90 degrees including the street orientation. The minimum number of visited edges of the optimal solution of this graph's chinese postman problem's is then:


    22

    23

    24
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    6,369
    Thanks
    1667

    Re: Chinese postman problem

    Hey yan1990.

    You are probably going to have to do an induction related approach for this problem.

    Have you considered the case when you have n^2 squares and then (n+1)^2 squares?

    I'll wait for your response.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2016
    From
    Athens
    Posts
    2

    Re: Chinese postman problem

    We have 64 squares...But i don't understand how induction is here the solution
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,374
    Thanks
    254
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    6,369
    Thanks
    1667

    Re: Chinese postman problem

    Induction is when you look at an isolated case for n and then try and find a relation for n+1.

    My thinking is that if the rules are the same for each square route (so think four nodes and edges connecting each adjacent "node") then one could find an inductive argument of the path taken given the less complex region.

    So if you have say n = 1 you get a point in the left hand corner. A case for n = 2 gives four nodes and the edges connecting them. n = 3 gives nine nodes and so on up until you do the whole 8x8 board with all edges.

    This is a common technique used to prove a lot of things in mathematics.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese remainder theorem problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jul 6th 2014, 01:10 AM
  2. Chinese remainder theorem problem
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Apr 1st 2012, 08:03 AM
  3. Chinese Remainder Theorem Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 21st 2009, 02:49 PM
  4. Chinese Postman Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jun 5th 2009, 04:24 AM
  5. Chinese Math PRoblem
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Mar 31st 2009, 05:25 PM

Search Tags


/mathhelpforum @mathhelpforum