Scribd
Upload
303 views1 page

Homework 12

1. The homework assignment asks students to complete several graph theory problems involving bipartite graphs, adjacency matrices, and Dijkstra's algorithm. 2. Students are to draw the graphs represented by two adjacency matrices and determine if they are isomorphic. 3. A problem involving a father and three children crossing a rope bridge is posed and students are asked to model it as a bipartite graph and find two solutions involving seven crossings each. 4. Dijkstra's algorithm is to be applied to a graph to find the shortest path from vertex a to t.

Uploaded by

Anonymous KEzv1IMF
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
303 views1 page

Homework 12

1. The homework assignment asks students to complete several graph theory problems involving bipartite graphs, adjacency matrices, and Dijkstra's algorithm. 2. Students are to draw the graphs represented by two adjacency matrices and determine if they are isomorphic. 3. A problem involving a father and three children crossing a rope bridge is posed and students are asked to model it as a bipartite graph and find two solutions involving seven crossings each. 4. Dijkstra's algorithm is to be applied to a graph to find the shortest path from vertex a to t.

Uploaded by

Anonymous KEzv1IMF
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

Homework – Module 12

Complete the following problems, on your own and turn them in by Tuesday midnight. Please
show all your work and make sure you have answered all the parts of each question. You may
find it helpful to illustrate a problem with an example, but remember that examples are not proof.
1. (9 points) For which values of n are the following graphs bipartite? Justify your answer.

(a) (2 points) The complete graph Kn.


(b) (3 points) The cycle graph Cn.
(c) (4 points) The hypercube graph Qn. (Hint: each vertex label has either an even or odd number
of 1s.)

2. (7 points) For the following adjacency matrices:

[ ] [ ]
0 1 0 1 1 0 1 0 0 1
1 0 1 0 0 1 0 1 1 1
A1 = 0 1 0 1 1 A2 = 0 1 0 1 0
1 0 1 0 1 0 1 1 0 1
1 0 1 1 0 1 1 0 1 0

a) (4 points) Draw the simple (undirected) graphs represented by A1 and A2.


b) (3 points) Determine whether the graphs in (a) are isomorphic. Give an explicit isomorphism
or a rigorous argument that none exists.

3. (10 points) A man is hiking with his three children, Alice, Bob, and Charlie, and all four must
get across a rope bridge. None of the children can cross alone, and the father can only escort at
most one child across at a time. Furthermore, Alice and Bob will fight if left unsupervised (i.e., if
the father is on one side of the bridge with Alice and Bob on the other), and Bob and Charlie will
also fight if left unsupervised. The problem is to find a sequence of crossings that gets the entire
family from one side of the bridge to the other.

a) (5 points) Construct a bipartite graph with a vertex for each possible state of the problem,
indicating which side of the rope bridge each family member is on, with an edge between
vertices corresponding to a trip across the bridge.
b) (5 points) Find paths in the graph corresponding to two different solutions, each involving
seven crossings.

4. (11 points) Apply Dijkstra’s algorithm to the following graph and construct the shortest path
from one side to the other. Start at a.
(b) Then give the shortest path from a to t.

a 5 b 4 c 3 d 2 e

4 2 3 1 5 7 7 5 2

f 2 g 4 h 3 i 5 j

3 2 4 3 2 3 2 5 2

k 3 l 4 m 3 n 1 o

2 4 1 4 2 3 2 1 2

p 2 q 4 r 1 s 2 t

You might also like