Discrete Mathematics for Computer Science

368 CHAPTER 6 Graph Theory

Draw the depth first search tree or the breadth first search tree that results from the

following:

(a) A depth first search on G beginning at vertex 1

(b) A depth first search on G beginning at vertex 6

(c) A breadth first search on G beginning at vertex 1

(d) A breadth first search on G beginning at vertex 6

13. For each of the following graphs:
    (a) Carry out a depth first search starting at vertex b.
    (b) Carry out a breadth first search starting at vertex b.
    (c) Repeat parts (a) and (b) using vertex g as the starting vertex.
    b a c
    a
    b cd

d f f h

9g >h.

In each case display the result of the search process as was done in Figures 6.22

through 6.24.

14. Perform a depth first search and a breadth first search on the graph given by the fol-
    lowing adjacency list:
    Vertices List of Adjacencies
    1 9 2 4
    2 1 3 5
    3 2 4
    4 3 1
    5 6 2
    6 7 9 5
    7 8 6
    8 7
    9 6 1

Start each search at vertex 3. Repeat the problem starting with vertex 5. Draw the depth

first search tree and the breadth first search tree for each case.

15. Write an algorithm for finding a shortest path between any two vertices in a connected
    graph.


16. Let G = (V, E) be a graph. Prove that if the minimum degree of G is greater than
    (I V I - 1)/2, then G is connected.


17. Let G = (V, E) be a graph. Prove that if I E I < I V- 1, then G is disconnected.


18. Find connected graphs with at least eight vertices such that:
    (a) G is Eulerian and not Hamiltonian.
    (b) G is not Eulerian but is Hamiltonian.
    (c) G is not Eulerian and not Hamiltonian.
    (d) G is Eulerian and Hamiltonian.