### Applications of Discrete Mathematics and Statistics in IT: ITCO341 – 1402A – 01

Assignment Details

Consider the following weighted graph:

In the table below, choose the bracket that contains the first letter of your last name. Then, choose 1 value for a and 1 value for b from the numbers listed for your bracket. (Put your chosen values for a and b in the heading for your first post for the week, so your classmates will know which values you have chosen for each and so they will not choose the same values as yours. Be sure to choose a combination of a and b that is different from your classmates who have already posted or have chosen their values.) The values chosen will be the weights in the paths labeled a and b in the weighted graph above.

Last Name Begins With

a

b

A–K

10, 14, 16, 5

4, 6, 9, 11

L–Q

5, 11, 13, 8

2, 7, 12, 15

R–Z

3, 8, 10, 19

13, 15, 17, 18

In the weighted graph above, find the shortest path from node A to node E using Dijkstra’s shortest path algorithm and using your chosen values for a and b.

Explain your key steps in determining the shortest path, and give the node sequence that corresponds to that shortest path.

Explain 2 examples where knowledge of a shortest path algorithm could be useful in an information technology career.

Thinking of the graph above as undirected, does this graph have a Euler path? If so, give an example of such a path starting with a node you choose; if not, explain why not.

Does this graph have a Euler circuit? If so, give an example; if not, explain why not.

Does this graph have a Hamiltonian path? If so, give an example of such a path starting with a node you choose; if not, explain why not.

If there is a Hamiltonian path, is there a Hamiltonian circuit? If so, give an example of such a circuit starting with a node you choose; if not, explain why not.