Exercise 8.1 Tree Definition Which of these graphs are trees?
1
Exercise 8.2 Tree Definition
Answer these questions about the rooted tree illustrated. a) Which vertex is the root?
b) Which vertices are internal?
c) Which vertices are leaves?
d) Which vertices are children of j ?
e) Which vertex is the parent of h ?
f) Which vertices are siblings of o ?
g) Which vertices are ancestors of m ?
h) Which vertices are descendants of b ?
2
Exercise 8.3 Spanning Tree
Find a spanning tree for each of these graphs. a) K5
b) K4,4
c) K1,6
d) Q3
e) C5
f) W5
Kruskal’s algorithm
Find a minimum-weight spanning tree via Kruskal’s algorithm. List the edges chosen
Exercise 8.4
in order and sketch the tree.
3
Exercise 8.5 Dijkstra’s algorithm
Given the root vertex a, find a shortest-path spanning tree via Dijkstra’s algorithm.
List the edges chosen in order, list the shortest path distance (from root vertex) to each vertex. Sketch the tree.
4
Reference
1. Rosen, Kenneth H., and Kamala Krithivasan. Discrete mathematics and its applica- tions: with combinatorics and graph theory. Tata McGraw-Hill Education, 2012.
2. Fraleigh, John B. A first course in abstract algebra. Pearson Education India, 2003.
5
