1. **Problem statement:** We have a directed graph $D = (V, A)$ with nodes $V = \{1,2,3,4,5,6,7\}$ and directed edges $A = \{(1,2),(2,4),(3,1),(3,2),(3,4),(4,5),(5,2),(5,6),(6,3),(6,7),(7,6)\}$. We need to answer three questions: 2. **(a) Is $D$ strongly connected?** - A digraph is strongly connected if there is a directed path from every node to every other node. - Check reachability: - From node 1: can reach 2, then 4, then 5, then 6, then 3, then 7. - From node 7: can reach 6, then 3, then 1, then 2, then 4, then 5. - Since from any node we can reach all others, $D$ is strongly connected. 3. **(b) Does $D$ contain a directed simple cycle passing all nodes exactly once?** - Such a cycle is a Hamiltonian cycle. - Try to find a cycle visiting all nodes once: - One candidate path: $3 \to 1 \to 2 \to 4 \to 5 \to 6 \to 7 \to 6$ (repeats 6, so no) - Another: $3 \to 2 \to 4 \to 5 \to 6 \to 7 \to 6$ (repeats 6 again) - Because of the edges, node 7 only connects to 6 and vice versa, so to include 7, we must visit 6 twice. - Therefore, no directed simple cycle passes all nodes exactly once. 4. **(c) Node-arc-incidence matrix of $D$:** - Rows correspond to nodes $1$ to $7$. - Columns correspond to arcs in order: $(1,2),(2,4),(3,1),(3,2),(3,4),(4,5),(5,2),(5,6),(6,3),(6,7),(7,6)$. - Entry is $-1$ if node is tail of arc, $+1$ if node is head, $0$ otherwise. $$ \begin{array}{c|ccccccccccc} & (1,2) & (2,4) & (3,1) & (3,2) & (3,4) & (4,5) & (5,2) & (5,6) & (6,3) & (6,7) & (7,6) \\ \hline 1 & -1 & 0 & +1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & +1 & -1 & 0 & +1 & 0 & 0 & +1 & 0 & 0 & 0 & 0 \\ 3 & 0 & 0 & -1 & -1 & -1 & 0 & 0 & 0 & +1 & 0 & 0 \\ 4 & 0 & +1 & 0 & 0 & +1 & -1 & 0 & 0 & 0 & 0 & 0 \\ 5 & 0 & 0 & 0 & 0 & 0 & +1 & -1 & -1 & 0 & 0 & 0 \\ 6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & +1 & -1 & -1 & +1 \\ 7 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & +1 & -1 \\ \end{array} $$ **Final answers:** - (a) Yes, $D$ is strongly connected. - (b) No, $D$ does not contain a directed simple cycle passing all nodes exactly once. - (c) The node-arc-incidence matrix is given above.