9 图 习题答案

练习 9.1 1.（l）证明：n 个顶点的简单图中不会有多于 条边。2)1(n （2）n 个顶点的有向完全图中恰有 条边。2 证: （l）由于简单图是没有重边和环的无向图，所以任意两个顶点之间最多有 1 条边，n 个顶 点最多有 C(n,2)=n(n-1)/2 条边。 （2）由于有向完全图是任何两个顶点都有有向边的图，所以 n 个顶点的边数总和为2nn 2. 分别画出下面两个图的补图及它的一个生成子图。 （1） （2） 解: （1） 补图 生成子图(不唯一) （2） 补图 生成子图(不唯一) 3. 一个简单图，如果同构于它的补，则该图称为自补图。 （1）给出一个 4 个顶点的自补图。 （2）给出一个 5 个顶点的自补图。 （3）是否有 3 个顶点或 6 个顶点的自补图？ （4）证明一个自补图一定有 4k 或 4k1 个顶点（k 为正整数） 。 解 （1）4 个顶点的自补图： （2）5 个顶点的自补图： （3）没有。 （4）证 设 G 为自补图，有 n 个顶点。我们已知 n 个顶点的完全图有 条边，2)1(n 因此 G 应恰有 条边。故或者 n 是 4 的整数倍，或者 n1 是 4 的整数倍，即图 G 一)1(n 定有 4k 或 4k1 个顶点（k 为正整数） 。 4. （l）证明图中（a ）与（b）同构。 (a) (b) （2）给出所有不同构的 4 个结点的简单图的图示。 证（l）在图（a ）图（b）间建立双射 h v A B D I J C E G H F h(v) 可逐一验证 (不赘) A D C B E F G H I J (u,v)E(a)当且仅当 (h(u),h(v)E(b) （2）所有不同构的 4 个结点的简单图的图示有如下 11 个： 练习 9.2 1. 证明：在简单无向图 G 中，从结点 u 到结点 v,如果既有奇数长度的通路又有偶数长 度的通路，那么 G 中必有一奇数长度的回路。 证 设 G 中，从结点 u 到结点 v 的奇数长度的通路为 O ，偶数长度的通路为 E。对 O 和 E 的除结点 u 和 v 的相交结点的数目归纳 k。 k=0,那么 O 和 E 恰好构成 G 的奇数长度的回路。 设奇数长度的通路与偶数长度的通路的相交结点的数目少于 k 时，命题成立。 设图 G 中，从结点 u 到结点 v 的奇数长度的通路与偶数长度的通路有 k 个相交结点， 如图所示： 考虑结点 u 到结点 k,如果从结点 u 到结点 k,既有奇数长度的通路又有偶数长度的通路， 那么据归纳假设，其中有一奇数长度的回路，因而 G 中必有一奇数长度的回路。如果从结 点 u 到结点 k 的两条通路均为偶数长度，或均为奇数长度，那么结点 k 到结点 v 必然既有 奇数长度的通路又有偶数长度的通路，因而构成一奇数长度的回路。 2. 证明：若简单无向图 G 是不连通的，那么 G必定是连通的。 证 设简单无向图 G 是不连通的，那么 G 由两个不相关的子图（没有任何边关联分别 在 两个子图中的顶点）G1，G2 组成，分别有顶点，u 1,u2,uk 和 v1,v2,vl。由于边 （u i ,vj）均不在 G 中（i=1,2,k, j=1,2,l ） 因此（u i ,vj）全部在 G中，从而 G是连通的。 3. 给出下图中有向图的强分图，单向分图和弱分图。 4. u 1 2 k v 解 图中有向图的强分图有： , , , , , 图中有向图的单向分图有： , , , 图中有向图的弱分图有： , , , 4. 有 7 个人 a，b，c ，d，e，f ，g 分别精通下列语言，问他们 7 人是否可以自由交谈（必 要时借助他人作翻译） 。 a 精通英语。 b 精通汉语和英语。 c 精通英语、俄语和意大利语。 d 精通日语和英语。 e 精通德语和意大利语。 f 精通法语、日语和俄语。 g 精通法语和德语。 解 下图中 7 个顶点表示 7 个人，关联两个顶点的边表示两个人同时精通某一种语言： 由于该图是连通的，因此他们 7 人是可以自由交谈（必要时借助他人作翻译） 。 v1 v2 v7 v10 v4 v3 v8 v9 v5 v6 a b d c e g f 5. v 是简单连通图 G 的割点，当且仅当 G 中存在两个顶点 v1，v2，使 v1 到 v2 的通路都经 过顶点 v 。试证明之。 证充分性是显然的。 必要性：设顶点 v 是简单连通图 G 的割点，如果不存在两个顶点 v1，v2，使 v1 到 v2 的通路都经过顶点 v，那么对任意两个顶点 v1，v2，都有一条通路不经过顶点 v，因而删 除顶点 v 不能使 G 不连通，与 v 是简单连通图 G 的割点矛盾。故 G 中必存在两个顶点 v1，v2，使 v1 到 v2 的通路都经过顶点 v 。 6. 简单连通图 G 的割边，当且仅当 e 不在 G 的任一回路上。试证明之。 证 设 e 是简单连通图 G 的割边，其端点为 u,v 。删除边 e 后，u,v 应在两个不同的连 通分支中。若 e 在 G 的一条回路上，那么删除边 e 后，u,v 应仍在一条通路上，矛盾。故 e 不在 G 的任一回路上。 反之，设 e 不在 G 的任一回路上，而 e 不是简单连通图 G 的割边。那么 G-e仍是连 通的，故还有 u 到 v 的一条通路，从而这条通路连同边 e 构成 G 中的一条回路，矛盾。因 此边 e 是简单连通图 G 的割边 练习 9.3 1. 试作出四个图的图示，使第一个既为欧拉图又为哈密顿图；第二个是欧拉图而非哈密顿 图；第三个是哈密顿图却非欧拉图；第四个既非欧拉图也非哈密顿图。 解（a）既为欧拉图又为哈密顿图；（b）是欧拉图而非哈密顿图；（c）是哈密顿图却非欧 拉图；（d）既非欧拉图也非哈密顿图。 2问 n 为何种数值时，K n 既是欧拉图又是哈密顿图。问 k 为何值时，k- 正则图既是欧拉 图又是哈密顿图。 解 n 为奇数时，K n 既是欧拉图又是哈密顿图。k 为大于或等于 n/2 的偶数时，k- 正则图既 是欧拉图又是哈密顿图。 3判别图中各图是否为欧拉图。 （a） (b) (c) (d) （a） （b） 解 （a）所有顶点的度都是偶数，它是为欧拉图。 （b）并非所有顶点的度都是偶数，它是不是欧拉图 （根据定理 7.11。 ） 411 个学生在一张圆桌旁共进晚餐，要求在每次晚餐上每个学生的邻座都与其它各次晚 餐的邻座不同。问这样共进晚餐能安排多少次。 解 每个学生作为一个顶点，做成一个 Kn图。就餐时邻座学生之间作一条边，每次就餐座 位安排就是一个哈密顿回路。要求每次就餐邻座不同，就是求无任何公共边的哈密顿回路 的个数。根据定理 7.14，可以安排（11-1）/2=5 次。 5判别图中各图是否为哈密顿图，若不是，请说明理由，并回答它是否有哈密顿通路。 解（a） ，(b) 是为哈密顿图。(c) 不是哈密顿图，也没有哈密顿通路。在图(c)中增加顶点 k ，并对其顶点做二着色，构成图(d)（如下） 。图(d) 不是哈密顿图，也没有哈密顿通路。因 为图中白色顶点比黑色顶点多两个。故(c) 不是哈密顿图，也没有哈密顿通路。否则它的 哈密顿回路或哈密顿通路必定经过顶点 k（k 在两个二度顶点之间的边上） ，从而图(d) 也 是哈密顿图，也有哈密顿通路，矛盾。 （a） (b) (c) k （d） 练习 9.4 1. 对给出的有向图 G: （1）计算它的邻接矩阵 A 及 A2，A 3，A 4，A 5。 （2）计算它的路径矩阵 B。 （3）计算它的可达性矩阵 P。 （4）请通过上述矩阵判断有几条长度为 2 的回路？从 c 到 b 有几条长度为 3 的拟路径？ 解 (1) 它的邻接矩阵 A= A2= 01010101 A3= A4= A5= 120101203223012463 (2)它的路径矩阵 B= 1 (3)它的可达性矩阵 P= 1 （4） 从 A2 中可以知道，有 2 条长度为 2 的回路。(bcb, cbc) 从 A3 中可以知道，从 c 到 b 有 3 条长度为 3 的拟路径。 (cbcb, ceab, cdab) 从 c 到 b 有 2 条长度为 3 的路径。(ceab, cdab) 2. 对给出的有向图 G: （1）计算它的邻接矩阵 A 及 A2，A 3，A 4，说出从 v1到 v4的长度为 l，2，3，4 的拟 路径各有多少条。 （2）计算 AA，A A，说出它们中第 2，3 分量及第 4，4 分量的意义。 （3）计算它的路径矩阵 B 及可达性矩阵 P，并从 P 说出 G 的各强分图。 解 (1) 它的邻接矩阵 A= v1到 v4的长度为 1 的拟路径各有 1 条。 01001 A2= v1到 v4的长度为 2 的拟路径各有 1 条。 01 A3= v1到 v4的长度为 3 的拟路径各有 1 条。 01 v1 v2 v3 v4 v5 A4= v1到 v4的长度为 4 的拟路径各有 2 条。 2100210 A5= 2100 (2) AA= = 010001021022012 A A= = 010011032 AA中第 2，3 分量为 0，表