Week 4 Assignments

Section 9.1

Exercise 2

The graph is not a tree, because there more than one paths from one vertex to another.

Exercise 3

The graph is not a tree, because not all of the vertices of the graph are connected. Thus, there is no an existing unique path between some vertices.

Exercise 9

The height of the tree in the Exercise 8 is 4

Exercise 10

[pic]

The height of this tree is 5

Exercise 12

An example of the hierarchical relationship is a family tree:

[pic]

Section 9.2

Exercise 5

Siblings of Ares: Hades, Poseidon and Zeus.

Exercise 6

[pic]

Exercise 8

The parent of c is b, while the parent of j is e.

Exercise 9

The children of d are h and i, while the only child of e is j.

Exercise 11

The siblings of f are e and g.
The sibling of h is i.

Exercise 12

The terminal vertices are: j, f, g, h, i.

Exercise 18

If two vertices in a rooted tree have same ancestors, they must share same simple path to their parent, which means that they are siblings.

Exercise 19

The only vertex in the rooted tree, that does not have ancestors, is a root itself.

Exercise 20

By definition, a tree cannot have two vertices sharing a child, because this will create two possible paths to that child and will violate the definition of a tree.

Exercise 21

A vertex in a rooted tree that has no decedents is a leaf (a terminal vertex).

Exercise 29

According to the Theorem 9.2.3, if a graph is a tree, then it is acyclic and has n – 1 edges. The graph in this problem contains a cycle (v1, v1) an n edges.

Section 9.3

Exercise 2
Exercise 3
Exercise 5
Exercise 6
Exercise 2
Exercise 9
Exercise 18
Exercise 19

Section 9.4

Exercise 2
Exercise 3
Exercise 24
Exercise 25

Section 9.5

Exercise 19
Exercise 20

Section 9.6

Exercise 2
Exercise 3
Exercise 5
Exercise 7

----------------------- a b

c

e

d

g

f

h

i

j

Person

Child 3

Grandchild 1

Aphrodite

Grandchild 3

Grandchild 4

Grandchild 2

Child 2

Child 1

Eros