离散数学第7章 图论 习题[教学内容]

1、第7章 习题课 1优学课堂 练习练习7-1（6）简单图的最大度小于结点数。）简单图的最大度小于结点数。 证明：设简单图证明：设简单图G中有中有n个结点。个结点。 任取一个结点任取一个结点v， 由已知由已知G是简单图没有环和重边，是简单图没有环和重边， v至多和至多和n-1个结点相邻，个结点相邻， 也即也即deg(v) n-1, 而而 (G)max deg(v) n-1, 因此因此 最大度小于结点数。最大度小于结点数。 2优学课堂 练习练习7-2（2）：若无向图）：若无向图G中恰有两个奇数度的结点，中恰有两个奇数度的结点， 则这两个结点之间必有一条路。则这两个结点之间必有一条路。 证明：设无向图

2、证明：设无向图G中两个奇数度的结点为中两个奇数度的结点为u和和v。 从从u开始构造一条迹，即从开始构造一条迹，即从u出发经关联于结点出发经关联于结点u的边的边e1到达结点到达结点 u1，若，若deg(u1)为偶数为偶数,则必可由则必可由u1再经关联于结点再经关联于结点u1的边的边e2到达结到达结 点点u2,如此继续下去如此继续下去,每边只取一次每边只取一次,直到另一个奇数度结点停止直到另一个奇数度结点停止, 由于图由于图G中只有两个奇数度结点中只有两个奇数度结点,故该结点或是故该结点或是u或是或是v。如果是。如果是v, 那么从那么从u到到v的一条路就构造好了。如果仍是结点的一条路就构造好了。如

3、果仍是结点u,此路是闭迹。此路是闭迹。 闭迹上每个结点都是关联偶数条边闭迹上每个结点都是关联偶数条边,而而deg(u)为奇数为奇数,所以至少还所以至少还 有一条关联于结点有一条关联于结点u的边不在此闭迹上。继续从的边不在此闭迹上。继续从u出发出发,沿着该边沿着该边 到达另一个结点到达另一个结点u1,依次下去直到另一个奇数度结点停下。这样依次下去直到另一个奇数度结点停下。这样 经过有限次后必可到达结点经过有限次后必可到达结点v,这就是一条从这就是一条从u到到v的路。的路。 3优学课堂 练习7-2（3）： 若图G是不连通的，则G的补图G是连通的。 证明：若G=是不连通的，可设图G的连通分支为 GV

4、1,GV2,GVm(m2)。 由于任意两个连通分支GVi,GVj不连通，因此Vi与Vj之 间的连线在补图中，在G中任取两个结点u和v，则u和v 的位置有两种情况： 1)若u和v均在同一个连通分支GVi中,根据上面的分析， 可在另一个连通分支GVj（ij)中取一个结点w，使得 u与w，v 与w在G中连通，故有uwv，即u与v在G 中连通 2)若u与v分别属于两个不同的连通分支GVi与GVj，由 上面的分析可知，u与v在G中连通。 故当图G不连通时，则补图G是连通的 4优学课堂 7-2（4）:当且仅当当且仅当G的一条边的一条边e不包含在不包含在G的回路中时，的回路中时， e才是才是G的割边。的割边

5、。 证明：必要性。（证明：必要性。（ e是是G的割边）的割边） 设设e是连通图是连通图G的割边，的割边，e关联的两个结点是关联的两个结点是u和和v。如果。如果e包含在包含在 G的一个回路中，那么除边的一个回路中，那么除边e=(u,v)外还有另一条分别以外还有另一条分别以u和和v为为 端点的路，所以删去边端点的路，所以删去边e后，后，G仍为连通图，这与仍为连通图，这与e是割边相矛盾。是割边相矛盾。 充分性。充分性。 如果边如果边e不包含在不包含在G的任一条回路中，那么连接结点的任一条回路中，那么连接结点u和和v的边只的边只 有有e，而不会有其它连接，而不会有其它连接u和和v的任何路。因为如果连接

6、的任何路。因为如果连接u和和v还有还有 不同于边不同于边e的路，此路与边的路，此路与边e就组成一条包含边就组成一条包含边e的回路，从而导的回路，从而导 致矛盾。所以删去边致矛盾。所以删去边e后，后，u和和v就不连通，故边就不连通，故边e是割边。是割边。 5优学课堂 300页（2） 如果u可达v，它们之间可能不止一条 路，在所有这些路中，最短路的长度 称为u和v之间的距离（或短程线）， 记作d，如果从u到v是不可达的， 则通常写成 d = 距离矩阵为 0 1 2 1 0 1 1 1 0 1 1 2 0 dij=1表示存在边。 6优学课堂 300页（3） 用Warshall算法求可 达性矩阵。 邻

7、接矩阵为 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 A= i=1时，因为A的第一行 全为0，所以A不变。 i=2时，因为A的第2列 全为0，所以A不变。 i=3时，因为A2，3=A4，3=1，将第3行 加到第2行和第4行。 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 A= i=4时，因为A4,2=1，将第四行 加到第2行，A不变。 i=5时，因为A的第5列全为0，所 以A不变。 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 P=

8、 故故A A的可达的可达 性矩阵为：性矩阵为： 7优学课堂 距离矩阵为 0 1 0 1 1 1 0 2 1 0 0 8优学课堂 300页（4）：写出如图7-3.11所示的图G的完 全关联矩阵，并验证其秩如定理7-3.2所述。 e1e2e3e4e5e6e7e8e9 A100001010 B011000100 C000110010 D110000001 E000011100 F001100001 完全关联矩阵为: 此图为连通图，由定理 7-3.2，其秩为5。 9优学课堂 311页（2）构造一个欧拉图，其结点数v和边数e满足下述条件 a)v，e的奇偶性一样。 b) v，e的奇偶性相反。 如果不可能，

9、说明原因。 v=3,e=3 v=5,e=5 v=4,e=4v=4,e=6 v=7,e=8 v=6,e=7 无向图G具有一条欧拉回 路，当且仅当G是连通的，并且 所有结点度数全为偶数。下面的 图中所有结点度数全为偶数，所 以都是欧拉图。 10优学课堂 311页（6） a)画一个有一条欧拉回路和一条汉密尔顿回路的图。 在无孤立结点图G中，经过图 中每条边一次且仅有一次的一 条回路，称为欧拉回路。 给定图G，经过图中每 个结点恰好一次的回路称作 汉密尔顿回路。 11优学课堂 b)画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。 12优学课堂 c)画一个没有一条欧拉回路，但有一条汉密尔顿回路的图。

10、13优学课堂 设设G是一个具有是一个具有k个奇数度结点（个奇数度结点（k0）的连通图，）的连通图， 证明在证明在G中的边能剖分为中的边能剖分为k/2条路（边不相重）。条路（边不相重）。 证明：因为一个图中度数为奇数的结点个数必为偶数， 故k必为偶数。 将G中k个奇数度结点分为数目相等的两组u1,u2,uk/2 和v1,v2,vk/2 。对图G添加边(u1,v1), (u2,v2), (uk/2,vk/2)共k/2条边，得到图G。由于图G中每个结 点的度数均为偶数，故G中存在一条欧拉回路。 在图G中删去边(u1,v1),得到一条欧拉路, 此路的两个端 点是u1和v1。结点u2和v2必在路的中间,

11、 再删去边 (u2,v2)，得到两条边互不相重的迹，这两个迹的端点 分别为u2和v2。结点u3和v3必在某一条迹的中间。 再删去边(u3,v3) ，则将一条迹（包含u3和v3的迹）又分 为两条边互不相重的迹，共得到3条互不相重的迹。 以此继续下去,直到所有的添加边(u1,v1), (u2,v2), (uk/2,vk/2)全部删去,得到k/2条边互不相重的路(迹)。 14优学课堂 练习 317页（1） 15优学课堂 317317页（页（2 2）证明：少于）证明：少于3030条边的平面连通简单图条边的平面连通简单图 至少有一个顶点的度不大于至少有一个顶点的度不大于4 4 。 证明：证明： 用反证法

12、。假设任一顶点的度均大于或等于用反证法。假设任一顶点的度均大于或等于5 5， 则则5v2e5v2e6060，即，即v v1212。 又因为又因为e3ve3v6 6，所以，所以5v2e6v5v2e6v1212 于是于是5v6v5v6v1212，即，即v12v12。矛盾。矛盾。 因此至少有一个顶点的度不大于因此至少有一个顶点的度不大于4 4 16优学课堂 练习 321页（1） (a) v*=5,e*=8,r*=5 17优学课堂 (b) v*=7,e*=13,r*=12 18优学课堂 (c) v*=5,e*=6,r*=3 19优学课堂 (d) v*=7,e*=12,r*=7 20优学课堂 证明：证明： 若图若图G是自对偶的，则是自对偶的，则v=v*，e=e*，即，即 r*=v=v*=r，e=e* 则由欧拉定理则由欧拉定理v-e+r=2 得得v-e+v=2，即，即e=2v-2。 若图若图G是自对偶的，则