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

习 题1.1 试证，任意有向图所有顶点出度之和等于其人度之和且等于边的条数。1.2 试证，任意有向完全图所有顶点出度平方之和等于其人度平方之和。1.3 试证，任意简单无向图的最大度小于顶点数。1.4 在图同构的观点下，试画出拥有三个顶点的所有简单有向图。并说明它们是否具有对称性、反对称性和传递性等特征。1.5 试确定图11中两个有向图是否同构。图1116 试确定图12中两个有向图是否同构。图1217 试证图13中两个无向图是不同构的。图1318 试确定图14中两个无向图是否同构。图1419 试证图15中两个无向图是同构的。图15110 设G是拥有四个顶点的无向完全图。在图同构的观点下，试求：1） G的所有子图。2） G的所有生成子图。111 试求1.4中各简单有向图的补图。112 试求图16中各简单图的补图：图16113 简单无向图若同构于它的补图，则该图称自补图。1） 试给出四和五个顶点的自补图。2） 是否有三或六个顶点的自补图？114 对图17的有向图1） 试求从顶点 到 的三条不同的基本路径。2） 顶点 到 的距离是多少？3） 此图是否有循环？4） 试求此图的可传递闭包。图17115 设在无向图G中，从顶点 到 有一条长度为偶数的基本路径，又有一条长度为奇数的基本路径。试证,G中必有一条长度为奇数的基本循环。116 对图18的有向图图181） 试求各顶点的出度和入度。2） 试求所有基本循环。3） 删去哪条边能得到一个非循环图？117 设 个城市由 条公路连结。试证，若 ，则人们总能通过这些公路,在任意两个城市之间旅行。118 设有 等七人，其中 会讲英语； 会讲华语和英语； 会讲英语，意大利和俄语； 会讲华语和日语； 会讲德语和意大利语； 会讲法语，日语和俄语； 会讲法语和德语。试问：必要时借助于其他人的转译，这七个人中，是否任意两个人都能交谈？119 试证，当且仅当无向连通图G的一条边 不包含在G的基本循环中时， 才是割边。120 试证，当且仅当无向连通图G的一个顶点 ，存在两个不同顶点 和 ，使所有 到 的基本路径都通过 时， 才是割点。121 对1.14和1.16中的有向图，试确定它们是否为弱连通的，单向连通的或是强连通的。122 试求1.16中有向图的强分图，单向分图和弱分图。123 对图19的简单无向图图191） 试求关联矩阵。2） 试求邻接矩阵。124 对图110的简单有向图图1101） 试求关联矩阵。2） 试求邻接矩阵。3） 试求从顶点 到 长度为2和3的所有基本路径。4） 从顶点 到 长度为4的路径有几条？在其中求出所有的简单路径。125 设两个简单有向图 和 的邻接矩阵分别为1） 试求矩阵 。2） 试求矩阵 。3） 试求 和 中的所有基本循环。126 对图111的简单有向图图1111） 试按定义求出可达矩阵P。2） 试求邻接矩阵A，并由此求出可达矩阵P。127 给定简单图 ，其中 ，定义G的矩离矩阵为对上题的简单有向图：1） 试按定义求出矩离矩阵D。2） 试用邻接矩阵A求出距离矩阵D。128 试求1.28中简单有向图 和 的距离矩阵。129 对图112的简单无向图图112试求邻接矩阵，可达矩阵和距离矩阵。130 给定一个简单有向图G，其距离矩阵为D。1） 试证，若D中所有元素都是非 的，则G必是强连通的。2） 怎样从距离矩阵求出可达矩阵？试确定图113的简单有向图图113是否为强分图。131 有一个人带着一只羊和两捆草想从河的左岸渡到右岸，但由于船小，每次只能带一只羊或一捆草，且主人不在时羊要吃草，试问这个人怎样才能安全地将这些东西渡过河去。132 1)有三对夫妇，在旅途中要渡过一条河。他们找到了一条小船，但这条船每次最多只能载两个人。由于这三个男人之间相互猜忌，以至于自己离开妻子时，都不愿意让妻子与别的男人在一起，从而使摆渡问题变得复杂化。试问他们怎样才能满意地渡过河去。2)试证，若有四对夫妇，则问题1)无解。3） 试证，若有四对夫妇，且小船每次最多能载三个人，则问题1)有解。在例14.2中，设桶 ， 和 的容积分别为 ， 和 升，试问怎样均分？133 试用迪杰斯特拉算法，求图114简单无向赋权图中 到 的最短路径。图114134 试求例14.3中简单无向赋权图的所有最短路径长。135 试求图115决策图的最优路径。图115136 设连结城镇 和 的围棋盘式道路图如图116，其中邻接交叉点间的数字表距离，单位是公里。试求城镇 和 间的最短路径。图116137 对图117的