关键词 > Math137A
Math137A Midterm - 2022
发布时间：2024-05-11
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Math137A
Midterm - April 29th, 2022
1. (a) Draw a single simple graph that simultaneously has the following properties:
i. Is planar.
ii. Has two edge-disjoint Hamiltonian cycles.
iii. Is not Eulerian.
(b) For your answer in Part (a), label the vertices 1, 2, . . . , n (where n is the number of vertices). Next identify a spanning tree that is not a path and write down its Pr¨(u)fer code.
2. For each of the following, state whether it is true or false. Explain your choices.
(a) If G is a graph with n vertices and n − 1 edges, then G is connected.
(b) If G is Hamiltonian, then G has a Eulerian circuit.
(c) If G has an Eulerian circuit, then G is Hamiltonian.
(d) There are Hamiltonian graphs with n vertices where each vertex has degree less than 2/n.
3. Let F be a forest with k connected components and n vertices in total. How many edges does F have?
4. Determine the number of spanning trees of the graph below.
5. For the graph below, find a minimum spanning tree. Then use this tree together with the 2- Approximation Algorithm discussed in class to find a Hamiltonian cycle with cost at most twice the cost of the cheapest Hamiltonian cycle. Numbers beside edges are their costs and you may assume they satisfy the triangle inequality.
6. This question is worth just 1 point.
If I were assigning final grades today, what letter grade do you feel you would deserve? If this grade is high, please justify why it should be so. If you feel you would get a poor grade, how might you improve this in the second half of the course?
Note: Whatever you answer here will have no efect on your actual final grade.
