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

Computer programs can be very complex, containing thousands (or millions) of lines of code and performing millions of operations per second. Given this, how can we possibly know that a particular computer program's results are correct? Do some research on this topic then think carefully about your response. Also, explain how YOU would approach testing a large problem. Your answer must be thoughtful and give some insight into why you believe your steps would be helpful when testing a large program.

Could you fix this? My marker has commented, What's missing? The input list is the link below. https://gmierzwinski.github.io/bishops/cs321/resources/CS321_Assignment_1_Input.txt result.put(true, dishwasherSum); result.put(false, sinkSum); return result; }}

PLEG136: Week 5 Portofolio Project Motion to Compel

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