GRAPHS Homework

Draw the acquaintanceship graph that represents that Tom and Patricia, Tom and Hope, Tom and Sandy, Tom and Amy,
Tom and Marika, Jeff and Patricia, Jeff and Mary, Patricia and Hope, Amy and Hope, Amy and Marika know each other,
but none of the other pairs of people listed know each other.

Draw the call graph for the telephone numbers 5550011, 5551221, 5551333, 5558888, 5552222, 5550091,
5551200 if there were 3 calls from 5550011 to 5558888 and 2 calls from
5558888 to 5550011, 2 calls from 5552222 to 5550091, 2 calls from
5551221 to each of the other numbers, and 1 call from 5551333 to each of 5550011,
5551221, 5551200.
 Given the following undirected graph.

Find the number of vertices, the number of edges, and the degree of each vertex.
Identify all isolated and pendant vertices.

Find the sum of the degrees of the vertices and verify that it equals twice the number of edges in the graph.

Determine the number of vertices and edges and find the indegree and outdegree of each vertex of the given directed
multigraph.
 Draw the following graphs.
 C_{7}
 K_{7}
 W_{7}
 K_{4,4}
 K_{1,8}
 For what values of n are these graphs bipartite?
 K_{n}
 C_{n}
 Q_{n}
 W_{n}

Suppose that there are five young women and six young men on an island.
Each woman is willing to marry some of the men on island and each man is willing to marry any woman who is willing
to marry him.
Suppose that Anna is willing to marry Jason, Larry, and Matt;
Barbara is willing to marry Kevin and Larry;
Carol is willing to marry Jason, Nick, and Oscar;
Diane is willing to marry Jason, Larry, Nick, and Oscar;
Elizabeth is willing to marry Jason and Matt.
 Model the possible marriages on the island using a bipartite graph.

Find a matching of the young women and the young men on the island such that each young woman is matched with
a young man whom she is willing to marry.

Find the union of the given pair of simple graphs assuming edges with the same endpoints are the same.
 Represent the given digraph with an adjacency list, an adjacency matrix and an incidence matrix.
 Find the adjacency matrix of each of the following graphs:
 C_{n}
 K_{n}
 K_{m,n}
 Q_{n}
 W_{n}
 Determine if the following graphs are isomorphic.
 Find the number of paths between c and f in the given graph of length 2, 3, 4, 5, 6, 7.

Show that given graph G_{1} is connected whereas given graph G_{2} is not connected.

Show that every connected graph with n vertices has at least n – 1 edges that is not a loop.
 Can someone cross all the bridges shown in the map below exactly once and return to the starting point?

Determine if the given graph has an Euler circuit and construct such a circuit if one exists.
If no Euler circuit exists, determine if the graph has an Euler path and construct such a path if one exists.

Determine if the given digraph has an Euler circuit and construct such a circuit if one exists.
If no Euler circuit exists, determine if the graph has an Euler path and construct such a path if one exists.

Show that finding a knight's tour on an 8 x 8 chessboard is equivalent to finding a Hamiltonian path
representing the legal moves of a knight on that board.
 Given the graphs below
 Find the shortage route and preferably with the least connections between Los Angeles and Boston.
 Find the fastest route between Los Angeles and Boston.
 Find the cheapest route between Los Angeles and Boston.

Solve the traveling salesman problem for the given graph by finding the total weight of all Hamiltonian circuits
and determining a circuit with minimum total weight.
 Determine whether the given graph is planar, and if it is, draw it so that no edges cross.
 Determine whether the given graph is homeomorphic to K_{3,3}.
 Find the chromatic number of the given graph.
 Find the chromatic number of the given graph.

What is the least number of colors needed to color a map of the USA?
Do not consider adjacent states that meet only at a corner.
Suppose that Michigan is one region.
Consider the vertices representing Alaska and Hawaii as isolated vertices.

How many different channels are needed for 6 stations located at the distances shown in given table, it
2 stations cannot use the same channel when they are within 150 miles of each other?

1 
2 
3 
4 
5 
6 
1 

85 
175 
200 
50 
100 
2 
85 

125 
175 
100 
160 
3 
175 
125 

100 
200 
250 
4 
200 
175 
100 

210 
200 
5 
50 
100 
200 
210 

100 
6 
100 
160 
250 
220 
100 


A zoo wants to set up natural habitats in which to exhibit its animals.
Unfortunately, some animals will eat some of the others when given the opportunity.
How can a graph model and coloring be used to determine the number of different habitats needed
and the placement of the animals in these habitats?
Solutions to Homework on Graphs
(to be posted after the due date)
© 20020913 cpsm ; last update
20100810 0:53