Discrete math 2

Discrete math 2 test 1 I. Graph theory 1. Create the adjacency matrix of the following graph: 2 pts 2. neither. State whether the graph has an Euler circuit, an Euler path, or a. 1 pt. b. 1 pt. c. 1 pt. 3. Draw a tournament with five players, in which player A beats everyone but E, B beats everyone but A, C beats D and E beats everyone but B. 2 pts. 4. Create a Hamiltonian circuit for a 4-dimensional hypercube 2 pts. 5. Use Dijkstra’s algorithm to build a shortest path tree. Use vertex P as starting vertex. 3 pts. 6. Stable matching. There are 5 boys (1,2,3,4,5) and 5 girls (A,B,C.D,E). Match the boys and girls in a good way (stable matchings) starting with boys. Preference list for boys 1 2 3 4 5 A,D,B,C,E A,D,B,C,E B,E,D,A,C B,A,D,E,C D,C,B,A,E Preference list for girls A B C D E 1,5,3,2,4 5,4,3,1,2 3,1,4,2,5 3,1,2,5,4 1,2,4,5,3 2 2pts. 7. Bipartite matching. Job Assignment Problem. There are 6 persons (A,B,C,D,E,F) and 6 jobs (!,2,3,4,5,6). Preferences are presented in the following matrix. 1 v v A B C D E F 2 v v v 3 v 4 5 6 v v v v v v v v v v v v Find an assignment so that all jobs are taken care of, while everyone is responsible for at most one job? 2 pts. 8. Graph coloring. Determine the chromatic number χ(G) of the following graphs: a. 1 pt. b. 1 pt. c. 1 pt. 3 9. Scheduling using conflict graphs. Create a schedule for the following flight plan using minimal number of gates. Flight Time 132 115 57 217 301 79 2 pts. 10. Draw a planar graph with 6 vertexes and 10 edges. 2 pts. 11. Representing relations. Let R = {(1,3), (2, 1), (2,2), (3, 1), (3, 2), (3,3}. Represent R: a) Using zero-one matrix; 1 pt. b) Using digraph. 1 pt. 12. Combining relations. Let: D = {(1, 4), (2, 3), (3, 2), (4, 1)} S = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} Combine: a. DUS 1 pt. b. D 1 pt. S 13. Perform the following modular operations: a. 47+32 mod 7 1 pt. b. 35*28 mod 11 1 pt. 14. Find φ(n) for: 4 a. n = 35 1 pt. b. n = 77 1 pt. c. n = 143 1 pt. 15. Find the multiplicative inverse mod n: 8-1 mod 21 2 pt. 16. Modular exponentiation: 6726 mod 21 2 pt. Rules for estimation 1. The max score is 36 points 2. The distribution of grades is: a) 6 – over 30 points b) 5 – between 25 and 30 points c) 4 – between 19 and 24 points d) 3 – between 13 and 18 points e) 2 – under 13 points 5