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…

5. Fleury's algorithm is an optimisation solution for finding a Euler Circuit of Euler Path in a graph, if they exist. Describe how this algorithm will always find a path or circuit if it exists. Describe how you calculate if the graph is connected at each edge removal. Fleury's Algorithm: The algorithm starts at a vertex of v odd degree, or, if the graph has none, it starts with an arbitrarily chosen vertex. At each step it chooses the next edge in the path to be one whose deletion would not disconnect the graph, unless there is no such edge, in which case it picks the remaining edge (a bridge) left at the current vertex. It then moves to the other endpoint of that edge and adds the edge to the path or circuit. At the end of the algorithm there are no edges left ( or all your bridges are burnt). (NOTE: Please elaborate on the answer and explain. Please do not copy-paste the answer from the internet or from Chegg.)

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…

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