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

A hypercube for k, have total 2k vertices, and each vertices have k degree. Total degree of hypercube is k2k . Total edges in hypercube = total degree/2 = k2k-1  . When k is even, then each of the vertices will have even degree and this will be the easy case because the hypercube in this case will be Eulerian graph in which all the vertices have even degree and such graph will always have Eulerian circuit, which means, we can always traverse the all the edges starting from a node and return back to the same node without repeating any edges.

We will divide this algorithm into two cases,

Case 1: when k is even.

This is an easy case. The algorithm is, start from a vertex v, go to other vertices though the edges which have not been already covered in walk. Since the graph has even degree, we will always has one uncovered outgoing edges corresponding to one uncovered incomming edges. Using Hierholzer's algorithm we can construct the Eulerian path covering all the edges.

Since we are covering each edge only once. Total cost:- edge weight*number of edges = 1*k2k-1= k2k-1

Case 2:- When k is odd.

This is little harder. Since the degree of each edge is odd in this case, Eulerian path is not possible. However we can make a close walk, which traverse entire vertices and covering k-1 edges in each vertices only once since k-1 is an even number. Thus using same algorithm, we will cover each vertices and their k-1 edges only once and returning back to starting vertices covering total (k-1)2k-1 edges. Now we have remining 2k-1 vertices yet to cover. The structure of graph is that every vertices is connected with only one uncovered edges.

Now starting from same initial vertices, go to another edges through covering the uncovered edge, from next vertex, go again to another vertices but this time through already covered edge and then again from next vertex go through uncovered edge to another vertex and so on. So we will go through alternate covered and uncovered edges and finally return back to starting vertices.

So at first we covered (k-1)2k-1 edges without any repetition, then in next cycle we covered 2k-1 uncovered edges exactly once and covered 2k-1 edges which was already covered.

Total cost :- 1*( (k-1)2k-1 + 2k-1 + 2k-1 ) = (k+1)2k-1

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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