关键词 > Math137A
Math 137A Final Exam Spring 2023
发布时间：2024-06-10
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Math 137A
Final Exam Spring 2023
1. (6 points) Draw all simple graphs (up to isomorphism) which have exactly 5 vertices and 5 edges. Why is your list complete?
2. (2 points each) Each statement below is false. Verify this fact by, for each statement, drawing a simple graph that serves as a counterexample.
(a) A graph with n vertices and n − 1 edges is a tree.
(b) Every Eulerian graph is Hamiltonian.
(c) Every graph G satisfies χ(G) ≤ ∆(G).
(d) If G hasn vertices and contains a Hamilton cycle, then every vertex v ∈ V (G) has deg(v) ≥ 2/n.
(e) Any maximum matching in a connected graph G with at least 4 vertices must contain at least two edges.
(f) If G is 2-connected but not 3-connected, then G has a vertex of degree 2.
3. (4 points) Let G be a connected planar graph with e edges, U vertices and where all faces have length at least 5. Prove that
4. (4 points) A wheel graph Wn is constructed by taking an n-cycle, adding a new vertex and joining this vertex to every vertex. For example, W3 = K4 and W4 is below. Calculate the chromatic number of Wn for all n. Hint: the answer depends on whether n is even or odd.
5. (5 points) Please answer one of the following two questions. Points will be awarded based on correctness and amount of detail provided.
• What is the relationship between edge-colorings of Kn,n and Latin squares of order n? In other words, how can you go from one to the other?
• How exactly would you construct a de Bruijn sequence of order 1000 using an Eulerian circuit? Included in your answer should be any definitions of graphs you are using, why an Eulerian circuit exists, and how it can be used to obtain a de Bruijn cycle.
6. (2+3 points) As you should know well by now, the Chebyshev Metric on Z2 measures the distance between points (i, j) and (k , ℓ) to be
max(|i - k|, |j - ℓ|).
For example, the distance between (1, 1) and (2, 3) is 2. Given the points below, suppose all edges exist but are not drawn (in other words we have the complete graph) and that the cost of traveling between two points is given by the Chebyshev metric.
In this question you will use Christofides’ Algorithm to find a Hamilton cycle whose cost is at most 3/2 the cost of the cheapest Hamilton cycle.
(a) Find a minimum cost spanning tree of the points below. Do this and draw the result below:
(b) Copy the tree you found in Part (a) above, and complete the next step of the algorithm here.
(c) Copy your answer from part (b) here, and then complete the final step of the algorithm.
7. Let G be a cubic graph that has Hamilton cycle.
(a) (2 points) Prove that G has an even number of vertices.
(b) (4 points) Prove that G is 3-edge-colorable.
8. (6 points)
The following graph illustrates a flow from source r to vertex s. As usual, the numerators are the flow values, and the denominators are the capacities of the edges.
(a) Explain why the current flow is not a maximum flow.
(b) Find a maximum (r, s)-flow. For convenience here is the same network again with only capac- ities shown.
(c) Prove your flow is maximum by identifying a corresponding minimum (r, s)-cut (you can just circle the vertices in the above picture).
