Description

5 attachmentsSlide 1 of 5attachment_1attachment_1attachment_2attachment_2attachment_3attachment_3attachment_4attachment_4attachment_5attachment_5

Unformatted Attachment Preview

Give an example of an application of a graph, in which the minimum

spanning tree would be of importance. Describe what the vertices,

edges and edge weights of the graph represent. Explain why finding a

minimum spanning tree for such a graph would be important.

CMSC 451 Homework 5

1. Execute Prim’s minimum spanning tree algorithm by hand on the graph below showing

how the data structures evolve specifically indicating when the distance from a fringe

vertex to the tree is updated. Clearly indicate which edges become part of the minimum

spanning tree and in which order. Start at vertex A.

2

3

A

7

5

6

4

G

3

1

F

B

I

4

H

8

2

6

E

C

2

2

1

D

2. Execute Kruskal’s algorithm on the weighted tree shown below. Assume that edges of

equal weight will be in the priority queue in alphabetical order. Clearly show what

happens each time an edge is removed from the priority queue and how the dynamic

equivalence relation changes on each step and show the final minimum spanning tree that

is generated.

3. Give an example of a weighted graph for which the minimum spanning tree is unique.

Indicate what the minimum spanning tree is for that graph. Give another example of a

weighted graph that has more than one minimum spanning tree. Show two different

minimum spanning trees for that graph. What determines whether a graph has more than

one minimum spanning tree?

4. Given the following adjacency lists (with edge weights in parentheses) for a directed

graph:

A: B(5), C(3), D(1)

B: C(1), D(3)

C: B(3), D(7), E(1)

D: A(6), C(3)

E: F(5)

F: D(3), A(4)

Execute Dijkstra’s shortest-path algorithm by hand on this graph, showing how the data

structures evolve, with A as the starting vertex. Clearly indicate which edges become part

of the shortest path and in which order.

Grading Rubric

Problem

Problem 1

Problem 2

Problem 3

Meets

10 points

Does Not Meet

0 points

Indicated when the distance from a

fringe vertex to the tree was updated

(3)

Did not indicate when the distance

from a fringe vertex to the tree was

updated (0)

Indicated which edges became part of

the minimum spanning tree and in

which order (3)

Did not indicate which edges became

part of the minimum spanning tree and

in which order (0)

Provided the correct final minimum

spanning tree (4)

Did not provide the correct final

minimum spanning tree (0)

10 points

0 points

Showed what happened each time an

edge was removed from the priority

queue (3)

Did not show what happened each

time an edge was removed from the

priority queue (0)

Showed how the dynamic equivalence

relation changed on each step (3)

Did not show how the dynamic

equivalence relation changed on each

step (0)

Provided the correct final minimum

spanning tree (4)

Did not provide the correct final

minimum spanning tree (0)

10 points

0 points

Provided a correct example of a

weighted graph for which the

minimum spanning tree is unique (2)

Did not provide a correct example of a

weighted graph for which the

minimum spanning tree is unique (0)

Provided the correct unique minimum

spanning tree for that graph (2)

Did not provide the correct unique

minimum spanning tree for that graph

(0)

Provided a correct example of a

weighted graph that has more than

one minimum spanning tree (2)

Did not provide a correct example of a

weighted graph that has more than

one minimum spanning tree (0)

Provided two correct distinct minimum

spanning trees for that graph (2)

Did not provide two correct distinct

minimum spanning trees for that graph

(0)

Correctly explained what determines

whether a graph has more than one

minimum spanning tree (2)

Did not correctly explain what

determines whether a graph has more

than one minimum spanning tree (0)

Problem 4

10 points

0 points

Clearly indicated which edges became

part of the shortest path and in which

order (5)

Did not clearly indicate which edges

became part of the shortest path and

in which order (0)

Provided correct final shortest path

tree (5)

Did not provide correct final shortest

path tree (0)

CMSC 451 Homework 6

1. Using Warshall’s algorithm, compute the reflexive-transitive closure of the relation below.

Show the matrix after the reflexive closure and then after each pass of the outermost for loop

that computes the transitive closure.

0

1

0

0

[1

0

0

0

0

0

0

0

1

1

1

0

0

1

0

0

1

0

0

0

1]

2. Using the matrix in the previous problem show the final result of executing Floyd’s

algorithm on that matrix to produce a matrix containing path lengths.

3. Show the graph that corresponds to the matrix in the first problem assuming the rows and

columns correspond to the vertices a, b, c, d and e. Show its condensation graph, renaming its

vertices. Determine any topological order of that graph and create an adjacency matrix with

the vertices ordered in that topological order. Finally compute the reflexive-transitive closure

of that matrix. What characteristic of that matrix indicates that it defines a total order?

4. Using Floyd’s algorithm, compute the distance matrix for the weight directed graph defined

by the following matrix:

0

2

4

0

2

5

3 3

[

]

0

−2 −4 0

Show the intermediate matrices after each iteration of the outermost loop.

Grading Rubric

Problem

Problem 1

Meets

10 points

Does Not Meet

0 points

Showed the correct matrix after the

reflexive closure (2)

Did not show the correct matrix after

the reflexive closure (0)

Showed the correct matrices after each

pass of the outermost for loop that

computes the transitive closure (8)

Did not show the correct matrices after

each pass of the outermost for loop

that computes the transitive closure (0)

Problem 2

Problem 3

Problem 4

10 points

0 points

Showed the correct final result of

executing Floyd’s algorithm on that

matrix to produce a matrix containing

path lengths (10)

Did not show the correct final result of

executing Floyd’s algorithm on that

matrix to produce a matrix containing

path lengths (0)

10 points

0 points

Showed the correct graph that

corresponds to the matrix in the first

problem assuming vertices a, b, c, d

and e (1)

Did not show the correct graph that

corresponds to the matrix in the first

problem assuming vertices a, b, c, d

and e (0)

Showed its correct condensation

graph, renaming its vertices (2)

Did not show its correct condensation

graph, renaming its vertices (0)

Determined a correct topological order

of that graph (2)

Did not determine a correct topological

order of that graph (0)

Created a correct adjacency matrix

with the vertices ordered in that

topological order (1)

Did not create a correct adjacency

matrix with the vertices ordered in that

topological order (0)

Correctly computed the reflexivetransitive closure of that matrix (2)

Correctly explained what characteristic

of that matrix indicates that it defines a

total order (2)

Did not correctly compute the

reflexive-transitive closure of that

matrix (0)

Did not correctly explain what

characteristic of that matrix indicates

that it defines a total order (0)

10 points

0 points

Showed the correct intermediate

matrices after each iteration of the

outermost loop using Floyd’s algorithm

(7)

Did not show the correct intermediate

matrices after each iteration of the

outermost loop using Floyd’s algorithm

(0)

Showed the correct final matrix after

executing Floyd’s algorithm (3)

Did not show the correct final matrix

after executing Floyd’s algorithm (0)

Give an example of an application of a graph, in which the minimum

spanning tree would be of importance. Describe what the vertices,

edges and edge weights of the graph represent. Explain why finding a

minimum spanning tree for such a graph would be important.

Give an example of an application of a graph, in which determining all pairs shortest paths

would be of importance. Describe what the vertices, edges and edge weights of the graph

represent. Explain the significance of the shortest path for such a graph and why it would be

important.

Purchase answer to see full

attachment

Explanation & Answer:

1 Discussion 4 Problems Solutions

User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.