Week 4 Individual Assignment

11.1 (513-518)
3. For the graph in Fig. 11.7, how many paths are there from b to f ?

There are 6 paths from b to f:
(b, a, c, d, e, f), (b, c, d, e, f), (b, e, f), (b, a, c, d, e, g, f), (b, c, d, e, g, f), and (b, e, g, f)

11. Let G be a graph that satisfies the condition in Exercise 10.
a) Must G be loop-free?
b) Could G be a multigraph?
c) If G has n vertices, can we determine how many edges it has?

a) Yes, G must be loop-free because an edge is a bridge only if that edge is not contained in any cycles. A loop is a cycle.

b) Yes, G can be a multi-graph. For example, the multi-graph in Figure 11.6 (pg. 518) becomes disconnected if we remove edge (c, e). This would leave two components of (a, b, c) and (d, e).

c) Yes, G would have n – 1 edges for n vertices; the same vertex closes a graph and there is always a vertex at the start and end, which means there is one more vertex than an edge.

11.2 (520-528)
4. If G = (V, E) is an undirected graph, how many spanning subgraphs of G are also induced subgraphs?

The undirected graph G = (V, E) has 2|E| spanning subgraphs, one for each subset of the edge set, and 2|V| induced subgraphs, one for each subset of the vertex set.

11.3 (530-537)
5. Let G1 = (V1, E1) and G2 = (V2, E2) be the loop-free undirected connected graphs in Fig. 11.42.
a) Determine |V1|, |E1|, |V2|, and |E2|.

Counting the vertices and edges in both graphs:

|V1| = |V2| = 8
|E1| = |E2| = 14

11.4 (540-553)
3a. How many vertices and how many edges are there in the complete bipartite graphs K4,7, K7,11, and Km,n, where m, n, ∈ Z+?

K4,7 = 11 vertices (4 + 7) = 28 edges (4 * 7)
K 7,11 = 18 vertices (7 + 11) = 77 edges (7 * 11)
Km,n = m + n vertices = m * n edges

11.5 (556-562)
2. Characterize the type of graph in which an Euler trail (circuit) is also a Hamilton path (cycle).

A Euler trail is open and crosses each edge at least once without repeating. A Hamilton path passes through each vertex only once, and becomes a cycle when only the first and last vertices connect. According to these definitions, a shape can have a Euler trail and a Hamiltonian path if they have the same amount of edges and vertices. A triangle and square are both examples of a Euler trail and a Hamiltonian path because each uses each of its edges only once, and each only connects vertices at the same beginning and endpoint to close the shape.

12.1 (581-585)
2. Let T1 = (V1, E1), T2 = (V2, E2) be two trees where |E1| = 17 and |V2| = 2|V1|. Determine |V1|, |V2|, and |E2|.

In every tree T = (V , E), |V | = |E| + 1.
If T1 = (V1, 17), then V1 = 18, and T1 = (18, 17)
If V2 = 2(V1), then V2 = 2(18) = 36
If V2 = 36, and V = E +1, then E2 = 37

V1 = 18; V2 = 36; and E2 = 37

12.2 (587-603)
6. List the vertices in the tree shown in Fig. 12.31 when they are visited in a preorder traversal and in a post-order traversal.

Pre-order transversal (starting with the root down to each leaf)
1, 2, 5, 9, 14, 15, 10, 16, 17, 3, 6, 4, 7, 8, 11, 12, 13

Post-order transversal (starting with the leaves and ending with the root)
14, 15, 9, 5, 10, 16, 17, 2, 3, 6, 7, 4, 8, 11, 12, 13, 1

12.3 (605-609)
2. Apply the merge sort to each of the following lists. Draw the splitting and merging trees for each application of the procedure.
a) −1, 0, 2, −2, 3, 6, −3, 5, 1, 4

12.5 (615-621)
1. Find the articulation points and bi-connected components for the graph shown in Fig. 12.44.

The articulation points (more than two children) are b, e, f , h, j , and k.
The bi-connected components are:
B1: {{a, b}}
B2: {{d, e}}
B3: {{b, c}, {c, f }, {f, e}, {e, b}}
B4: {{f, g}, {g, h}, {h, f }};
B5: {{h, i}, {i, j }, {j, h}}
B6: {{j, k}}
B7: {{k, p}, {p, n}, {n, m}, {m, k}, {p, m}}.