MTH 108                                      Sample Exam Chapter 1, 2

 

      1.   What is the valence of vertex A in the graph below?

           

            A)   3    B)  4    C)  5    D)  6

 

      2.   Which of the graphs below are connected?

           

            A)   I only    B)  II only    C)  I and II both    D)  Neither I or II

 

      3.   Which of the graphs below have Euler circuits?

           

            A)   I only    B)  II only    C)  I and II both    D)  Neither I or II

 

      4.   Consider the paths represented by the numbered sequence of edges on the graphs below. Which path represents an Euler circuit?

           

            A)   I only    B)  II only    C)  I and II both    D)  Neither I or II

 

      5.   Consider the path represented by the sequence of numbered edges on the graph below. Why does the path not represent an Euler circuit?

           

            A)   The path does not start and stop at the same vertex.

            B)   The path does not cover every edge of the graph.

            C)   The path uses some edges more than one time.

            D)   The path does not touch each vertex of the graph.

 

 

 

      6.   Consider the path represented by the numbered sequence of edges of the graph below. Which statement is true?

           

            A)   The path is not a circuit.

            B)   The path is an Euler circuit.

            C)   The path is a circuit, but not an Euler circuit.

            D)   None of the above

 

      7.   In order to eulerize the graph below, give the fewest number of edges that need to be added or duplicated?

           

           

            A)   1    B)  2    C)  3    D)  4

 

      8.   If a graph had 8 vertices of odd valence, what is the absolute minimum number of edges that would need to be added (duplicated) to eulerize the graph?

            A)   2    B)    4    C)    6    D)    8

 

      9.   Which of the graphs shown below gives the best eulerization of the given graph. (In the graphs below, added edges are denoted with zig-zag lines.)

           

 

 

 

 

 

    10.   For the street network shown below, which graph would be most useful for routing a garbage truck? Assume all streets are two way and that passing down a street once would be sufficient to collect from both sides.

           

 

    11.   Which of the following describes a Hamiltonian circuit for the graph below?

           

           

            A)   ABCDEFGA    B)  ACBAEGFDEA    C)  ACBFGDEA    D)  ABCDGEF

 

 

 

 

 

 

 

 

 

 

 

 

 

    12.   On the graph below, which routing is produced by using the nearest-neighbor algorithm to solve the traveling salesman problem?

           

            A)   ABCDA    B)  ABDCA    C)  ACBDA    D)  ABCD

 

    13.   On the graph below, which routing is produced by using the sorted-edges algorithm to solve the traveling salesman problem?

           

            A)   ABCDA    B)  ABDCA    C)  ACBDA    D)  ABCD

 

    14.   Use Kruskal's algorithm for minimum-cost spanning trees on the graph below. The cost of the tree found is:

           

            A)   23    B)    20    C)    16    D)    5

 

 

 

 

 

 

 

 

 

 

    15.   What is the earliest possible completion time for a job whose order-requirement is shown below?

           

            A)   27    B)    17    C)    21    D)    48

 

    16.   Suppose an employee of a power company needs to read the electricity meters outside of each house along the streets in a residential area. The technique most likely to be useful in solving this problem is

            A)   finding a Euler circuit on a graph.

            B)   applying the nearest-neighbor algorithm for the traveling salesman problem.

            C)   applying Kruskal's algorithm for finding a minimum-cost spanning tree for a graph.

            D)   None of these techniques is likely to apply.

 

    17.   Given the two graphs shown below, which one represents a tree?

           

            A)   I only    B)    II only    C)    I and II both    D)    Neither I or II

 

    18.   In which of the diagrams below do the wiggled edges represent spanning trees?

           

            A)   I only    B)   II only    C)  I and II both    D)    Neither I or II

 

    19.   Identify an Euler circuit on the graphs below by numbering the sequence of edges in the order traveled.

             

 

 

 

    20.   Add wiggly edges to find an efficient Eulerization of the graphs shown below.

             

 

    21.   Find an Euler circuit on the graph on the left and use it to find a circuit on the graph on the right that reuses 3 edges.

           

           

 

    22.   Use the brute force algorithm to solve the traveling salesman problem for the graph of the four cities shown below.

           

           

 

    23.   The local cafe offers 3 different entrees, 10 different vegetables, and 4 different salads. A "blue plate special" includes an entree, a vegetable, and a salad. How many different ways can a special be constructed?