1、第 7章 习题课练习 7-1（ 6）简单图的最大度小于结点数。证明：设简单图 G中有 n个结点。任取一个结点 v， 由已知 G是简单图没有环和重边， v至多和 n-1个结点相邻， 也即 deg(v) n-1, 而 (G) max deg(v) n-1, 因此 最大度小于结点数。练习 7-2（ 2）：若无向图 G中恰有两个奇数度的结点，则这两个结点之间必有一条路。证明：设无向图 G中两个奇数度的结点为 u和 v。从 u开始构造一条迹，即从 u出发经关联于结点 u的边 e1到达结点u1，若 deg(u1)为偶数 ,则必可由 u1再经关联于结点 u1的边 e2到达结点 u2,如此继续下去 ,每边只取
2、一次 ,直到另一个奇数度结点停止 ,由于图 G中只有两个奇数度结点 ,故该结点或是 u或是 v。 如果是 v,那么从 u到 v的一条路就构造好了。如果仍是结点 u,此路是闭迹。闭迹上每个结点都是关联偶数条边 ,而 deg(u)为奇数 ,所以至少还有一条关联于结点 u的边不在此闭迹上。继续从 u出发 ,沿着该边到达另一个结点 u1,依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点 v,这就是一条从 u到 v的路。练习 7-2（ 3）：若图 G是不连通的，则 G的补图 G是连通的。证明：若 G=是不连通的，可设图 G的连通分支为GV1,GV2,GV m(m2)。由于任意两个连通分支
3、GVi,GVj不连通，因此 Vi与 Vj之间的连线在补图中，在 G中任取两个结点 u和 v，则 u和 v的位置有两种情况：1)若 u和 v均在同一个连通分支 GVi中 ,根据上面的分析，可在另一个连通分支 GVj（ ij)中取一个结点 w，使得u与 w， v 与 w在 G中连通，故有 u w v，即 u与 v在 G中连通2)若 u与 v分别属于两个不同的连通分支 GVi与 GVj，由上面的分析可知， u与 v在 G中连通。故当图 G不连通时，则补图 G是连通的7-2（ 4） :当且仅当 G的一条边 e不包含在 G的回路中时， e才是 G的割边。证明：必要性。（ e是 G的割边）设 e是连通图
4、G的割边， e关联的两个结点是 u和 v。 如果 e包含在G的一个回路中，那么除边 e=(u,v)外还有另一条分别以 u和 v为端点的路，所以删去边 e后， G仍为连通图，这与 e是割边相矛盾。充分性。如果边 e不包含在 G的任一条回路中，那么连接结点 u和 v的边只有 e， 而不会有其它连接 u和 v的任何路。因为如果连接 u和 v还有不同于边 e的路，此路与边 e就组成一条包含边 e的回路，从而导致矛盾。所以删去边 e后， u和 v就不连通，故边 e是割边。300页（ 2） 如果 u可达 v， 它们之间可能不止一条路，在所有这些路中，最短路的长度称为 u和 v之间的距离（或短程线），记作
5、d， 如果从 u到 v是不可达的，则通常写成 d =距离矩阵为0 1 2 1 0 1 1 1 0 1 1 2 0dij=1表示存在边 。300页（ 3）用 Warshall算法求可达性矩阵。邻接矩阵为0 0 0 0 01 0 1 1 01 0 0 0 00 0 1 0 00 0 0 0 0A=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 01 0 1 1 01 0 0 0 01 0 1 0 00 0 0 0 0A=i=4时，因为 A4,2=1，将
6、第四行加到第 2行， A不变。i=5时，因为 A的第 5列全为 0，所以 A不变。 0 0 0 0 01 0 1 1 01 0 0 0 01 0 1 0 00 0 0 0 0P=故 A的可达性矩阵为：距离矩阵为0 1 0 1 1 1 0 2 1 0 0300页（ 4）：写出如图 7-3.11所示的图 G的完全关联矩阵，并验证其秩如定理 7-3.2所述。e1 e2 e3 e4 e5 e6 e7 e8 e9A 1 0 0 0 0 1 0 1 0B 0 1 1 0 0 0 1 0 0C 0 0 0 1 1 0 0 1 0D 1 1 0 0 0 0 0 0 1E 0 0 0 0 1 1 1 0 0F 0 0 1 1 0 0 0 0 1完全关联矩阵为 :此图为连通图，由定理7-3.2，其秩为 5。311页（ 2）构造一个欧拉图，其结点数 v和 边数 e满足下述条件a)v， e的奇偶性一样。b) v， e的奇偶性相反。如果不可能，说明原因。v=3,e=3v=5,e=5v=4,e=4 v=4,e=6v=7,e=8v=6,e=7无向图 G具有一条欧拉回路，当且仅当 G是连通的，并且所有结点度数全为偶数。下面的图中所有结点度数全为偶数，所以都是欧拉图。
