Help

Winter 2014 Math 330 Homework III

III.1 Determine the adjacency matrix, M for the following graph assuming the vertices are alphabetically ordered.

A // B

�� C

>>

//

��

D

OO >>

Eoo

F // G

>>

III.2 The following are some powers of the matrix M above. How many ways are there to go from node C to node D in either 3 or 4 steps?

M2 =

 

0 0 1 0 1 0 0 0 0 2 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0

 

M3 =

 

0 1 0 0 0 0 1 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 

M4 =

 

1 0 1 1 0 1 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 3 1 1 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 

M5 =

 

0 0 3 1 1 0 0 1 0 4 2 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 

III.3 A package service transports packages between Alderaan, Dagobah, and Tatooine. Half the packages from Alderaan remain on Alderaan, 30% of the packages from Alderaan go to Dagobah, and 20% of the packages from Alderaan go to Tatooine. 45% of the packages from Dagobah go to Alderaan and 55% of the packages from Dagobah go to Tatooine. 25% of the packages from Tatooine go to Alderaan, 35% of the packages from Tatooine go to Dagobah, and the remaining packages from Tatooine remain on Tatooine. Determine the Markov matrix, N, associated with this system.

—1—

Winter 2014 Math 330 Homework III

III.4 For the package system above the matrix N100 is given below. In the long run, how would you expect your delivery ships to be distributed across the three systems.

N100 =

 0.40 0.40 0.400.24 0.24 0.24

0.36 0.36 0.36

 

III.5 You are attempting to conquer the universe. The steps listed below must be completed in order to achieve this. Assuming you can only do two events at a time, what is the shortest time to conquer the universe and what order should the events be done?

1 year Conquer Castle Greyskull. You must Fly to Eternia and Train your Troops before doing this.

4 years Fly to Eternia. You must Build Your Fleet before doing this.

2 years Build Your Fleet. You must Design Your Fleet and Buy Materials before doing this.

5 years Buy Materials.

7 years Design Your Fleet.

3 years Recruit Your Soldiers.

2 years Train Your Soldiers. You must Build Your Fleet and Recruit Your Soldiers before doing this.

III.6 Assume that the employees and companies have the rankings below (rated highest to lowest) are given below. Find two stable matchings.

Student First Second Third Fourth Albert HP Bellcore AT&T Draper Barbara AT&T Bellcore Draper HP Calvin HP Draper AT&T Bellcore Dawn Draper AT&T Bellcore HP

Company First Second Third Fourth AT&T Dawn Albert Calvin Barbara Bellcore Calvin Barbara Albert Dawn HP Dawn Calvin Albert Barabara Draper Barbara Dawn Calvin Albert

—2—

Winter 2014 Math 330 Homework III

III.7 The four super heroes American Maid, Big Shot, Die Fledermaus, and Sewer Urchin need to team up to go on patrol. The rankings of the first three superheroes for their partner is given below. Show that there is no stable matching irrelevant of the Sewer Urchin’s preferences.

Superhero First Second Third American Maid Big Shot Die Fledermaus Sewer Urchin Big Shot Die Fledermaus American Maid Sewer Urchin Die Fledermaus American Maid Big Shot Sewer Urchin

III.8 Ignoring the arrowheads on the graph in Problem 1, can you find a Hamiltonian Circuit through the graph?

III.9 Ignoring the arrowheads on the graph in the Problem 1, can you find a Eulerian Circuit through the graph?

—3—