PART A
1. The degree(v) of a pendant vertex may be either one or zero.
T or F
2. A tree is any connected, undirected graph with an even number of vertices.
T or F
3. A simple graph is an undirected graph with no multiple edges and no loops.
T or F
4. A multigraph is an undirected graph with multiple edges and no loops.
T or F
5. Consider the following directed relations on {1, 2, 3, 4} :
R = {(1,1), (2,2), (3,3), (4,4)}
S = {(1,4), (2,3), (3,2), (4,1)}
R is reflexive and S is symmetric
T or F
6. Set A is divided into several disjoint partitions. The UNION of these partitions is the original set.
T or F
7. A W14 has 15 vertices and 28 edges.
T or F
8. The root of any tree must be at either level 1 (one) or level 0
(zero).
T or F
9. A leaf is a vertex with just one child.
T or F
10. A weighted graph has a value assigned to each edge.
T or F
11. The minimum spanning tree of a weighted graph is a graph that is drawn with the length of each edge roughly proportional to the value assigned to each edge.
T or F
12. Siblings must have the same parent but not necessarily the same level.
T or F
13. Since Prim's and Kruskal's algorithms generate a minimum spanning tree of a given weighted graph, each algorithm would always provide identical MST graphs.
T or F
14. A bipartite graph Kn,m has (n+m) vertices and a maximum of (n*m) edges.
T or F
PART B
Problems that require a particular approach - such as Prim and Kruskal - need a reasonable amount of intermediate work to identify and verify the solution process.
1. Form a binary search tree from the words of the following sentence using alphabetical order and inserting words as they appear in the sentence:
2. The expression below is in postfix expression form. Determine its numerical value.
{ 3, -5, +, 4, 2, /, 3, *, * }
3. Determine if Graph Z is bipartite. Defend your answer.
4. Define a postorder and preorder traversal of the following:
[(x + 4) / 2] + [(2 - x) / 5) ] .
a. postorder:
b. preorder:
5. Determine the Minimal Spanning Tree in Graph Y using Kruskal's
Algorithm. All edges must be labeled from lower to higher named vertices, e.g., from "c" to "d" but not from "d" to "c".
6. Given the coding scheme:
a:001, b:0001, e:1, r:0000, s: 0100, t:011, x:01010
Find the words represented by:
a. 0010000011
b. 0001110000
c. 01110100011
d. 001010101
e. What is the best compression ratio (versus ASCII 8-bit encoding) of the words in a through d above? (2 points). Defend your answer.
7. Determine the Minimum Spanning Tree in Graph X. Use Prim's Algorithm in which all edges must be labeled from lower to higher named vertices, e.g., from "c" to "d" but not from "d" to "c"
8. Construct a postorder, inorder and preorder transversal of Tree T.
a. postorder:
b. inorder:
c: preorder:
9. Are Graphs G and H isomorphic? Defend your answer.
10. Suppose that a full 37-ary tree has 3 internal vertices. How many leaves does it have? Defend your answer.
11. What is the shortest path in Graph S between "a" and "z". Use Dijkstra's algorithm.
a. the shortest path is:
b. the shortest distance between "a" and "z" is:
12. A tree has 42 edges. How many vertices does it have?
A.
Use a greedy algorithm to determine the shortest path in Graph S. The algorithm starts at vertex "a" and ends at vertex "z" always selecting the shortest edge. The selection must be in ascending lexicographic order, i.e., m to n - not n to m. See discussion on pages 195, 232, and 798.
B.
Is the solution using Prim's Algorithm in Question B.7 the same
topology and length as the required Kruskal solution? Defend your
answer.
GRAPH INFORMATION
Graph G
Initially draw a hexagon with vertices a-b-d-f-e-c-a.
Connect vertices a to f; b to c; d to e. There are no connections in the center.
b d
a f
c e
Graph H
Initially draw a hexagon with vertices u-v-w-x-y-z-u.
Connect vertices u to x; v to y; w to z.
There is no connection in the center.
u
z v
y w
x
Graph S
Initially draw a hexagon with vertices a-b-d-z-e-c-a.
Connect vertices b to c; b to e; c to d; d to e.
Edge values are:
a-b = 3; a-c = 4;
b-c = 1; b-d = 5; b-e = 5
c-d = 2; c-e = 4;
d-e = 1; d-z = 5; e-z = 3.
b d
a z
c e
Tree T
Construct a Tree with
vertex a at level 0;
vertices b, c and d at level 1;
vertices e, f, i, j, and k at level 2;
vertices g, h, l and m at level 3.
Connect vertex a to b, a to c, and a to d.
Connect vertex b to e and f.
Connect vertex c (no further connection).
Connect vertex d to i, j and k.
Connect vertex e to g and h.
Connect vertex f (no further connections).
Connect vertex i to l.
Connect vertex j (no further connection).
Connect vertex k to m.
Connect vertex g, h, l and m (no further connection).
a
b c d
e f i j k
g h l m
Graph X
Initially draw a rectangle with vertices a-c-e-z-d-b-a.
Connect vertices a to d; c to d; d to e.
Edge values are:
a-b = 1; a-c = 4; a-d =3;
b-d = 3; c-d = 2; c-e = 2;
d-e = 2; d-z = 2; e-z = 2.
a c e
b d z
Graph Y
Draw a hexagon with vertices a-b-d-z-e-c-a.
Connect vertices b to c; b to z; d to e.
Edge values are:
a-b = 3; a-c = 5;
b-c = 2; b-d = 5; b-z = 4;
c-e = 5;
d-e = 1; d-z = 7; e-z = 3.
b d
a z
c e
Graph Z
Graph Z is a five-pointed figure.
Connect a to b, a to c and a to e.
Connect b to d.
Connect c to d.
Connect d to e.
b c
a d
e