例：待访问城市的集合C??C1,Cn,?,Cm?，每对城市Ci,Cj?C之间的距
离dCi,Cj?Z?，以及一个界B?Z?。
问：在C存在一个总长不超过B的、通过所有城市的旅行路线吗？ (15) 旅行商最优问题
(16)有向图的有向Hamilton圈问题
例：给定有向图G(V,E)
问：G是否有一个有向Hamilton圈，即长度为n?|V|，而且恰好经过每个顶点一次，然后回到起始顶点
(17) 无向图的Hamilton圈问题
例：给定无向图G(V,E)
问：G是否有一个Hamilton圈，即长度为n?|V|，而且恰好经过每个顶点一次，然后回到起始顶点的圈。
将有向图的（有向）Hamilton圈问题实例变换成无向图的Hamilton提示：
问题实例：把已知有向图D的每个顶点u换成欲构造的无向图G的三个顶点：ui,um,uo，并将顶点um与顶点ui,uo分别相连。如果在有向图D中有从顶点u到顶点v的有向边（弧），则在无向图G中将顶点uo与顶点vi连接一条边。
(18) 区间排序问题（Sequencing within intervals）
例：给定任务的有限集合W，对于每个任务w?W，相应有一个开始时间
r(w)和终止时间d(w)以及工作时间l(w)，其中r(w)?Z??{0} ，
??d(w),l(w)?Z?
问：是否存在任务集的一个可行时间排序表，即是否存在函数
?:W?Z??{0}，满足下面两个条件：
（1） 对每个w?W，有?(w)?r(w),且?(w)?l(w)?d(w)； （2） 若w'?W,w'?w，则?(w')?l(w')??(w)或?(w')??(w)?l(w)
(19) 三元精确覆盖问题X3C
例：给定有限集合X,|X|=3q,以及X的三元子集族C。
问：C含有X的一个精确覆盖吗？即是否存在一个子族C'?C，使得X的每个元素恰好只出现C'的一个三元子集中。
(20) Steiner树判定问题
例：给定图G?(V,E)，对其每条边e?E都有相应的权w(e)?Z?，另外有G的顶点子集R?V，某个界B?Z?。
问：是否存在G的一颗子树T?(V1,E1)，使R?V1?V,E1?E，而且
e?E1?w(e)?B？
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库计算机算法设计与分析练习题(3)在线全文阅读。
相关推荐：