[整理版]随便率性有向图一切顶点出度之和等于其人度之和且等于边的
习 题
1.1 试证，任意有向图所有顶点出度之和等于其人度之和且等于边的条数。
1.2 试证，任意有向完全图所有顶点出度平方之和等于其人度平方之和。
1.3 试证，任意简单无向图的最大度小于顶点数。 1.4 在图同构的观点下，试画出拥有三个顶点的所有简单有向图。并
说明
关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书
它们是否具有对称性、反对称性和传递性等特征。
1.5 试确定图1,1中两个有向图是否同构。
图1,1
1(6 试确定图1,2中两个有向图是否同构。
图1,2
1(7 试证图1,3中两个无向图是不同构的。
图1,3
1(8 试确定图1,4中两个无向图是否同构。
图1,4
1(9 试证图1,5中两个无向图是同构的。
图1,5
1(10 设G是拥有四个顶点的无向完全图。在图同构的观点下，试求:
1)G的所有子图。
2)G的所有生成子图。
1(11 试求1.4中各简单有向图的补图。 1(12 试求图1,6中各简单图的补图:
图1,6
1(13 简单无向图若同构于它的补图，则该图称自补图。
1)试给出四和五个顶点的自补图。
2)是否有三或六个顶点的自补图, 1(14 对图1,7的有向图
1)试求从顶点 到 的三条不同的基本路径。
2)顶点 到 的距离是多少,
3)此图是否有循环,
4)试求此图的可传递闭包。
图1,7
1(15 设在无向图G中，从顶点 到 有一条长度为偶数的基本路径，又有
一条长度为奇数的基本路径。试证,G中必有一条长度为奇数的基本循
环。
1(16 对图1,8的有向图
图1,8
1)试求各顶点的出度和入度。
2)试求所有基本循环。
3)删去哪条边能得到一个非循环图, 1(17 设 个城市由 条公路连结。试证，若 ，则人们总能通过这些公路,
在任意两个城市之间旅行。
1(18 设有 等七人，其中 会讲英语; 会讲华语和英语; 会讲英语，
意大利和俄语; 会讲华语和日语; 会讲德语和意大利语; 会讲
法语，日语和俄语; 会讲法语和德语。试问:必要时借助于其他人
的转译，这七个人中，是否任意两个人都能交谈,
1(19 试证，当且仅当无向连通图G的一条边 不包含在G的基本循环中时，
才是割边。
1(20 试证，当且仅当无向连通图G的一个顶点 ，存在两个不同顶点
和 ，使所有 到 的基本路径都通过 时， 才是割点。
1(21 对1.14和1.16中的有向图，试确定它们是否为弱连通的，单向连通
的或是强连通的。
1(22 试求1.16中有向图的强分图，单向分图和弱分图。
1(23 对图1,9的简单无向图
图1,9
1)试求关联矩阵。
2)试求邻接矩阵。
1(24 对图1,10的简单有向图
图1,10
1)试求关联矩阵。
2)试求邻接矩阵。
3)试求从顶点 到 长度为2和3的所有基本路径。
4)从顶点 到 长度为4的路径有几条,在其中求出所有的简单路径。
1(25 设两个简单有向图 和 的邻接矩阵分别为
1)试求矩阵 。
2)试求矩阵 。
3)试求 和 中的所有基本循环。 1(26 对图1,11的简单有向图
图1,11
1)试按定义求出可达矩阵P。
2)试求邻接矩阵A，并由此求出可达矩阵P。 1(27 给定简单图 ，其中 ，定义G的矩离矩阵为
对上题的简单有向图:
1)试按定义求出矩离矩阵D。
2)试用邻接矩阵A求出距离矩阵D。 1(28 试求1.28中简单有向图 和 的距离矩阵。 1(29 对图1,12的简单无向图
图1,12
试求邻接矩阵，可达矩阵和距离矩阵。 1(30 给定一个简单有向图G，其距离矩阵为D。
1)试证，若D中所有元素都是非 的，则G必是强连通的。
2)怎样从距离矩阵求出可达矩阵,
试确定图1,13的简单有向图
图1,13
是否为强分图。
1(31 有一个人带着一只羊和两捆草想从河的左岸渡到右岸，但由于船小，
每次只能带一只羊或一捆草，且主人不在时羊要吃草，试问这个人怎
样才能安全地将这些东西渡过河去。 1(32 1)有三对夫妇，在旅途中要渡过一条河。他们找到了一条小船，但这
条船每次最多只能载两个人。由于这三个男人之间相互猜忌，以至于
自己离开妻子时，都不愿意让妻子与别的男人在一起，从而使摆渡问
题变得复杂化。试问他们怎样才能满意地渡过河去。
2)试证，若有四对夫妇，则问题1)无解。
3)试证，若有四对夫妇，且小船每次最多能载三个人，则问题1)
有解。
在例1,4.2中，设桶 ， 和 的容积分别为 ， 和 升，试
问怎样均分,
1(33 试用迪杰斯特拉算法，求图1,14简单无向赋权图中 到 的最短
路径。
图1,14
1(34 试求例1,4.3中简单无向赋权图的所有最短路径长。
1(35 试求图1,15决策图的最优路径。
图1,15 1(36 设连结城镇 和 的围棋盘式道路图如图1,16，其中邻接交叉点间
的数字
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
距离，单位是公里。试求城镇 和 间的最短路径。
图1,16 1(37 对图1,17的评审图(权的单位是天)
17图1,
1)试求各顶点的最早完成时间和可容许的最迟完成时间。
2)完成整个计划最快需多少天,
3)试求关键路径。
4)如何解释权是0的边, 试求不在关键路径上各顶点的缓冲时间。
![[整理版]随便率性有向图一切顶点出度之和等于其人度之和且等于边的](https://swf.iask.com/32ZZmE1j6uJ.jpg?ssig=nRgPKBdyUX&Expires=1719048243&KID=sina,ishare&range=0-223848)
浙公网安备 33021202002483