欢迎来到天天文库
浏览记录
ID:8360232
大小:38.50 KB
页数:6页
时间:2018-03-22
《任意有向图所有顶点出度之和等于其人度之和且等于边的...》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、习题1.1试证,任意有向图所有顶点出度之和等于其人度之和且等于边的条数。1.2试证,任意有向完全图所有顶点出度平方之和等于其人度平方之和。1.3试证,任意简单无向图的最大度小于顶点数。1.4在图同构的观点下,试画出拥有三个顶点的所有简单有向图。并说明它们是否具有对称性、反对称性和传递性等特征。1.5试确定图1-1中两个有向图是否同构。图1-11.6试确定图1-2中两个有向图是否同构。图1-21.7试证图1-3中两个无向图是不同构的。图1-31.8试确定图1-4中两个无向图是否同构。图1-41.9试证图1-5中两
2、个无向图是同构的。图1-51.10设G是拥有四个顶点的无向完全图。在图同构的观点下,试求:1)G的所有子图。2)G的所有生成子图。1.6试求1.4中各简单有向图的补图。1.7试求图1-6中各简单图的补图:图1-61.8简单无向图若同构于它的补图,则该图称自补图。1)试给出四和五个顶点的自补图。2)是否有三或六个顶点的自补图?1.9对图1-7的有向图1)试求从顶点到的三条不同的基本路径。2)顶点到的距离是多少?3)此图是否有循环?4)试求此图的可传递闭包。图1-71.10设在无向图G中,从顶点到有一条长度为偶数的
3、基本路径,又有一条长度为奇数的基本路径。试证,G中必有一条长度为奇数的基本循环。1.11对图1-8的有向图图1-81)试求各顶点的出度和入度。2)试求所有基本循环。3)删去哪条边能得到一个非循环图?1.12设个城市由条公路连结。试证,若,则人们总能通过这些公路,在任意两个城市之间旅行。1.13设有等七人,其中会讲英语;会讲华语和英语;会讲英语,意大利和俄语;会讲华语和日语;会讲德语和意大利语;会讲法语,日语和俄语;会讲法语和德语。试问:必要时借助于其他人的转译,这七个人中,是否任意两个人都能交谈?1.6试证,当
4、且仅当无向连通图G的一条边不包含在G的基本循环中时,才是割边。1.7试证,当且仅当无向连通图G的一个顶点,存在两个不同顶点和,使所有到的基本路径都通过时,才是割点。1.8对1.14和1.16中的有向图,试确定它们是否为弱连通的,单向连通的或是强连通的。1.9试求1.16中有向图的强分图,单向分图和弱分图。1.10对图1-9的简单无向图图1-91)试求关联矩阵。2)试求邻接矩阵。1.11对图1-10的简单有向图图1-101)试求关联矩阵。2)试求邻接矩阵。3)试求从顶点到长度为2和3的所有基本路径。4)从顶点到长
5、度为4的路径有几条?在其中求出所有的简单路径。1.12设两个简单有向图和的邻接矩阵分别为1)试求矩阵。2)试求矩阵。1)试求和中的所有基本循环。1.6对图1-11的简单有向图图1-111)试按定义求出可达矩阵P。2)试求邻接矩阵A,并由此求出可达矩阵P。1.7给定简单图,其中,定义G的矩离矩阵为对上题的简单有向图:1)试按定义求出矩离矩阵D。2)试用邻接矩阵A求出距离矩阵D。1.8试求1.28中简单有向图和的距离矩阵。1.9对图1-12的简单无向图图1-12试求邻接矩阵,可达矩阵和距离矩阵。1.10给定一个简单
6、有向图G,其距离矩阵为D。1)试证,若D中所有元素都是非的,则G必是强连通的。2)怎样从距离矩阵求出可达矩阵?试确定图1-13的简单有向图图1-13是否为强分图。1.11有一个人带着一只羊和两捆草想从河的左岸渡到右岸,但由于船小,每次只能带一只羊或一捆草,且主人不在时羊要吃草,试问这个人怎样才能安全地将这些东西渡过河去。1.61)有三对夫妇,在旅途中要渡过一条河。他们找到了一条小船,但这条船每次最多只能载两个人。由于这三个男人之间相互猜忌,以至于自己离开妻子时,都不愿意让妻子与别的男人在一起,从而使摆渡问题变得
7、复杂化。试问他们怎样才能满意地渡过河去。2)试证,若有四对夫妇,则问题1)无解。1)试证,若有四对夫妇,且小船每次最多能载三个人,则问题1)有解。在例1-4.2中,设桶,和的容积分别为,和升,试问怎样均分?1.7试用迪杰斯特拉算法,求图1-14简单无向赋权图中到的最短路径。图1-141.8试求例1-4.3中简单无向赋权图的所有最短路径长。1.9试求图1-15决策图的最优路径。图1-151.10设连结城镇和的围棋盘式道路图如图1-16,其中邻接交叉点间的数字表距离,单位是公里。试求城镇和间的最短路径。图1-161
8、.11对图1-17的评审图(权的单位是天)图1-171)试求各顶点的最早完成时间和可容许的最迟完成时间。1)完成整个计划最快需多少天?2)试求关键路径。3)如何解释权是0的边?试求不在关键路径上各顶点的缓冲时间。
此文档下载收益归作者所有