# 1. 22.1-2 Give An Adjacency-list Representation For A .

3y ago
65 Views
566.61 KB
11 Pages
Last View : 1m ago
Transcription

1. 22.1-2 Give an adjacency-list representation for a complete binary tree on 7 vertices.Give an equivalent adjacency-matrix representation. Assume that vertices are numberedfrom 1 to 7 as in a binary heap. (Edges are directed from parent to djacency 00002. 22.1-5 The square of a directed graph G (V, E) is the graph G2 (V, E2) such that(u,w) E2 if and only if for some v V, both (u,v) E and (v, w) E. That is, G2 containsan edge between u and w whenever G contains a path with exactly two edges between u andw. Describe efficient algorithms for computing G2 from G for both the adjacency-list andadjacency-matrix representations of G. Analyze the running times of your algorithms.G2 for an adjacency matrix: - Computing G2 may be done in V3 time by matrix multiplication:for i 1 to Vfor j 1 to V {G2[i][j] 0;for k 1 to Vif (g[i][k] 1 && g[k][j] 1) {G2[i][j] 1;break;}}

G2 for an adjacency list:Procedure G-Square (V[G], E[G])V[G2] ß V[G]for each u V[G]for each v Adj[u]for each w Adj[v]E[G2] ß {(u, w)} E[G2]3Run time O(V )3. 22.2-1 Show the d and Π values that result from running breadth-first search on thedirected graph of Figure 22.2(a), using vertex 3 as the source.-/-/-5/3/4123 1/0/-4564/2/52/1/33/1/34. 22.2-4 What is the running time of BFS if its input graph is represented by an adjacencymatrix and the algorithm is modified to handle this form of input?Each vertex can be explored once and its adjacent vertices must be determined too. This takesΘ(V2) time.5. Do a DFS on figure 22.6 (p.611). Classify each edge based on the DFS tree you /12 xTTCu18/1913/14Bz10/116. Find the strongly connected components in figure 22.6.From 5., the first DFS gives the list R U Q T Y X Z S U W (reverse order of turning black)

5/10rBCT17/18T7/8C16/19u3/4Cy11/14 xwCCtTBvqC15/20s1/2T6/9TBz12/13Strongly connected components are {s, w, v}, {q, y, t}, {x, z}, {r}, {u}7. 22.4-1 Show the ordering of vertices produced by TOPOLOGICAL-SORT when it isrun on the dag of Figure 22.8, under the assumption of Exercise /13p n o s m r y v x w z u q t8. 22.5-1 How can the number of strongly connected components of a graph change if anew edge is added?The number of strongly connected components can be reduced.

9. 22.5-3 Professor Bacon claims that the algorithm for strongly connected components canbe simplified by using the original (instead of the transpose) graph in the second depth-firstsearch and scanning the vertices in order of increasing finishing times. Is the professorcorrect?Consider102For this algorithm, the first DFS will give a list 1 2 0 for the second DFS. All vertices will beincorrectly reported to be in the same SCC.For the CLRS algorithm, the first DFS will give a list 0 2 1 for the second DFS. After reversingedges, the correct SCCs {0, 1} and {2} will be reported.10. 22.5-4 Prove that for any directed graph G, we have ((GT)SCC)T GSCC. That is, thetranspose of the component graph of GT is the same as the component graph of G.Since the strongly connected relationship is an equivalence relation, G and GT will always havethe same strongly connected components. If two vertices X and Y are not strongly connected,then there is a unique path from X to Y in G iff there is a unique path from Y to X in GT.A similar property will also hold for the component graph and transpose of the component graph,i.e. If two vertices X and Y are not strongly connected in G, then here is a unique path fromSCC(G,X) to SCC(G,Y) in (G)SCC iff there is a unique path from SCC(GT,Y) to SCC(GT,X) in(GT)SCC).11. 23.1-1Let (u, v) be a minimum-weight edge in a graph G. Show that (u, v) belongs to someminimum spanning tree of G.Let A be a subset of some MST T such that (u, v) A. To choose an edge to be added to A, allthe edges on the cut are considered and an edge with lowest weight is selected. Since (u, v) is theminimum weight edge in the graph G, it gets selected on some cut.

12. 24.3-1 Run Dijkstra’s algorithm on the directed graph of Figure 24.2, first using vertexs as the source and then using vertex z as the source. In the style of Figure 24.6, show the dand Π values and the vertices in set S after each iteration of the while loop.Black vertices are in the set S. The black, thick arrows are the values of Π and the values of d areincluded are listed inside each node.TA.6 3226 Y302YS 565YE.232S 565Y3203ZX632S 55ZY94111711T3726YF.941594162Z63ZXS 5X 33011T377T941265D. 413263Z6XS 5X337 TC.0T 4150B.30SX632711Z

Using Vertex Z as the source.TA.X6 3T 2415276 Y336241276 ZYC.75S0X 3 SB.03ZD.T33S66241XT7627568Y333S2X674127508ZY630Z

X63S0T3T33SF.30Z

13. a. Determine the transitive closure of the following Boolean matrix by using Warshall’salgorithm.1 011 00 011 01 000 01 011 10 001 0T(1) 1111100000111111111111111T(3) T(5) T(2) T(4) b. Convert the matrix to indicate successors and use the version of Warshall’s algorithmthat allows path tracing.02003-1-1-1-1-1220233303333043

14. 26.2-2In Figure 26.1(b), which is the flow across the cut ({s, v2, v4}, {v1, v3, t})? What is thecapacity of this /14Net flow across the cut is f(s, v1) f(v2,v1) f(v2,v3) f(v3,v4) f(v4,t) 11 1 -4 7 4 19 and its capacity is 16 14 7 4 v37994v44ts104419 / 207/7t911 / 1310v2v312 / 1612412 / 12v184s4/4v44 / 141210t914v112 / 204 / 134v4v312 / 1612412 / 12v184104v41412st7914v112/ 20134v4v312 / 1691312 / 12v12016v2v411 / 144/4

12v112v3141910s47t92113v24v41117 26.3-121s111111314 1116117111Augmenting patht18S ?1 ?6 ?195Flow N/W:21s1/111/1111314 11617111/11t181195Residual N/W:1121s111314 1151161171111891Augmenting pathtS ?2 ?8 ?tt

1121s111314 11116117111Augmenting patht18195Final Residual graph:11s21111134 1151161171111891tS ?3 ?7?t

5. Do a DFS on figure 22.6 (p.611). Classify each edge based on the DFS tree you determine. q t y x z s v w r u 1/16 2/7 3/6 4/5 10/11 9/12 8/15 13/14 18/19 17/20 T T T B T T B T T B T C C F 6. Find the strongly connected components in figure 22.6. From 5., the first DFS gives the list

Related Documents:

Come let us worship the Lord in the beauty of holiness. Give God the honor. Give God the praise. Come let us worship the Lord; Let's give God the praise. Worship God. Worship God. Give my God the glory. Give my God the praise. Worship God. Worship God. Come let us worship the Lord; Let's give God

Phrasal Verbs Made Easy PDF Capsule 6 - Give Etymology. Do you know in Old English the word 'give' was not present? They used 'giefan' (past tense: geaf, past participle: giefen) meaning to give, bestow, entrust, deliver to another, grant, commit and devote. In Middle English, it became 'given' and later, 'give' Give In . Meaning: 1.

Comin from the cities, comin from the wild I see a breathless army breakin like a cloud They re gonna smother love, they re gonna shoot your hopes Before the meek inherit they ll learn to hate themselves Singin , give me help, give me strength Give a soul a night of fearless sleep Give me love, give me peace

Mediterranean world. Your quiz can potentially give you a higher score on the midterm examination. A score of 100% will give 4% on the exam, 90-99% will give 3%, 80-89% will give 2% and 70-79% will give 1%. A list of sites to be identified for the quiz is on the la

Effective Feedback: To Give and How to Give. November 10, 2015 . professional development and resume building. Nira Geevargis is an Assistant Professor and Director of Externship Programs at the University . Writing is

Psalm 119:25 This is the first of many passionate requests found in Psalm 119, where the psalmist boldly appeals to the Source of Life to give him life! “Give me life in your ways” v.37 “In your steadfast love give me life” v.88 “Give me life, O Lord, according to your word!” v.107

1) Roll vs. Starship Combat Strategy and Tactics to give the captain a 1 toward his tactical advantage roll, 2) Roll vs. Leadership to give a 1 on any single attack, 3) Roll vs. Leadership to give a 1 on any single defense, or 4) Roll vs. Leadership to give a 10 to any single skill roll ed against by a bridge officer Often, an execu

give me liberty!: an american history (fifth brief edition) (vol. 1) 5th 9780393616217 nort req no foner give me liberty: brief (v1)(w/access) (v1) 5th 2017 9780393614152 w. w. req no amh 1020 01 kennedy 05/14/2018 foner give me liberty! brief (w/access code) (v2) 5th 2017 9780393614169 nort req no amh 1020 03 kennedy 05/14/2018 foner give me .