Here are examples of hypercubes for k=1, 2, 3: 100 101 10 11 10 10 01 001 k-1 k=

Question

Here are examples of hypercubes for k=1, 2, 3: 100 101 10 11 10 10 01 001 k-1 k=2 One more piece of background information: The Chinese Postman Problem (CPP) is the problem of finding a "closed walk" - meaning we move around from vertex to vertex in a weighted graph by traversing edges, where the initial vertex and end vertex are the same - that traverses all the edges in a graph. In particular, we seek a closed walk of minimum total length that uses all the edges Exercise: Solve the CPP in the k-dimensional cube Qk, under the condition that every edge has weight 1.(Hint: consider two cases, (1) k is odd, (2) k is even). By "solve", I mean that you should describe an efficient algorithm in a sentence or two and then give the minimum cost for your solution

Explanation / Answer

The Qk cubes are k-regular graphs( where every vertex have same number of edges). if k is even, then the minimum cost is k*2(k-1). For k = odd the duplicate edge is required at each vertex which match cross the last coordinate. The minimum cost for k=odd is (k+1)*2(k-1).

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.