计算机问题求解 - 算法在计算机科学中的地位.ppt
《计算机问题求解 - 算法在计算机科学中的地位.ppt》由会员分享,可在线阅读,更多相关《计算机问题求解 - 算法在计算机科学中的地位.ppt(27页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、计算机问题求解 论题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-通路
2、)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.
3、4A nontrivial connected digraph D is Eulerian if and only ifodv= idv for every vertexvof D.,问题7:书上说这个证明与无向欧拉图的证明类似。你能否简述一下怎么类似?,问题8:如果要求将一个城区所有的道路均定为单行道,但仍然要保证任何两个地点之间可以合法通行,是否能做到?你能给出一个解这个问题的模型吗?,问题9:直观上你能否想象到什么样的连通图是不可能强定向的?,?,没有桥,这也是充分条件,证明的关键:S是什么?它为什么一定存在?为什么S一定会包含图中所有的顶点?,问题10:以上的证明方式有什么特点?它与算
4、法设计有什么关系?,无向图边定向算法,输入:无环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:什么样的比赛状况,取胜次数最多的人(队)获得冠军可以为认为是合理
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 问题 求解 算法 计算机科学 中的 地位
限制150内