HOMEWORK PROBLEMS #4
4-1 A standard chessboard is shown in the following Figure (a). Define a new “bishop-pawn” marked by a red disc as shown in Figure (b), which can move only “one step by one step” along the diagonal direction, as indicated in Figure (b).
Can this “bishop-pawn” start from a black block, somewhere on the chessboard, then move to visit every black block, once and once only, and
(1) needs not to return to the starting block;
(2) finally returns to the starting block.
If so, how? If not, why?
SHAPE \* MERGEFORMAT
4-2 Answer the following True or False questions, with a few words or (counter)examples to support your answers (to avoid trivial cases, assume all network sizes EMBED Equation.3 ):
(4-2.1) Undirected graphs
1.1) In a Hamiltonian graph, every node has an even degree.
1.2) If a graph is both Eulerian and Hamiltonian, then it has an even number of edges.
1.3) A circuit with an even number of edges is bipartite.
1.4) If two graphs are isomorphic then they are homeomorphic.
1.5) If two graphs are homeomorphic then they are isomorphic.
1.6) For any even number EMBED Equation.3 , the r-regular graph has an even number of edges.
(4-2.2) Digraphs
2.1) If a digraph is directed Eulerian then its underlying graph is also Eulerian.
2.2) If a digraph is directed Hamiltonian then its underlying graph is also Hamiltonian.
2.3) If a digraph is strongly connected then it has a directed spanning tree.
2.4) A directed tree always has a perfect matching and it is unique.
2.5) A matching in a digraph is also a matching in its underlying graph.
2.6) A perfect matching in a digraph is always a perfect matching in its underlying graph.
(4-2.3) In a digraph, denote the node’s in-degree by EMBED Equation.3 and out-degree by EMBED Equation.3 .
3.1) A connected digraph is directed Eulerian if and only if every node satisfies EMBED Equation.3 .
3.2) A connected digraph is directed Eulerian if and only if EMBED Equation.3 .
3.3) A connected digraph is directed bipartite if and only if every node satisfies EMBED Equation.3 .
3.4) A connected digraph is directed bipartite if and only if EMBED Equation.3 .
4-3 Solve the Chinese postman problem shown below, where the time for the postman to walk through each street has been indicated.
SHAPE \* MERGEFORMAT
4-4 Solve the maximum flow problem on the following graph, where numbers are rewards (show your steps):
SHAPE \* MERGEFORMAT
4-5 Use the augmenting path algorithm to find a maximum matching of the following bipartite graph (show your steps):
Is your result a perfect matching?
PAGE 56 Fuzzy Set Theory • 1
This HW is due to Canvas on Thursday 15 October 2020
EE 6605 CityU 2020
This HW is due to Canvas on Thursday 15 October 2020
(a) (b)
A
Post Office
B
C
D
E
F
4
5
7
5
5
10
8
7
7
2
6
3
3
8
4
5
2
5
6
4
1
7
3
3
A
B