代做MAT 145 Combinatorics Practice Final Exam代做Prolog

MAT 145 Combinatorics

Practice Final Exam

Short-Answer Questions

1. SQ 1 Is the following matrix an adjacency matrix for a simple graph? Explain your answer.

2. SQ 2 State the definition of a closed Eulerian trail.

3. SQ 3 State the definition of a Hamiltonian cycle.

4. SQ 4 What is the chromatic number of K5? Briefly explain your answer.

5. SQ 5 How many passwords of length 7 created from an alphabet of size 36 have at least one repeated entry? For example, abca1a3 has at least one repeated entry but abcd123 does not.

6. SQ 6 How many ways are there to form. two groups of 7 people and one group of 5 people from a collection of 19 people?

7. SQ 7 Given a weighted, connected graph G = (V,E), describe Kruskal’s algorithm and the output of Kruskal’s algorithm.

8. SQ 8 Suppose that G1 = (V1, E1) is isomorphic to G2 = (V2, E2). State four properties of the graphs that must be the same. (For example, |V1| = |V2|.)

Long-Answer Questions – only 4 of the 6 problems will be graded. You will indicate which problems you would like graded on the cover sheet.

1. LQ 1 Sketch K6.

(a) Construct a closed Eulerian trail, if possible, and explain why it is an Eulerian trail. If it is not possible, explain why.

(b) Construct a Hamiltonian cycle, if possible, and explain why it is a Hamiltonian cycle. If it is not possible, explain why.

2. LQ 2 Define R(n, n, n) = m to be the smallest number so that every 3-coloring of the edges of Km contains a monochromatic Kn in either Blue, Red, or Green.

(a) Find R(2, 2, 2), explain your answer.

(b) Find R(2, 2, n), explain your answer.

(c) Find R(2, 3, 3), explain your answer

3. LQ 3 Given five points inside an equilateral triangle of side length 2, show that there are two points whose distance from each other is at most 1.

4. LQ 4 Consider the complete bipartite graph Ka,b with a, b ≥ 1. Find all of the nonisomorphic induced subgraphs of order 4. Your answer should depend on the values of a and b.

5. LQ 5 Give a combinatorial proof of the following. For m, n 2 N and p 2 Z with 0 ≤ p ≤ m + n,

6. LQ 6 Let T1 = (V1, E1) and T2 = (V2, E2) be trees of order n1 ≥ 1 and n2 ≥ 1. Let a ∈ V1 and b ∈ V2. Let T = (V,E), where

V = V1 [ V2            and              E = E1 [ E2 [ {(a, b)},

be a graph of order n1 + n2. Give two different explanations for why T is a tree.