COMP 3804程序代做、代写Python，c++语言编程、Java代写编程代写-代写Java编程

DATA STRUCTURES AND ALGORITHM ANALYSIS

COMP 3804

Assignment 4

Date Due: Friday, Dec 11, 2020

Time Due: 11:59pm

Your 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 Jeff

Erickson’s 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 G

be 2-connected (i.e. between every pair of vertices, there exists 2 vertex disjoint paths). Prove or disprove the

following: 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 is

2-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 T

be a minimum spanning tree of G. Let H be a connected subgraph of G. Prove or disprove that there exists a

minimum spanning tree T

0 of H, such that every edge of T ∩ H is in T

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 the

weights 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 graph

induced on S, denoted G[S] is a graph that has vertex set S and an edge between two vertices u, v ∈ S provided

that {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 of

G, that is G[V − K] has no edges. Prove that finding the smallest killer set of G is an NP-Complete problem.