图论 班 姓名 学号 图论作业 4 一、填空题 1. 长度至少为 3 的奇圈的点色数和边色数分别为 和 。 2. 彼得森图的点色数和边色数分别为 和 。 3. 已知树 T 的度序列为(1, 1, 1, 2, 2, 2, 3)，则 T 的点色数和边色数分别为 和 。 4. 方体 Q6的点色数和边色数分别为 和 。 5. 设 G 的阶数为 n，覆盖数为 β，则其独立数为 。 6. 完全图 Km,n (m≥n)的独立数和覆盖数分别为 和 。 7. 已知树 T 的阶数为 n，则其色多项式为 。 8. 拉姆齐数 R(3, 3)= 。 9. 图中强连通分支的个数为 。 10. 高为 h 的完全二元树至少有 片树叶。 11. 树叶带权分别为 1, 2, 4, 5, 6, 8 的最优二元树权值为 。 12. 设 m 元完全树有 t 片树叶，i 个分支点，则其总度数为 。 13. 对具有 m 条边的简单图定向，能得到 个不同的定向图。 二、不定项选择题 1. 下列说法错误的是( ) (A) 在正常着色下，图 G 的每个色组在 G 的补图中导出的子图是完全图； (B) 若图 G 非连通，则图 G 的补图必为连通图； (C) 图 G 与其补图具有相同的频序列； (D) 存在 14 阶的自补图； (E) 所有 4 阶图的补图都是可平面图； (F) 存在 6 阶可平面图 G，其补图也是可平面图； (G) 存在 8 阶外可平面图 G，其补图也是外可平面图。 2. 关于完全图 Kn，下列说法错误的是( ) (A) 点色数为 n； (B) 边色数为 n； (C) 点连通度为 n-1； (D) 边连通度为 n-1； (E) 是临界图； (F) 是唯一可着色图。 3. 设 G 是惟一 k(k≥2)可着色图，下列说法正确的是( ) (A) 最小度 δ(G)≥k-1; (B) 图 G 是 k-1 连通的； (C) 在 G 的任一正常 k 着色中，G 的任意两个色组的并导出的子图是连通的； (D) 在 G 的任一正常 k 着色中，G 的任意 l 个色组的并导出的子图是 l 连通的； (E) 若 G 是 k-1 正则的，则 G 必为 Kk。 1 / 3 

图论 班 姓名 学号 4. 下列说法正确的是( ) (A) 图 G 的独立集是其补图的团； (B) 点子集 S 是 G 的独立集当且仅当 S 的补集是 G 的覆盖； (C) 若图 G 没有孤立点，则 G 的边独立数与边覆盖数之和等于图 G 的阶数； (D) 若图 G 是偶图，则图 G 的边独立数等于点覆盖数； (E) 若图 G 是没有孤立点的偶图，则图 G 的点独立数等于边覆盖数。 5. 下列说法正确的是( ) (A) 在有向图中，顶点的出度之和等于边数的两倍； (B) 在有向欧拉图中，各点的度数必为偶数； (C) 在有向图的邻接矩阵中，所有元素之和等于边数的两倍； (D) 在无环有向图的关联矩阵中，各行元素之和均等于 0； (E) 在无环有向图的关联矩阵中，所有元素之和等于 0。 6. 对于有向图，下列说法错误的是( ) (A) 有向图 D 中任意一顶点只能处于 D 的某一个强连通分支中； (B) 在有向图 D 中，顶点 v 可能处于 D 的不同的单向连通分支中； (C) 有向连通图中顶点间的强连通关系是等价关系； (D) 有向连通图中顶点间的单向连通关系是等价关系； (E) 强连通图的所有顶点必然处于某一有向闭途径中。 三、解答题 1. 现有 5 个人 A, B, C, D, E 被邀请参加桥牌比赛。比赛的规则是：①每一场比赛由两个 2 人 组进行对决；②要求每个 2 人组(X, Y)都要与其它 2 人组(U, V)进行对决。若每个人都要与 其他任意一个人组成一个 2 人组，且每个组在同一天不能有多余一次的比赛，则最少需要安 排多少天比赛？ 2. 有 6 名博士生要进行论文答辩，答辩委员会成员分别是 A1={张教授，李教授，王教授}；A2={赵教授，钱教授，刘教授}； A3={严教授，王教授，刘教授}；A4={赵教授，梁教授，刘教授}； A5={张教授，钱教授，孙教授}；A6={李教授，王教授，严教授}。 要使教授们参加答辩不至于发生时间冲突，至少安排几次答辩时间段？请给出一种最少时间 段下的安排。 2 / 3 

图论 班 姓名 学号 3. 设 T 是一棵二元完全树，已知树叶数为 t(t≥2)，求 T 的边数。 4. 设 T 是 8 阶二元有序树，已知 T 的先序遍历和中序遍历分别为 52143768 与 12345678。 构造树 T 并求其后序遍历。 5. 求下图的色多项式及色数。 3 / 3