In: Science

Submitted By abacussolutions

Words 408

Pages 2

Words 408

Pages 2

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…...