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

Question

Want to see more full solutions like this?

Answer 1

Question

Chapter 22, Problem 1P

(a)

Program Plan Intro

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

(a)

Expert Solution

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

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

5. (This question goes slightly beyond what was covered in the lectures, but you can solve it by combining algorithms that we have described.) A directed graph is said to be strongly connected if every vertex is reachable from every other vertex; i.e., for every pair of vertices u, v, there is a directed path from u to v and a directed path from v to u. A strong component of a graph is then a maximal subgraph that is strongly connected. That is all vertices in a strong component can reach each other, and any other vertex in the directed graph either cannot reach the strong component or cannot be reached from the component. (Note that we are considering directed graphs, so for a pair of vertices u and v there could be a path from u to v, but no path path from v back to u; in that case, u and v are not in the same strong component, even though they are connected by a path in one direction.) Given a vertex v in a directed graph D, design an algorithm for com- puting the strong connected…

Part 2: Random GraphsA tournament T is a complete graph whose edges are all oriented. Given a completegraph on n vertices Kn, we can generate a random tournament by orienting each edgewith probability 12 in each direction.Recall that a Hamiltonian path is a path that visits every vertex exactly once. AHamiltonian path in a directed graph is a path that follows the orientations of thedirected edges (arcs) and visits every vertex exactly once. Some directed graphs havemany Hamiltonian paths.In this part, we give a probabilistic proof of the following theorem:Theorem 1. There is a tournament on n vertices with at least n!2n−1 Hamiltonian paths.For the set up, we will consider a complete graph Kn on n vertices and randomlyorient the edges as described above. A permutation i1i2 ...in of 1,2,...,n representsthe path i1 −i2 −···−in in Kn. We can make the path oriented by flipping a coin andorienting each edge left or right: i1 ←i2 →i3 ←···→in.(a) How many permutations of the vertices…

Given a graph that is a tree (connected and acyclic). (I) Pick any vertex v.(II) Compute the shortest path from v to every other vertex. Let w be the vertex with the largest shortest path distance.(III) Compute the shortest path from w to every other vertex. Let x be the vertex with the largest shortest path distance. Consider the path p from w to x. Which of the following are truea. p is the longest path in the graphb. p is the shortest path in the graphc. p can be calculated in time linear in the number of edges/vertices

Answer 2

Question

Chapter 22, Problem 1P

(a)

Program Plan Intro

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

(a)

Expert Solution

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

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!

Answer 3

Question

Chapter 22, Problem 1P

(a)

Program Plan Intro

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

(a)

Expert Solution

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

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!

Answer 4

Question

Chapter 22, Problem 1P

(a)

Program Plan Intro

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

(a)

Expert Solution

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

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!

Answer 5

Chapter 22, Problem 1P

(a)

Program Plan Intro

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

(a)

Expert Solution

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

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

Answer 6

Chapter 22, Problem 1P

(a)

Program Plan Intro

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

(a)

Expert Solution

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

Answer 7

Chapter 22, Problem 1P

(a)

Program Plan Intro

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

Answer 8

(a)

Expert Solution

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

Answer 9

(a)

Expert Solution

Answer 10

(a)

Expert Solution

Answer 11

Expert Solution

Answer 12

(b)

Program Plan Intro

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

(b)

Expert Solution

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

Answer 13

(b)

Program Plan Intro

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

Answer 14

(b)

Expert Solution

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