Test #4

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

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

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

There are of course, not the only possibilities.

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.

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

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

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:

Converted by