Posted: November 2nd, 2015

HOMEWORK

1. Given the following graph, fill out the table below

Property                                                                              Values

Set of Vertices

1. The size of the graph
2. Degree of the Vertex 1
3. Degree of the Vertex 3
4. Show one path from 1 to 6
5. Are 2 and 4 adjacent?
6. f) Is this complete graph?

2. Cont… (using the same graph)
3. Is this graph a binary graph?
4. Represent this graph using an adjacency matrix
5. Represent this graph using an adjacency list
6. Describe the concept of a complete graph? Provide an example of a four-vertex graph

3. Describe the concept of a complete graph? Provide an example of a four-vertex graph.

4. Given the following tree, fill out the answer

Property                                                                              Values

1. Is this rooted tree?
2. Leaf vertices
3. Intenal vertices
4. Ancestores of vertice H
5. Decendants of vertice D
6. Siblings of vertice G
7. Parent vertice of F

5. Given the following tree

1. Is this tree a binary tree? Why?
2. Is this a full binary tree? Why?
3. Is this a complete binary tree? Why?

6. Provide two real-world applications of a tree in business, economics or the sciences (but not a family tree). Describe, in enough detail why a tree layout would be useful for these situations.