Graph Review Solutions

Exercise 17.17. Give the adjacency-matrix representations of the three graphs depicted in Figure 17.2. Here are the graphs from the figure together with their adjacency-matrices:
$\begin{figure} \sf\bfseries\footnotesize \hfill \psset{mnode=circle} {\colo... ...& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \end{tabular} \hfill \end{figure}$

$\begin{figure} \sf\bfseries\footnotesize \hfill \psset{mnode=circle} {\colo... ...& 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{tabular} \hfill \end{figure}$

$\begin{figure} \sf\bfseries\footnotesize \hfill \psset{mnode=circle} {\colo... ...& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \end{tabular} \hfill \end{figure}$
Exercise 17.27. Show, in the style of Figure 17.10, the adjacency-lists structure produced when you use Program 17.9 to insert the edges in the graph
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
(in that order) into an initially empty graph. The key point here is that the new edges are inserted at the front of the adjacency lists. Here is the result:
$\begin{figure} % latex2html id marker 146 \sf\bfseries\footnotesize \hfill ... ...0,1){6}} \put(42,9){\makebox(0,0){2}} \end{picture} \hfill\hfill \end{figure}$
Exercise 18.6. Show, in the style of Figure 18.5, a trace of the recursive function calls made when a cDFS<DenseGRAPH> object is constructed for the graph
0-2 0-5 1-2 3-4 4-5 3-5.
Draw the corresponding DFS recursive-call tree. First, here is a representation of the graph:
$\begin{figure} \sf\bfseries\footnotesize \hfill \psset{mnode=circle} {\colo... ...ine{1,3}{2,3} \ncline{2,3}{2,2} \end{psmatrix} }} \hfill\hfill \end{figure}$
Now here is the desired trace. Note that the significance of using the DenseGRAPH representation is that we will visit adjacent nodes in increasing numerical order (as we read across a row of the adjacency matrix).
```
              012345
0-0           0*****
  0-2         0*1***
    2-0
    2-1       021***
      1-2
  0-5         021**3
    5-0
    5-3       0214*3
      3-4     021453
        4-3
        4-5
      3-5
    5-4
```
The DFS recursive-call tree is
$\begin{figure} \sf\bfseries\footnotesize \hfill \psset{levelsep=20pt,treesep... ...{ \pstree{\Tcircle{3}}{ \Tcircle{4} } } } }}\hfill\hfill \end{figure}$
Exercise 18.7. Show, in the style of Figure 18.6, the progress of the search for the example in Exercise 18.6. The recursive-call tree is shown above, so I won't repeat it here.
$\begin{figure} \sf\bfseries\footnotesize \hfill \psset{mnode=circle} {\colo... ...%% 1-2 \ncline{2,3}{2,2} %% 1-2 \end{psmatrix} }} \hfill\hfill \end{figure}$
Exercise 18.15. Draw the DFS forest that results from a standard adjacency-matrix DFS of the graph
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.
Note that this is the same graph from Exercise 17.27. Here is a representation of the graph:
$\begin{figure} \sf\bfseries\footnotesize \hfill \psset{mnode=circle} {\colo... ...%% 9-2 \ncline{2,4}{2,5} %% 2-5 \end{psmatrix} }} \hfill\hfill \end{figure}$
Performing a depth-first search using the adjacency matrix results in starting from node 0 and following the path to the smallest numbered not-already-visited adjacent node at each step, backing up to try larger unvisited nodes at the end. Here is the resulting DFS forest:
$\begin{figure} \sf\bfseries\footnotesize \hfill \psset{levelsep=20pt,treesep... ...{3}}{ \pstree{\Tcircle{7}}{ \Tcircle{8} } } }}\hfill\hfill \end{figure}$
Exercise 18.16. Draw the DFS forest that results from a standard adjacency-lists DFS of the graph
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.
The difference between this and the last problem is that the adjacency lists will store the edges in reverse order from how they were entered. Exercise 17.27 figured out the lists; here is the resulting DFS forest:
$\begin{figure} \sf\bfseries\footnotesize \hfill \psset{levelsep=20pt,treesep... ...{3}}{ \pstree{\Tcircle{8}}{ \Tcircle{7} } } }}\hfill\hfill \end{figure}$
Exercise 18.50. Draw the BFS forest that results from a standard adjacency-lists BFS of the graph
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.
With the same graph as the previous two problems but using a queue instead of a stack (in fact, I didn't use a stack for the DFS exercises, since that would have reversed the order of the adjacent nodes and messed up the distinction between the matrix and list representations; instead, I used the recursive version of DFS) we get the following BFS forest:
$\begin{figure} \sf\bfseries\footnotesize \hfill \psset{levelsep=20pt,treesep... ...stree{\Tcircle{3}}{ \Tcircle{8} \Tcircle{7} } }}\hfill\hfill \end{figure}$
Exercise 18.51. Draw the BFS forest that results from a standard adjacency-matrix BFS of the graph
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.
Finally, using the increasing numeric order to visit adjacent nodes that comes with the adjacency matrix, we get the following BFS forest:
$\begin{figure} \sf\bfseries\footnotesize \hfill \psset{levelsep=20pt,treesep... ...stree{\Tcircle{3}}{ \Tcircle{7} \Tcircle{8} } }}\hfill\hfill \end{figure}$