Homework answers / question archive / City College of San Francisco Discrete Mathematics Writing Assignment: Three ASSIGNMENT PURPOSE The purpose of this assignment is to evaluate your ability to [write proofs using symbolic logic, Boolean algebra, and mathematical induction], [apply matrices and graph theory to networking, matching problems, and optimization problems], and [analyse essential features of recursive and iterative algorithms]

City College of San Francisco Discrete Mathematics Writing Assignment: Three ASSIGNMENT PURPOSE The purpose of this assignment is to evaluate your ability to [write proofs using symbolic logic, Boolean algebra, and mathematical induction], [apply matrices and graph theory to networking, matching problems, and optimization problems], and [analyse essential features of recursive and iterative algorithms]

Sociology

Share With

City College of San Francisco Discrete Mathematics Writing Assignment: Three ASSIGNMENT PURPOSE The purpose of this assignment is to evaluate your ability to [write proofs using symbolic logic, Boolean algebra, and mathematical induction], [apply matrices and graph theory to networking, matching problems, and optimization problems], and [analyse essential features of recursive and iterative algorithms]. These items are Student Learning Outcomes for the course. View the related Assignment page in Canvas for more details on this assignment. Writing Prompt A procedure for connecting up a (possibly disconnected) simple graph and creating a spanning tree can be modelled as a state machine whose states are finite simple graphs. A state is final when no further transitions are possible. The transitions are determined by the following rules: Rule 1: If there is an edge {u, v} on a cycle, then delete {u, v}. Rule 2: If vertices u and v are not connected, then add the edge {u, v}. (a) Draw all the possible final states reachable starting with graph with vertices {1, 2, 3, 4} and edges {{1, 2}, {3, 4}}. (For a nice presentation, use some application to draw the graphs. One free flow-chart building application that will work to make such graphics is draw.io. Embed these images into this document. If you have a goal of becoming a serious LaTeX nerd, try out the tikz package that is already loaded for this document.) (b) Prove that if the machine reaches a final state, then the final state will be a tree on the vertices of the graph on which it started. ′ ′ (c) For any graph G , let e be the number of edges in G , c be the number of connected components it has, and s be the number of cycles. Prove that one of the following quantities strictly decreases at each transition. • c • s • e-s • c+e • 3c + 2e • c+s (d) Prove that the final state for this state machine model is reachable for any starting state. Problem Response (a) (b) Rule 1 will make sure that there will not have any cycle in the graph, and Rule 2 will make sure that all the vertices will be connected. Thus, if the machine reaches the final state, which mean there is no more cycles to break, and no more vertices that are not connected to be connected, the graph become a tree (c) Because of Rule 1 and Rule 2, we know that after every round the machine execute, either e + 1 or s − 1. We also know that every time e + 1, which means there is a new vertex connected, so c + 1 too. We can see that only s is strictly decreases since it will decrease every time executing Rule 2, and the Rule 1 won’t increase s since it only add edge on the vertices that are not connected. If two vertices are not connected, there is no way to make a cycle by adding only one edge. (d) Because of Rule 1, we can insure that there won’t have any cycle in the graph. Because of Rule 2, we can insure that there won’t have any vertex that is not connected to the graph. The state machine can’t reach the final state if and only if there is an edge {u, v} on a cycle, if we remove {u, v}, it will cost a vertex be disconnected, which is impossible since the definition of a cycle is there are two different path from a vertex to another. If we remove an edge to cut off a path, there should be another path to make the vertex still connected with the graph. 2/2