CS5002 Discrete Structures Prof. Rachlin Spring 2022 April 20, 2022
Homework #11
Assigned: Wednesday April 20, 2022
Due: Tuesday April 26, 2022 @ 11:59pm ET/Boston −5%: Wednesday April 27, 2022 @ 11:59pm ET/Boston −10%: Thursday April 28, 2022 @ 11:59pm ET/Boston
Copyright By PowCoder代写 加微信 powcoder
Instructions:
• Homework is due on Tuesday at 11:59pm ET/Boston. Homeworks received up to 24 hours late (11:59pm ET on Wednesday) will be penalized 5 percent. Homeworks received up to 48 hours late (11:59pm ET on Thursday) will be penalized 10 percent. NO assignment will be accepted after 48 hours.
• We expect that you will study with friends and fellow students and you are welcome to verbally discuss the problems openly. However, your solution writeup should be the product of your own mind and expressed in your own words. The TAs and I will be available to answer specific questions or address speific points of confusion but we will not verify your answers prior to submission.
• Assignments should be typed using Word or LateX, or hand-written neatly. When submitting to gradescope be sure to indicate the page containing your answer to each problem, so that the TAs don’t have to search for your solution.
• To get full credit, explain your solution and show each step of the solution process! Simply writing down a correct answer will receive little or no credit. We don’t need your scratch work or draft solutions, only your final solution explaining your step-by-step reasoning. Recommendation: try to imagine you need to explain your solution to someone not in this class.
• If you think the TA made a clerical error in grading your assignment, you may submit a regrade request on Gradescope within 1 week of the publication of the grades. After 1 week of publication, ALL GRADES ARE FINAL.
Problem 1 [20 pts (10, 10)]: Graph Theory
1. Nine people are at a party. Explain why it is impossible for each of the nine party goers to
have shaken hands with exactly five other party goers.
Solution: Sum of degrees would be 9 · 5 = 45 = 2|E| (by the degree-sum formula), implying |E| = 22.5 which is impossible. Declaring the impossibility of such a graph by appealing to the Handshaking Lemma (i.e., that there must be an even number of odd-degree vertices) is also acceptable.
2. If a graph with 1 million vertices consists of 3 connected components, what is the minimum number of edges it might have? Hint: How do we ”minimally connect” a graph?
Solution: The minimum number of edges is achieved when the 3 components are all trees. Each will have one fewer edge than its number of vertices |Vi|, so the total number of edges will be i(|Vi| − 1) = |V | − 3 = 1, 000, 000 − 3 = 999, 997.
Problem 2 [20 pts (10,10): Graph Representations
ABCDEFG A0001100 B0000011 C0001010 D1010010 E1000010 F0111101 G0100010
For the above adjacency matrix representation of an unweighted undirected graph, create an equivalent adjacency list representation and draw the resulting graph.
Problem 3 [20 pts (10,10): Graph Traversal
For the 9-vertex graph below, highlight the edges that would be traversed using Depth-First
Search (left) and Breadth-First Search (right) starting at the middle vertex labeled X. Add a number, 1 to 9 next to each vertex to show the order in which each vertex is visited, starting with a 1 next to X. In cases of a tie, the traversal should proceed alphabetically.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com