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.