EE6605 HW#4 Solutions 2020 4-1 No solutions. Just like the seven-bridge problem, to have a solution all nodes must have an even
degree, but there are two corner nodes that have an odd degree (Fig. (a)).
From another viewpoint, if the two corners are not the starting or ending nodes then after the “bishop-pawn” moves into any corner, it needs to move out again but then it repeats the next black block on its diagonal path; however, if the two corners are starting and ending nodes, respectively, then the “bishop-pawn” does not return to the beginning (Fig. (b)).
4-2 (4-2.1)
1.1) False
1.2) False
(a) (b)
1.3) True For a circuit v1 v2 vn v1, if it has an even number of edges, then the index n must be an even number. Thus, putting all nodes with odd indices into group V1 and all nodes with even indices into group V2 , one has a bipartite graph
with V1 on one side and V2 on the other side.
1.4) True An isomorphism is a trivial homeomorphism without degree-2 nodes.
1.5) False A long chain and a short chain are homeomorphic but not isomorphic (since even the numbers of their nodes are different).
1.6) False
(4-2.2)
2.1) Ture because there is a directed path going through all edges once and once only, and
finally return to the starting node. Removing all the directions along this path gives a solution to the underlying graph.
EE6605 HW#4 Solutions 2020
2.2) Ture because there is a directed path going through all nodes once and once only, and finally return to the starting node. Removing all the directions along this path gives a solution to the underlying graph.
2.3) Ture because from a strongly connected digraph, one can remove those edges whose removal will not destroy the strong connectivity of the network, thus what is left is a directed spanning tree.
2.4) False 2.5) False 2.6) False
(4-2.3)
3.1) True For every node, the number of “walk in” is equal to the number of “walk out”, so the
situation is the same as the undirected graphs.
3.2) False
3.3) False
3.4) False
4-3 Let T be the total time for the postman to walk through all original streets (T = 58, not important). B5C
Post Office
4
5
F
10
7
D
5 A78
7 E
T+AB+AF+EF = T+16; T+BF+FE = T+14; T+BC+CE = T+13; T+ED+CD+BC = T+17; T+EF+FC+BC = T+22; T+CE+FC+BF = T+25
Optimal solution: Adding BC and CE 4-4 Total maximum path length = 22
EE6605
HW#4 Solutions 2020 3
27
A13B 6 543
5
4
3
8
2
4-5 (Solution not unique)
Or
6
This is a perfect matching.