Results 1 to 6 of 6

Math Help - Hamiltonian/Euler Problems (Travelling Salesman Prob)

  1. #1
    Newbie
    Joined
    Nov 2006
    Posts
    21

    Hamiltonian/Euler Problems (Travelling Salesman Prob)

    Hi,

    I was wondering if anyone could help me with these Euler/Hamiltonian type problems;

    Suppose we have a graph with 5 horizontal rows and 4 verticle columns

    (G_(5,4))

    So it looks something like:

    Code:
    *-*-*-*
    | | | |
    *-*-*-*
    | | | |
    *-*-*-*
    | | | |
    *-*-*-*
    | | | |
    *-*-*-*
    All the horiz. edges have a weight of h and all the vertical ones have a weight of v, where both h and v are pos. numbers.

    a.) Solve the TSP (Travelling Salesman Prob), that is: find a hamiltonian circuit (HC) of least total weight) if: h < v

    b.) Solve the TSP, that is: find a HC of least total wght if: h > v

    c.) Describe every m, n such that G_(m,n) has a HC

    d.) Describe every m, n such that G_(m,n) has a Hamiltonian PATH.

    2.) Eulerize G_(m,n) for every m, n >= 2. That is, what's the fewest # of edges you'll need to DUPLICATE such that the new graph will have an Eulerian circuit.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2006
    Posts
    21
    My professor said they are definitely solveable. Anyone have any suggestions?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2006
    Posts
    21
    Okay; I have figured out a-d on #1; now I need help with #2:

    Eulerize G_(m,n) for every m, n >= 2. That is, what's the fewest # of edges you need to DUPLICATE such that the new graph will have an Eulerian circuit.

    So it's a general problem for any graph m, n. Since this is worth a ton of points, I need to at least try and attempt it for partial credit.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2006
    Posts
    21
    I was given a hint that I should be able to answer the question "how many edges would you need to duplicate to optimally eulerize G_(146,284)".

    When I try working on different cases, I can't get a method that works every time for all m, n.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2006
    Posts
    21
    I think I got it!

    Now this will be my last post unless someone proves me wrong from my conjecture:

    Number of even vertices of odd degree (actually all are even) / 2
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2006
    Posts
    21
    Nope just found a counter-example.

    I probably should have noted that the graph is a "grid graph" so it has m horizontal rows and n vertical columns, and I have to optimally Eulerize it (add fewest duplicate edges to make an Euler circuit) for any G_(m,n).

    Well I might as well give up on it now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Asymmetric Travelling Salesman Problem - Particular case
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: November 17th 2011, 02:13 AM
  2. Salesman Tour
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 6th 2011, 01:11 AM
  3. [SOLVED] Euler and Hamiltonian Cycle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 21st 2010, 03:56 AM
  4. Travelling Salesman
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: April 27th 2009, 04:08 AM
  5. Euler & Hamiltonian Circuit proofs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 9th 2008, 07:16 PM

Search Tags


/mathhelpforum @mathhelpforum