MAT1005 Exam 2 - Find the degree
Scheduling, Graphing Theory 1, And Graphing Theory 2
MAT1005 Exam 2
1. Find the degree of each vertex below.
2. Find an Euler path for the following.
3. Eulerize the following then find an Euler circuit.
4. Does a Hamiltonian path or circuit exist for the following?
5. Use the Brute Force algorithm for the following.
6. Use the Nearest Neighbor Algorithm for the following (start at A).
7. Use the Sorted Edges Algorithm (Cheapest Link Algorithm) for the following .
8. Use Kruskal’s Algorithm for the following.
9. Use the Decreasing-Time Algorithm to create a priority list for the given digraph, and schedule with 2 processors.
10. Use the Critical Path Algorithm to create a priority list and schedule on two processors for the following.
11. Draw a graph with four vertices that is connected and draw a graph with four vertices that is not connected.
12. Draw a graph of four vertices with one vertex with degree 1, another vertex with degree 2, another vertex with degree 3, and the last vertex with degree 2.
13. To deliver mail in a particular neighborhood, the postal carrier needs to walk along each of the streets with houses (the dots). Create a graph with edges showing where the carrier must walk to deliver the mail.
14. Find an Euler circuit for the following (start at A and end at A).
15. Find a Hamiltonian circuit for the following (start at B and end at B).