Draw depth-first tree that results when algorithm is applied

Assignment Help Data Structure & Algorithms

Reference no: EM131320284

EXERCISES for Section 4.2

In Exercises 4.2.1 through 4.2.7, draw the depth-first tree that results when Algorithm 4.2.1 is applied to the graph shown below, starting at the specified vertex. Include the dfnumbers and use: (a) lexicographic order as the default priority; (b) reverse lexico¬graphic order as the default priority.

4.2.1^s Vertex w.
4.2.2 Vertex u.
4.2.3 Vertex x.
4.2.4 Vertex y.
4.2.5^s Vertex t.
4.2.6 Vertex z.
4.2.7 Vertex s.

EXERCISES for Section 4.3

Larcises 4.3.1 through 4.3.4, apply prior's algorithm (Algorithm 4.3.1) to the given w ighled graph, starting at vertex s and resolving ties as in Example 4.3.1. Draw the minimum spanning tree that results, and indicate its total weight. Also give the discovery number at each vertex.

In Exercises 4.3.5 through 4.3.8, apply Dijkstra's algorithm (Algorithm 4.3.2) to the given weighted graph, starting at vertex s and resolving ties as in Example 4.3.3. Draw the shortest-path tree that results, and indicate for each vertex v, the discovery number and the distance from vertex s to v.

4.3.5^s The graph of Exercise 4.3.1. 4.3.6 The graph of Exercise 4.3.2.
4.3.7 The graph of Exercise 4.3.3. 4.3.8 The graph of Exercise 4.3.4.

4.3.9 Suppose that the weighted graph shown below represents a communication network, where the weight pii on arc ij is the probability that the link from i to j does not fail. If the link failures are independent of one another, then the probability that a path does not fail is the product of the link probabilities for that path. Under this assumption, find the most reliable path from s to t. (Hint: Consider -logiopii.)

EXERCISES for Section 4.4

In Exercises 4.4.1 through 4.4.7, (a) give the dfnumber and low values for each vertex that result from a depth-first search on the graph shown, starting at the specified vertex. Use the alphabetical order of the vertex names as the default priority; (b) verify the characterization given by Corollary 4.4.12 for the calculations of part (a).

4.4.1^s Vertex a.
4.4.2 Vertex b.
4.4.3 Vertex c.
4.4.4 Vertex e.
4.4.5^s Vertex g.
4.4.6 Vertex i.
4.4.7 Vertex f .

4.4.8 Prove that a postorder traversal of a depth-first tree reproduces the finish order of the depth-first search.

EXERCISES for Section 5.4

In Exercises 5.4.1 through 5.4.4, identify the blocks in the given graph and draw the block graph.

5.4.1^s

In Exercises 6.1.6 through 6.1.9, apply Algorithm 6.1.1 to construct an E ulFrian tour of the given graph. Begin the construction at vertex s.

252 Chapter 6 OPTIMAL GRAPH TRAVERSALS

In Exercises 6.1.16 through 6.1.19, use an appropriate modification of Algorithm 6.1.1 to construct an eulerian tour or open eulerian trail in the given digraph.

In Exercises 6.2.12 through 6.2.15, apply Algorithm 6.2.2 to find a minimum-weight postman tour for the given weighted graph. Determine whether the solution is unique.

In Exercises 6.3.6 through 6.3.10, draw the specified graph or prove that it does not exist.

6.3.6s An 8-vertex simple graph with more than 8 edges that is both eulerian and hamiltonian.

6.3.7 An 8-vertex simple graph with more than 8 edges that is eulerian but not hamiltonian.

6.3.8 An 8-vertex simple graph with more than 8 edges that is hamiltonian but not eulerian.

6.3.9 An 8-vertex simple hamiltonian graph that does not satisfy the conditions of Ore's theorem.

6.3.10 A 6-vertex simple graph with 10 edges that is not hamiltonian.

Attachment:- Graph Theory.pdf

Reference no: EM131320284

Questions Cloud

Create presentation in which you explore the security tasks : For this assessment, create a presentation in which you explore the security tasks that systems administrators should be knowledgeable about

Write a function that will calculate the current persons bmi : Write a function that will prompt for the current person's height in FEET and INCHES and return total height in INCHES. Write a function that will calculate and return the current person's BMI.

Differentiate between motherboard components : Use built-in diagnostics and monitoring. Differentiate between motherboard components. Compare and contrast RAM types and features

Implications did this have for superpower relations : Why did Gorbachev choose the United Nations as his forum for this speech? What did Gorbachev mean by "de-ideologizing relations among states? What implications did this have for superpower relations?

Draw depth-first tree that results when algorithm is applied : In Exercises 4.2.1 through 4.2.7, draw the depth-first tree that results when Algorithm 4.2.1 is applied to the graph shown below, starting at the specified vertex.

Discuss the overview of flexible forms of organizing : Your answer for this question should discuss the overview of flexible forms of organizing and include examples of organizations who those flexible forms

Reconstruction as a constitutional revolution : Discuss the Radical Reconstruction as a Constitutional Revolution.

Economy exposure to panics and recessions : How could the federal government at the time of the Gilded Age have reduced the economy's exposure to panics and recessions?

Relationship between islam-judaism and christianity : Islam and the other monotheistic religions: Write an essay discussing the relationship between Islam, Judaism and Christianity. What does the Qur'an say about the "Peoples of the Book," and how they are to be treated?

User Account

All Pages