” COMP 3804程序 写作、 辅导Python，c++语言DATA STRUCTURES AND ALGORITHM ANALYSISCOMP 3804Assignment 4Date Due: Friday, Dec 11, 2020Time Due: 11:59pmYour assignment should be typed (or neatly printed) and submitted on CuLearn.For your NP-Completeness proofs, you may use any of the NP-Complete problems listed in Chapter 12 of JeffEricksons textbook for your reduction.1. (10 pts) Let G = (V, E) be an undirected graph where each edge e = {u, v} has a weight wt(u, v) 0. Let Gbe 2-connected (i.e. between every pair of vertices, there exists 2 vertex disjoint paths). Prove or disprove thefollowing: Let u, v be two arbitrary vertices in G. Let S(u, v) be the shortest path from u to v in G. Since G is2-connected, Does there always exist another path from u to v, denoted P(u, v), such that S(u, v) and P(u, v)are vertex disjoint? Vertex disjoint means that the only vertices shared by S(u, v) and P(u, v) are u and v.2. (10 pts) Let G = (V, E) be an undirected graph where each edge e = {u, v} has a weight wt(u, v) 0. Let Tbe a minimum spanning tree of G. Let H be a connected subgraph of G. Prove or disprove that there exists aminimum spanning tree T0 of H, such that every edge of T H is in T0.3. (10 pts) Let G = (V, E) be a directed graph where each edge e = {u, v} has weight wt(u, v) 0 or wt(u, v) 0(i.e. no edge has a weight of zero). Prove that deciding if G has a directed cycle such that the sum of theweights of the edges in the Cycle is zero, is an NP-Complete problem.4. (10 pts) Let G = (V, E) be an Undirected and unweighted graph. Let S be a subset of the vertices. The graphinduced on S, denoted G[S] is a Graph that has vertex set S and an edge between two vertices u, v S providedthat {u, v} is an edge of G. A subset K of V is called a killer set of G if the deletion of K kills all the edges ofG, that is G[V K] has no edges. Prove that finding the smallest killer set of G is an NP-Complete problem.如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
