任意有向图所有顶点出度之和等于其人度之和且等于边的...

《任意有向图所有顶点出度之和等于其人度之和且等于边的...》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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的边？试求不在关键路径上各顶点的缓冲时间。