Math 2602

April 13 , 2000
Test #4

Open Book and Notes. You have 50 minutes. Carefully explain your proceedures and answers

All answers should be given exactly (no decimals) if possible.
    
    Note: It is your responsibility to write your answers out in a way that is legible and understandable by the grader(s).

Problem 1 (5 points each)

a: Find an Euler cycle in the complete graph on 5 vertices.

b: Find a Hamiltonian cycle on the complete graph on 6 vertices.

Answer

There are of course, not the only possibilities.

Problem  2 (10 Points)

The above represents states in a markov chain. The transitions are

At 2 and 3, the probability is 1/3 moving to the left one step.
At 2 and 3 the probability os 2/3 moving to the right one step
At the end points, the probability is 1/4 staying there, and 3/4
moving (to the right for 1, to the left for 4) one step.

Write out the matrix for the markov chain.

Write out the equations you have to solve to find the
long term prbabilities of being at 1,2,3,4.

b: Different markov chain: 2,3 are same as above, but 1 and 4 are absorbing. Write the matrix of the markov chain, with the absorbing states corresponding to the 1st columns (and rows).  Find the probabilities for ending in 1 and 4, given that you started at 2 and given that you started at 3. This is a matrix. Find it BY MATRIX METHODS.

Answer

Work

b: States in matrix are 1,4,2,3 in that order.

Problem 3: (10 points)

Find akll soluutions to Ax = b, where  A = , and   b =

Ans

Or is a slighly nicer format:
      + 2   + 3   + 4   =  16
      + 2   +      +      =  8
2    + 4   + 4   + 5   =  24

Gaussian elimination. Substract the 1st from the second and twice the first from the third:

      + 2   + 3   + 4   =    16
                         -2    - 3   = -  8
                        - 2    -3   =  -  8

The third is the same, so drop it.


      + 2   + 3   + 4   =    16
                         -2    - 3   = -  8
                         
  Set    = t,   = s and solve: