GRAPHS Homework

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


  2. Draw the call graph for the telephone numbers 555-0011, 555-1221, 555-1333, 555-8888, 555-2222, 555-0091, 555-1200 if there were 3 calls from 555-0011 to 555-8888 and 2 calls from 555-8888 to 555-0011, 2 calls from 555-2222 to 555-0091, 2 calls from 555-1221 to each of the other numbers, and 1 call from 555-1333 to each of 555-0011, 555-1221, 555-1200.


  3. Given the following undirected graph.
    1. Find the number of vertices, the number of edges, and the degree of each vertex.  
      Identify all isolated and pendant vertices.
    2. Find the sum of the degrees of the vertices and verify that it equals twice the number of edges in the graph.

  4. Determine the number of vertices and edges and find the indegree and outdegree of each vertex of the given directed multigraph.
  5. Draw the following graphs.


    1. C7
    2. K7
    3. W7
    4. K4,4
    5. K1,8

  6. For what values of n are these graphs bipartite?


    1. Kn
    2. Cn
    3. Qn
    4. Wn

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


    1. Model the possible marriages on the island using a bipartite graph.
    2. 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.

  8. Find the union of the given pair of simple graphs assuming edges with the same endpoints are the same.
  9. Represent the given digraph with an adjacency list, an adjacency matrix and an incidence matrix.
  10. Find the adjacency matrix of each of the following graphs:


    1. Cn
    2. Kn
    3. Km,n
    4. Qn
    5. Wn

  11. Determine if the following graphs are isomorphic.
  12. Find the number of paths between c and f in the given graph of length 2, 3, 4, 5, 6, 7.
  13. Show that given graph G1 is connected whereas given graph G2 is not connected.
  14. Show that every connected graph with n vertices has at least n – 1 edges that is not a loop.


  15. Can someone cross all the bridges shown in the map below exactly once and return to the starting point?
  16. 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.
  17. 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.
  18. 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.


  19. Given the graphs below


    1. Find the shortage route and preferably with the least connections between Los Angeles and Boston.
    2. Find the fastest route between Los Angeles and Boston.
    3. Find the cheapest route between Los Angeles and Boston.

  20. 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.
  21. Determine whether the given graph is planar, and if it is, draw it so that no edges cross.
  22. Determine whether the given graph is homeomorphic to K3,3.
  23. Find the chromatic number of the given graph.
  24. Find the chromatic number of the given graph.
  25. 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.


  26. 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?


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

  28. 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)


© 2002-09-13 cpsm ; last update 2010-08-10 0:53