联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp2

您当前位置:首页 >> Java编程Java编程

日期:2020-12-08 11:35

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

0

.

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.

1


版权所有:留学生编程辅导网 2018 All Rights Reserved 联系方式:QQ:99515681 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。