Introduction to Algorithms
Introduction to Algorithms
3rd Edition
ISBN: 9780262033848
Author: Thomas H. Cormen, Ronald L. Rivest, Charles E. Leiserson, Clifford Stein
Publisher: MIT Press
Question
Book Icon
Chapter 22, Problem 1P

(a)

Program Plan Intro

To prove the breath first search properties in an undirected graph.

(a)

Expert Solution
Check Mark

Explanation of Solution

In the undirected graph, breath first search follow properties as:

Suppose in the undirected graph an edge ( u , v ) is consider as forward or back edge then vertex ‘ u’ should occur before vertex ‘ v’ and edges associated with ‘ u’ should be explore before any other edge in breath first search. Thus, the edge ( u , v ) can be considered as the tree edge because there is no forward and backward edge in undirected graph BFS traversal.

In the breath first search, an edge must be a tree if [v.π]=u and this can be possible if [v.d]=[u.d]+1 . In this values of [ u.d ] and [ v.d ] cannot be changed after initialization. So, in the breath first search [v.d]=[u.d]+1 .

Therefore for every tree edge ( u, v ) in breath first search, [v.d]=[u.d]+1 .

If vertex ‘ u’ visit before vertex ‘ v’ , and edge ( u, v ) is cross edge. As the properties of tree edge and cross edge, vertex ‘ u’ visit before vertex ‘ v’ that means vertex ‘ v’ must be in the queue. Hence, from the given statement, it will follow the condition for the cross edge ( u, v ):

Therefore, [v.d]=[u.d]+1 or [v.d]=[u.d].

(b)

Program Plan Intro

To prove the breath first search properties in the directed graph.

(b)

Expert Solution
Check Mark

Explanation of Solution

Breath first search properties in the directed graph as follows:

An edge ( u, v ) is not the tree edge if the given graph G is directed. So, the graph will not contain the forward edge ( u, v ).

In the breath first search, an edge must be a tree if [v.π]=u and this can be possible if [v.d]=[u.d]+1 . In this values of [ u.d ] and [ v.d ] cannot be change after initialization. So, in the breath first search [v.d]=[u.d]+1 . Therefore, for every tree edge ( u, v ) in breath first search, [v.d]=[u.d]+1 .

If vertex ‘ u’ visit before vertex ‘ v’ , and edge ( u, v ) is cross edge. As the properties of tree edge and cross edge, vertex ‘ u’ visit before vertex ‘ v’ that means vertex ‘ v’ must be in the queue. Hence, from the given statement, it will follow the condition for the cross edge ( u, v ):

Therefore, [v.d]=[u.d]+1 or [v.d]=[u.d] .

By seeing the above statements, it is clear for all vertices, 0[v.d] .

In the breath first search, back edge (u, v) where vertex ‘v’ is the ancestor of vertex ‘u’ and from the given vertices if the drawn edge is larger than the other. Hence, [v.d][u.d] .

Therefore, for every back edge (u, v), 0[v.d][u.d] .

Want to see more full solutions like this?

Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!
Students have asked these similar questions
23:12 Chegg content://org.teleg + 5G 5G 80% New question A feed of 60 mol% methanol in water at 1 atm is to be separated by dislation into a liquid distilate containing 98 mol% methanol and a bottom containing 96 mol% water. Enthalpy and equilibrium data for the mixture at 1 atm are given in Table Q2 below. Ask an expert (a) Devise a procedure, using the enthalpy-concentration diagram, to determine the minimum number of equilibrium trays for the condition of total reflux and the required separation. Show individual equilibrium trays using the the lines. Comment on why the value is Independent of the food condition. Recent My stuff Mol% MeOH, Saturated vapour Table Q2 Methanol-water vapour liquid equilibrium and enthalpy data for 1 atm Enthalpy above C˚C Equilibrium dala Mol% MeOH in Saturated liquid TC kJ mol T. "Chk kot) Liquid T, "C 0.0 100.0 48.195 100.0 7.536 0.0 0.0 100.0 5.0 90.9 47,730 928 7,141 2.0 13.4 96.4 Perks 10.0 97.7 47,311 87.7 8,862 4.0 23.0 93.5 16.0 96.2 46,892 84.4…
You are working with a database table that contains customer data. The table includes columns about customer location such as city, state, and country. You want to retrieve the first 3 letters of each country name. You decide to use the SUBSTR function to retrieve the first 3 letters of each country name, and use the AS command to store the result in a new column called new_country.  You write the SQL query below. Add a statement to your SQL query that will retrieve the first 3 letters of each country name and store the result in a new column as new_country.
We are considering the RSA encryption scheme. The involved numbers are small, so the communication is insecure.  Alice's public key (n,public_key) is (247,7). A code breaker manages to factories  247 = 13 x 19  Determine Alice's secret key. To solve the problem, you need not use the extended Euclid algorithm, but you may assume that her private key is one of the following numbers 31,35,55,59,77,89.
Knowledge Booster
Background pattern image
Similar questions
SEE MORE QUESTIONS
Recommended textbooks for you
Text book image
Operations Research : Applications and Algorithms
Computer Science
ISBN:9780534380588
Author:Wayne L. Winston
Publisher:Brooks Cole
Text book image
Fundamentals of Information Systems
Computer Science
ISBN:9781305082168
Author:Ralph Stair, George Reynolds
Publisher:Cengage Learning
Text book image
CMPTR
Computer Science
ISBN:9781337681872
Author:PINARD
Publisher:Cengage
Text book image
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
Text book image
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Text book image
Principles of Information Systems (MindTap Course...
Computer Science
ISBN:9781285867168
Author:Ralph Stair, George Reynolds
Publisher:Cengage Learning