计算机问题求解 - 算法在计算机科学中的地位.ppt

计算机问题求解 论题3-4 - 有向图,2019年09月24日,Part I有向通路,问题1:有向图中的顶点间的adjcency关系与无向图中有什么不同? 这对顶点的度数有什么影响?,问题2:你能否利用上面的图讨论一下有向图中“通路”与无向图有什么不同，这又如何影响了“连通”的概念？,y,z之间边的方向会影响什么？,有向图的连通性,若将有向图D各边的方向去掉，所得的无向图(称为D的底图)连通，则D称为弱连通有向图。(见下右图: 既无uv-, 又无vu-通路)u,vVD, 若(u,v)-有向通路和(v,u)-有向通路至少有一个存在，则D称为单连通有向图。 (见下中图: 有uv-, 但无vu-通路)u,vVD, 若(u,v)-有向通路和(v,u)-有向通路均存在，则D称为强连通有向图。 (见下左图),v,v,问题3：直观上你能否想像一下，强联通的有向图应该有怎样的关键特征？,可以将所有的顶点排在一个有向回路上。,问题4：你还记得怎么找强联通分支吗？,顺便说说单向联通的特征,单向连通图G的顶点集的任意子集含处处可达的点。,V,?,假如V没有任何点可以通达其它所有顶点。,总可以找到V的一个子集Vk*, 它包含一个可以通达Vk*中所有其它顶点的点，但再加一个点，这个条件就不满足了。,V*=Vk* ,问题5：你认为要表示全部16个4位二进数至少要多少个bit？,有向欧拉图,Theorem 7.4 A nontrivial connected digraph D is Eulerian if and only if od v = id v for every vertex v of D.,问题7:书上说这个证明与无向欧拉图的证明类似。你能否简述一下怎么类似？,问题8：如果要求将一个城区所有的道路均定为单行道，但仍然要保证任何两个地点之间可以合法通行，是否能做到？你能给出一个解这个问题的模型吗？,问题9：直观上你能否想象到什么样的连通图是不可能强定向的？,?,没有桥，这也是充分条件,证明的关键：S是什么？它为什么一定存在？为什么S一定会包含图中所有的顶点？,问题10：以上的证明方式有什么特点？它与算法设计有什么关系？,无向图边定向算法,输入：无环2-连通无向图G (设VG=v1,v2,vn输出：以G为底图的强连通有向图过程：(1) 令V1=v1, i=1。(2) 若Vi=VG, 对未定向边任意定向，算法结束。否则转3。(3) 取边 , 使得 (一定可取到所要的边)。 从 开始找一条初级通路或回路，满足始点和终点在Vi中，而中间点均在VG-Vi中, 加方向使之成为有向通路。(4) Vi+1=Vi 上述通路或回路中所有中间点，转2。,Part II竞赛图,问题11：什么样的图是竞赛图？它可以认为是什么样的比赛的模型？,问题12：什么样的比赛状况，取胜次数最多的人（队）获得冠军可以为认为是合理的？,Theorem 7.6 A tournament T is transitive if and only if T has no cycles.,if T is a transitive tournament of order n, then there is a unique vertex u of T having outdegree n  1, which is certainly the largest outdegree of any vertex of T.,v1,v2,vk,vi,Vi+1,?,即使不是传递的,Theorem 7.7 If u is a vertex of maximum outdegree in a tournament T, then (u, v) 2 for every vertex v of T.,证明的关键：如果有wi存在，它与某个vi是什么关系？,顺便问一句：在实际的循环赛中，这意味着什么？,竞赛图中有向哈密尔顿通路,Theorem 7.8 Every tournament contains a Hamiltonian path.,证明的关键：竞赛图中最长的有向通路（当然存在）一定包含图中所有的顶点。,有向哈密尔顿通路应用的例子,任务的最佳排序问题：假设有任务t1, t2, tn需在同一设备上串行执行，从任务ti转到任务tj所需的设备调整时间是aij，如何排任务执行次序，使设备调整需时间最少？数学模型： 建立有向图D, 顶点对应于要执行的任务，vivjED当且仅当aijaji。边vivj带权aij。 问题的解对应于最小权的有向哈密尔顿通路。,问题13：这一定是竞赛图吗？,循环赛该如何排名次（1）,A,F,E,D,C,B,按照在一条有向Hamilton通路(一定存在)上的顺序排名：C A B D E F,问题：Hamilton通路路不是唯一的，例如：也可以得到另一排名A B D E F CC 从第一名变成了最后一名,按照得胜的竞赛场次(得分)排名：A(胜4) B,C(胜3) D,E(胜2) F(胜1),循环赛该如何排名次（2）,A,F,E,D,C,B,问题：很难说B,C并列第二名是否公平， 毕竟C战胜的对手比B战胜的对手 的总得分更高(9比5)。,这是否更合理一点呢？,A,F,E,D,C,B,建立对应与每个对手得分的向量s1 = (a1, b2, c3, d4, e5, f6)然后逐次求第k级的得分向量sk, 每个选手的第k级得分是其战胜的对手在第k-1级得分的总和。(第0级值设为1),对应于左图所示的竞赛结果，得分向量：s1=(4,3,3,2,2,1) s2=(8,5,9,3,4,3) s3=(15,10,16,7,12,9) s4=(38,28,32,21,25,16)s4=(90,62,87,41,48,32) .,可以证明：当问题竞赛图是强连通的，且至少有4个选手时，这个序列一定收敛于一个固定的排列，这可以作为排名：A C B E D F,A: BDEF; B: DEF; C: ABDD: EF; E: CF; F: C,课外作业,GC Ex.7.1: 1, 2, 4, 5GC Ex.7.2: 9, 10, 13, 14, 15编程任务: (除课程指南中指定的以外) 实现无向图的边定向算法。,