Discrete and Combinatorial Mathematics (Week 4) - Assignment Example

Dear please refer to the ebook.pdf file for your reference if needed. Answer the following questions on the same word document; please placeanswers where it says “Please place answer here”. The username and password for the ebook.pdf file is: username: rmisenti password: rich1920Exercise 11.1 (page 519 in ebook.pdf)3.) For the graph in Fig. 11.7, how many paths are there from b to f?PLEASE PLACE ANSWER HERE (in red)1). b a c d e g f2). b a c d e f3). b   c d e g f 4). b c d e f5). b e g f6).

b e f = 6 ways.6.) If a, b are distinct vertices in a connected undirected graph G, the distance from a to b is defined to be the length of a shortest path from a to b (when a = b the distance is defined to be0). For the graph in Fig. 11.9, find the distances from d to (each of) the other vertices in G.PLEASE PLACE ANSWER HERE (in red)Distance to e = 1distance to f = 1distance to c = 1distance to k = 2distance to g = 2distance to h = 3distance to j = 3distance to l = 3distance to m = 3distance to i = 48.) Figure 11.

10 shows an undirected graph representing a section of a department store. The vertices indicate where cashiers are located; the edges denote unblocked aisles between cashiers. The department store wants to set up a security system where (plainclothes) guards are placed at certain cashier locations so that each cashier either has a guard at his or her location or is only one aisle away from a cashier who has a guard. What is the smallest number of guards needed?PLEASE PLACE ANSWER HERE (in red)Positions of the guards are b, g, j, and d. 4 guards.15.) For the undirected graph in Fig. 11.12, find and solve a recurrence relation for the number of closed v-v walks of length n ≥ 1, if we allow such a walk, in this case, to contain or consist of one or more loops.

PLEASE PLACE ANSWER HERE (in red)V-W Exercise 11.3 (page 537 in ebook.pdf)5.)PLEASE PLACE ANSWER HERE (in red)Tan x = 1, x = 45 degrees.Yes, they are isomorphic.20.)(a)Find an Euler circuit for the graph in Fig. 11.44.(b) If the edge {d, e} is removed from this graph, find an Euler trail for the resulting subgraph.PLEASE PLACE ANSWER HERE (in red)a) Begin with: a-b-c-g-k-j-i-h-d-aOther edges: b-g-j-f-i-e-d-bJoin: a-b-g-j-f-i-e-d-b-c-g-k-j-i-h-d-aMore edges: b-e-f-bJoin: a-b-e-f-b-g-j-f-i-e-d-b-c-g-k-j-i-h-d-aEuler Circuit: a-b-e-f-b-g-j-f-i-e-d-b-c-g-k-j-i-h-d-ab) Beginning path: d-a-b-c-g-k-j-i-h-dMore edges: d-b-g-j-f-i-e-b-f-eJoin: d-a-b-c-g-k-j-i-h-d-b-g-j-f-i-e-b-f-eEuler Trail: d-a-b-c-g-k-j-i-h-d-b-g-j-f-i-e-b-f-e21.) PLEASE PLACE ANSWER HERE (in red)a) For odd values of n, each vertex of K_n has even degree so K_n has an Euler circuit.b) The graph K2 has a Euler path but lacks a Euler circuit.

For even values or integers of n greater than 2, Kn has more than 2 vertices of odd degree, so K_n has neither an Euler path nor an Euler circuit.22.) For the graph in Fig. 11.37(b), what is the smallest number of bridges that must be removed so that the resulting subgraph has an Euler trail but not an Euler circuit? Which bridge(s) should we remove?PLEASE PLACE ANSWER HERE (in red)One bridge. Bridge b should be removed for the resulting sub graph to have a Euler trail.Exercise 12.2 (page 604 in ebook.pdf)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.

PLEASE PLACE ANSWER HERE (in red)2, 15, 17, 89.)LetG = (V , E) be an undirected graph with adjacency matrix A(G) as shown here.Use a breadth-first search based on A(G) to determine whether G is connected.PLEASE PLACE ANSWER HERE (in red)A (G) is connected since v8 v8 are connected within the provided graph.Exercise 12.5 (page 621 in ebook.pdf)3.) Let T = (V, E) be a tree with |V | = n ≥ 3.a) What are the smallest and the largest numbers of articulation points that T can have? Describe the trees for each of these cases.b) How many biconnected components does T have in each of the cases in part (a)?

PLEASE PLACE ANSWER HERE (in red)Smallest = 3, largest = 3*3 = 9Biconcave components = 128.) For the loop-free connected undirected graph G in Fig. 12.43(i), order the vertices alphabetically.a) Determine the depth-first spanning tree T for G with e as the root. b) Apply the algorithm developed in this section to the tree T in part (a) to find the articulation points and biconnected components of G.PLEASE PLACE ANSWER HERE (in red)A,b,c, d, e, f, g, h. Articulation points are d, f, and a. Discussion Question: You are an electrical engineer designing a new integrated circuit involving potentially millions of components.

How would you use graph theory to organize how many layers your chip must have to handle all of the interconnections, for example? Which properties of graphs come into play in such a circumstance?If the likelihood of the edge (v1, v2) is 50%, then there are equal chances that that edge will not be a section of the edge set. Similarly, for all the pair of vertices we can say that there is equal probability of having or not having an edge between those two. So, if there are n vertices in the vertex set then there can be maximum n "single connected component" (in which no edge is there) of that graph or minimum one connected component in which all the vertices are connected to each other.