Discrete Mathematics for Computer Science

412 CHAPTER 6 Graph Theory

3. Let D = (V, E) be a directed graph. An edge (a, b) E E:
   (a) Contributes one to the indegree of a
   (b) Contributes one to the outdegree of a
   (c) Contributes one to the indegree of a and one to the outdegree of b
   (d) All of the above


4. The longest directed trail in the graph shown contains how many edges?

(a) 8

(b) 7

(c) 6

(d) 5

5. Construct a graph with degree sequence 1, 2, 2, 3, 4, 5, or prove that none exists.


6. Answer the following questions for the following tree

a

b c

d e f

g h j

k p q s t

(a) What vertices are leaves?

(b) What vertex is the root?

(c) What vertex is the parent of g?

(d) What vertices are the descendants of c?

(e) What vertices are the siblings of s?

(f) What is the level number of the vertex f?

(g) What vertices are at level four?

(h) What is the height of the tree?

7. Find an MCST in G. Show all the steps of the algorithm you use.

a 3 b

4e____

e 5 d 7 c