图论 班 姓名 学号 图论作业 2 5 1 2 3 6 3 4 2 2 2 2 一、填空题 1. 图 G 的顶点数为 n 且 7 连通，则其边数至少为 。 2. 彼得森图的点连通度和边连通度分别为 和 。 3. 非平凡树的点连通度和边连通度分别为 和 。 4. 长度为 n (n≥3)的圈的 2 宽直径为 。 5. 完全图 Kn (n≥5)的 3 宽直径为 。 6. 设图 G 是具有 k 个奇度顶点，则在 G 中最少添加 条边才能使 G 具有欧拉回路。 7. 完全偶图 Km,n (m, n≥2 且均为偶数)，则在其最优欧拉环游中共含 条边。 8. 下图的最优欧拉环游的权值为 。 9. 具有 5 个点的度极大非哈密尔顿图族为______和_______。 二、不定项选择题 1. 下列说法正确的是( ) (A) 有割边的图一定有割点； (B) 有割点的图一定有割边； (C) 割点至少属于图的两个块； (D) 割边不在图的任一圈中； (E) 图的割点也是子图的割点。 2. 设 κ(G), λ(G), δ(G)分别表示图 G 的点连通度、边连通度和最小度。下面说法错误的是( ) (A) 存在图 G，使得 κ(G)=λ(G)=δ(G)； (B) 存在图 G，使得 κ(G)<λ(G)<δ(G)； (C) 设 G 是 n 阶简单图，若 δ(G)≥n/2，则 G 连通且 λ(G)=δ(G)； (D) 图 G 是 k 连通的，则 κ(G)=k； (E) 若图 G 是 k 连通的，则 λ(G)≥k。 3. 下面说法错误的是( ) (A) 2 连通图一定没有割点(假定可以有自环)； (B) 2 连通图一定没有割边； (C) 完全图一定没有割边； (D) 非平凡树一定有割边； (E) 非平凡树一定有割点。 4. 下面说法正确的是( ) (A) 若图 G 是 k 连通的，则 G 中必存在 k 点割； 1 / 4 

图论 班 姓名 学号 (B) 若图 G 是 k 连通的，则 G 也是 k 边连通的； (C) 若图 G 是 k 边连通的，则 G 也是 k 连通的； (D) 存在最小度为 3 的 4 连通图； (E) 存在具有 n 个点、m 条边的[2m/n+1]连通图。 5. 设图 G 是一个块，下列说法错误的是( ) (A) 图中一定有圈； (B) 图中一定无环； (C) 若 G 的阶数大于等于 3，则 G 中任意两点必位于某一圈上； (D) 若 G 的阶数大于等于 3，则 G 中任意两条边必位于某一圈上； (E) 若 G 的阶数大于等于 3，则 G 中没有割边。 6. 下面说法错误的是( ) (A) 顶点度数为偶数的图一定是欧拉图； (B) 欧拉图一定没有割点； (C) 欧拉图一定没有割边； (D) 非平凡欧拉图中一定有圈； (E) 至少具有 2 个点的无环欧拉图一定是 2 边连通的。 7. 关于哈密尔顿图，下列命题错误的是( ) (A) 若 G 是哈密尔顿图，则对于 V 的每个非空顶点子集 S，均有ω(G-S)≤|S|； (B) 设 G 是阶数为 n (n≥3)的简单图，若其最小度 δ≥n/2，则 G 是哈密尔顿图； (C) 设 G 是 n (n≥3)阶简单图，若 G 中任意两个不邻接点 u 与 v，满足 d(u)+d(v)≥n，则 G 是 哈密尔顿图； (D) 哈密尔顿图一定没有割边； (E) 哈密尔顿图一定没有割点。 8. 关于哈密尔顿图，下列命题正确的是( ) (A) 设 n (n≥3)阶简单图的最小度满足 δ≥n/2，则其闭包一定为完全图； (B) 设 n (n≥3)阶简单图的任意两个不邻接顶点 u 与 v 满足 d(u)+d(v)≥n，则其闭包一定为完 全图； (C) 设图 G 满足度序列判定定理的条件，则其闭包一定为完全图； (D) 若简单图 G 的闭包不是完全图，则它一定是非哈密尔顿图； (E) 若简单图 G 的闭包是完全图，则图 G 是哈密尔顿图。 9. 关于哈密尔顿图，下列命题错误的是( ) (A) 设 G 是阶数为 n (n≥3)的非哈密尔顿简单图，则 G 度弱于某个 Cm,n图； (B) 图 G 是哈密尔顿图当且仅当其闭包是完全图； (C) 若(n, m)简单图 G 的边数 m > n −  2  1    + 1 ， 且 n≥3，则 G 是哈密尔顿图； (D) 若图 G 的闭包是哈密尔顿图，则其闭包一定是完全图； (E) 设 G 是阶数为 n (n≥3)的哈密尔顿简单图，若 n 为奇数，则 G 一定不是偶图。 三、解答题 1. 证明：在简单图 G 中，若任意两个不相邻的点之间存在 k 条独立的路，则任意两个不同 点之间存在 k 条独立的路。 2 / 4 

图论 班 姓名 学号 2. 在 8×8 黑白方格相间的棋盘上跳动一只马，这只马能否连续地完成每一种可能的跳动恰 好一次？（一只马跳动一次是指从一个长为 3、宽为 2 的黑白方格组成的长方形的一个角跳 到对角上） 3. 证明：彼得森图不是哈密尔顿图。 4. 若图 G 不是哈密尔顿图，但对于任意点 v，G-v 都是哈密尔顿图，则称 G 是超哈密尔顿 图。彼得森图是否为超哈密尔顿图？ 3 / 4 

图论 班 姓名 学号 5. 今有 a, b, c, d, e, f, g 七个人围圆桌开会，已知：a 会讲英语，b 会讲英语和汉语，c 会讲 英语、意大利语和俄语，d 会讲日语和汉语，e 会讲德语和意大利语，f 会讲法语、日语和俄 语，g 会讲法语与德语。是否存在一种排座方法，使每个人能够和他身边的人交流？并说明 理由。 4 / 4