图论作业 4

一、填空题

1. 长度至少为 $3$$3$ 的奇圈的点色数和边色数分别为 $3$$3$ 和 $3$$3$

考点：点色数 + 边色数

2. 彼得森图的点色数和边色数分别为 $3$$3$ 和 $4$$4$

3. 已知树 $T$$T$ 的度序列为 $(1,1,1,2,2,2,3)$$(1,1,1,2,2,2,3)$，则 $T$$T$ 的点色数和边色数分别为 $2$$2$ 和 $3$$3$

考点：二部图点色数 + 边色数

二部图的点色数和边色数分别为 $2$$2$ 和最大度

一棵树肯定是二部图

4. 方体 $Q_6$$Q_6$ 的点色数和边色数分别为 $2$$2$ 和 $6$$6$

考点：二部图点色数 + 变色数

二部图的点色数和边色数分别为 $2$$2$ 和最大度

$n$$n$ 方体是 $n$$n$ 正则二部图

5. 设 $G$$G$ 的阶数为 $n$$n$，覆盖数为 $\beta$$\beta$，则其独立数为 $n-\beta$$n-\beta$

考点：独立数 + 覆盖数 = 阶数

定理 117 (Gallai)：对任意的 $n$$n$ 阶图 $G$$G$，有 $\alpha (G)+\beta (G)=n$$\alpha(G) + \beta(G) = n$

6. 完全图 $K_{m,n}(m\ge n)$$K_{m,n} \ (m \ge n)$ 的独立数和覆盖数分别为 $m$$m$ 和 $n$$n$

考点：二部图独立数、覆盖数

独立数 $=max(m,n)$$= \max(m ,n)$

$|V|=m+n$$|V|=m+n$

7. 已知树 $T$$T$ 的阶数为 $n$$n$，则其色多项式为 $k(k-1{)}^{n-1}$$k(k-1)^{n-1}$

考点：树的色多项式 (知道即可)

注意：树的色多项式绝对不会考

$G$$G$ 是具有 $n$$n$ 个点的树，则 $P_k(G)=k(k-1{)}^{n-1}$$P_k(G)=k(k-1)^{n-1}$

8. 拉姆齐数 $R(3,3)=$$R(3, 3)=$ $6$$6$

注意：考的概率很小

Ramsey 数 只需知道 $R(3,3)=6;R(4,4)=18$$R(3,3) = 6; \ R(4,4) = 18$

9. 图中强连通分支的个数为 $3$$3$

注意 (重要)：判断一个有向图有多少强连通分支和单向连通分支；只能从特殊的点出发

左上角两个顶点只有出去的，没有进来的，两个点构成一个强连通分支

右上角顶点单独为一个强连通分支

剩余五个顶点被一条有向闭途径连接起来，所以在一个强连通分支中

10. 高为 $h$$h$ 的完全二元树至少有 $h+1$$h+1$ 片树叶

叶子节点出现的越晚，叶子节点越多

例：二元完全树 $(m=2)$$(m = 2)$，则分支点数为 $i=t-1$$i = t−1$，边数之和为 $m(T)=2(t-1)$$m(T) = 2(t − 1)$。另外，高度为 $h$$h$ 的二元完全树最少有 $h+1$$h + 1$ 片叶子

11. 树叶带权分别为 $1,2,4,5,6,8$$1,2, 4, 5, 6, 8$ 的最优二元树权值为 $62$$62$

考点：哈夫曼编码

$W=(1+2)\times 4+4\times 3+(5+6+8)\times 2=62$$W = (1+2) \times 4 + 4 \times 3 + (5+6+8) \times 2 = 62$

12. 设 $m$$m$ 元完全树有 $t$$t$ 片树叶，$i$$i$ 个分支点，则其总度数为 $2(t+i-1)$$2(t+i-1)$ 或 $2mi$$2mi$

定理 121: 设 $D=(V,E)$$D=(V,E)$ 是一个有向图，则有 $\sum _{v\in V}{d}^{+}(v)=\sum _{v\in V}{d}^{-}(v)=|E|$$\sum\limits_{v\in V}d^+(v)=\sum\limits_{v\in V}d^-(v)=|E|$

总度数 $=\sum _{v\in V}{d}^{+}(v)+\sum _{v\in V}{d}^{-}(v)=2|E|$$= \sum\limits_{v\in V}d^+(v) + \sum\limits_{v\in V}d^-(v) = 2|E|$

对于树，边数 = 顶点数 - 1

顶点数 = 树叶 + 分支点 = $t+i$$t + i$

所以：$=\sum _{v\in V}{d}^{+}(v)+\sum _{v\in V}{d}^{-}(v)=2|E|=2(t+i-1)$$= \sum\limits_{v\in V}d^+(v) + \sum\limits_{v\in V}d^-(v) = 2|E| = 2(t+i-1)$

---

出度全部由于分支点，因为树叶的出度为 $0$$0$，所以：$\sum _{v\in V}{d}^{+}(v)=mi$$\sum\limits_{v\in V}d^+(v)=mi$

所以：$\sum _{v\in V}{d}^{+}(v)+\sum _{v\in V}{d}^{-}(v)=2mi$$\sum\limits_{v\in V}d^+(v) + \sum\limits_{v\in V}d^-(v) = 2mi$

13. 对具有 $m$$m$ 条边的简单图定向，能得到 $2^m$$2^m$ 个不同的定向图

无环图即可

(感觉不会考 🐶)

二、不定性选择题

1. 下列说法错误的是 (DG)

• A. 在正常着色下，图 $G$$G$ 的每个色组在 $G$$G$ 的补图中导出的子图是完全图
• B. 若图 $G$$G$ 非连通，则图 $G$$G$ 的补图必为连通图
• C. 图 $G$$G$ 与其补图具有相同的频序列
• D. 存在 $14$$14$ 阶的自补图 ❌
• E. 所有 $4$$4$ 阶图的补图都是可平面图
• F. 存在 $6$$6$ 阶可平面图 $G$$G$，其补图也是可平面图
• G. 存在 $8$$8$ 阶外可平面图 $G$$G$，其补图也是外可平面图 ❌

考点：关于补图的知识点

F 相关结论 (不会考)：定理 91：至少有 9 个点的简单可平面图的补图是不可平面的，而 9 是这种数目中最小的一个

G 相关结论 (不会考)：定理 84：每个至少有 7 个顶点的外可平面的补图不是外可平面图，且 7 是这个数目的最小者

A 正确：正常着色 (点着色)，原图中每个色组中的点肯定无边相连，所以补图中一定是完全图

B 正确

C 正确：定理 6：一个 $n$$n$ 阶图 $G$$G$ 和它的补图有相同的频序列；注意是频序列，不是度序列

D 错误：定理 1：若 $n$$n$ 阶图 $G$$G$ 是自补的（即 $G\cong \bar{G}$$G \cong \overline G$），则 $n\equiv 0,1(\mathrm{mod}4)$$n \equiv 0,1\pmod{4}$

E 正确：$K_4$$K_4$ 是可平面图，任何一个 $4$$4$ 阶简单图一定是一个可平面图；所以 $4$$4$ 阶图的补图也一定是可平面图

F 正确：对于阶数小于 $9$$9$ 的简单可平面图，补图依然是可平面图

G 错误

2. 关于完全图 $K_n$$K_n$，下列说法错误的是 (B)

• A. 点色数为 $n$$n$
• B. 边色数为 $n$$n$ ❌
• C. 点连通度为 $n-1$$n-1$
• D. 边连通度为 $n-1$$n-1$
• E. 是临界图
• F. 是唯一可着色图

考点：对完全图的理解

注意： E 和 F 涉及到第七章最后一节课讲的内容，不作要求 (临界图、唯一可着色图、不含三角形的 $k$$k$ 色图、完美图等等)

A 显然正确

B 错误：根据奇偶分成两种情况

C 正确 D 正确：关于完全图，需要记住无点割，有边割

E 正确：完全图是临界图

F 正确：完全图是唯一可着色图

3. 设 $G$$G$ 是唯一 $k(k\ge 2)$$k \ (k \ge 2)$ 可着色图，下列说法正确的是 (ABCDE)

• A. 最小度 $\delta (G)>k-1$$\delta(G)>k-1$
• B. 图 $G$$G$ 是 $k-1$$k-1$ 连通的
• C. 在 $G$$G$ 的任一正常 $k$$k$ 着色中，$G$$G$ 的任意两个色组的并导出的子图是连通的
• D. 在 $G$$G$ 的任一正常 $k$$k$ 着色中，$G$$G$ 的任意 $l$$l$ 个色组的并导出的子图是 $l$$l$ 连通的
• E. 若 $G$$G$ 是 $k-1$$k-1$ 正则的，则 $G$$G$ 必为 $K_k$$K_k$

注意：本题涉及的知识点不考

4. 下列说法正确的是 (ABCDE)

• A. 图 $G$$G$ 的独立集是其补图的团
• B. 点子集 $S$$S$ 是 $G$$G$ 的独立集当且仅当 $S$$S$ 的补集是 $G$$G$ 的覆盖
• C. 若图 $G$$G$ 没有孤立点，则 $G$$G$ 的边独立数与边覆盖数之和等于图 $G$$G$ 的阶数
• D. 若图 $G$$G$ 是偶图，则图 $G$$G$ 的边独立数等于点覆盖数
• E. 若图 $G$$G$ 是没有孤立点的偶图，则图 $G$$G$ 的点独立数等于边覆盖数

A 正确：图 $G$$G$ 的独立集即为各不相邻的顶点，其补图一定都相邻，故为团

B 正确：定理 116：给定图 $G=(V,E)$$G=(V,E)$ 且 $S\subseteq V$$S \subseteq V$，则 $S$$S$ 是 $G$$G$ 的独立集当且仅当 $V\setminus S$$V\setminus S$ 是 $G$$G$ 的覆盖

C 正确：定理 118 (Gallai)：对任意不含孤立点的 $n$$n$ 阶图 $G$$G$，有 ${\alpha }^{{}^{\prime }}(G)+{\beta }^{{}^{\prime }}(G)=n$$\alpha^{'}(G) + \beta^{'}(G) = n$

D 正确：对于二部图，无论是否有孤立点，图 $G$$G$ 的边独立数等于点覆盖数（最重要，必须掌握）

E 正确：定理 119: 设 $G$$G$ 是无孤立点的偶图，则 $G$$G$ 中最大独立集包含的顶点数等于最小边覆盖包含的边数

5. 下列说法正确的是 (BE)

• A. 在有向图中，顶点的出度之和等于边数的两倍 ❌
• B. 在有向欧拉图中，各点的度数必为偶数
• C. 在有向图的邻接矩阵中，所有元素之和等于边数的两倍 ❌
• D. 在无环有向图的关联矩阵中，各行元素之和均等于 $0$$0$ ❌
• E. 在无环有向图的关联矩阵中，所有元素之和等于 $0$$0$

考点：有向图

A 错误：定理 121: 设 $D=(V,E)$$D=(V,E)$ 是一个有向图，则有 $\sum _{v\in V}{d}^{+}(v)=\sum _{v\in V}{d}^{-}(v)=|E|$$\sum\limits_{v\in V}d^+(v)=\sum\limits_{v\in V}d^-(v)=|E|$

B 正确：出度 = 入度；度数 = 出度 + 入度 = 2 * 出度

C 错误：有向图的邻接矩阵中，行和 = 顶点的出度，列和 = 顶点的入度；所有元素之和 = 出度之和 = 入度之和 = 边数

D 错误：关联矩阵每一列恰有一个「1」和一个「-1」，第 $i$$i$ 行的 1 的个数等于 $d^{+}(v_i)$$d^+(v_i)$，-1 的个数等于 $d^{-}(v_i)$$d^-(v_i)$

E 正确：每一列和均为 $0$$0$，所以列和也为 $0$$0$

6. 对于有向图，下列说法错误的是 (D)

• A. 有向图 $D$$D$ 中任意一顶点只能处于 $D$$D$ 的某一个强连通分支中
• B. 在有向图 $D$$D$ 中，顶点 $v$$v$ 可能处于 $D$$D$ 的不同的单向连通分支中
• C. 有向连通图中顶点间的强连通关系是等价关系
• D. 有向连通图中顶点间的单向连通关系是等价关系 ❌
• E. 强连通图的所有顶点必然处于某一有向闭途径中

A 正确：定理 123: 有向图 $D=(V,E)$$D=(V,E)$ 的每个点位于且仅位于 $D$$D$ 的一个强 (弱) 连通分支中

B 正确： 注：有向图 $D$$D$ 的某个顶点，可能会分属于 $D$$D$ 的若干个单向连通分支。因为单向连通关系不是等价关系

C 正确

D 错误：见选项 B 分析

E 正确：定理 122: 有向图 $D=(V,E)$$D=(V,E)$ 是强连通的当且仅当 $D$$D$ 中存在含有所有顶点的有向闭途径

三、解答题

1. 现有 $5$$5$ 个人 $A,B,C,D,E$$A,B,C,D,E$ 被邀请参加桥牌比赛。比赛的规则是：① 每一场比赛由两个 $2$$2$ 人组进行对决；② 要求每个 $2$$2$ 人组 $(X,Y)$$(X, Y)$ 都要与其它 $2$$2$ 人组 $(U,V)$$(U, V)$ 进行对决。若每个人都要与其他任意一个人组成一个 $2$$2$ 人组，且每个组在同一天不能有多于一次的比赛，则最少需要安排多少天比赛？

考点：「点着色」和「边着色」应用题

注意 1：✨ 考试注意识别到底是「点着色」还是「边着色」

注意 2：考试不会超过本题的难度

本题：「边着色」

分析：以每个二人组为顶点（共 10 个），两个二人组连一条线当且仅当四个人互不相同时

解：如果两个二人组涉及到四个不同的人，这两个二人组之间连一条边，那么每一场比赛就转换成图中的一条边

原问题就转换成求该图的边色数

显然这个图为彼得森图，彼得森图的边色数是 $4$$4$

所以最少需要安排 $4$$4$ 天的比赛

2. 有 $6$$6$ 名博士生要进行论文答辩，答辩委员会成员分别是 $A_1=\text{张}\text{教}\text{授}，\text{李}\text{教}\text{授}，\text{王}\text{教}\text{授}$$A_1={张教授，李教授，王教授}$；$A_2=\text{赵}\text{教}\text{授}，\text{钱}\text{教}\text{授}，\text{刘}\text{教}\text{授}$$A_2={赵教授，钱教授，刘教授}$ $A_3=\text{严}\text{教}\text{授}，\text{王}\text{教}\text{授}，\text{刘}\text{教}\text{授}$$A_3={严教授，王教授，刘教授}$；$A_4=\text{赵}\text{教}\text{授}，\text{梁}\text{教}\text{授}，\text{刘}\text{教}\text{授}$$A_4={赵教授，梁教授，刘教授}$ $A_5=\text{张}\text{教}\text{授}，\text{钱}\text{教}\text{授}，\text{孙}\text{教}\text{授}$$A_5={张教授，钱教授，孙教授}$；$A_6=\text{李}\text{教}\text{授}，\text{王}\text{教}\text{授}，\text{严}\text{教}\text{授}$$A_6={李教授，王教授，严教授}$ 要使教授们参加答辩不至于发生时间冲突，至少安排几次答辩时间段？请给出一种最少时间段下的安排

考点：点色数和边色数应用题

注意：✨ 考试注意识别到底是「点着色」还是「边着色」

解：以博士生为顶点，如果两名博士生有相同的答辩委员会成员，则连接一条边，他们的答辩时间就不能安排在一起，必须错开

如上图，点色数为 $3$$3$。所以，至少安排 $3$$3$ 次答辩时间段

3. (19 年考过) 设 $T$$T$ 是一棵二元完全树，已知树叶数为 $t(t\ge 2)$$t \ (t \ge 2)$，求 $T$$T$ 的边数

解：假设有 $x$$x$ 个分支点，那么出度之和为 $2x$$2x$

出度之和 = 边数 = $t+x-1=2x$$t + x - 1 = 2x$

得 $x=t-1$$x = t - 1$

所以 $m=2t-2$$m = 2t-2$

4. 设 $T$$T$ 是 $8$$8$ 阶二元有序树，已知 $T$$T$ 的先序遍历和中序遍历分别为 $52143768$$52143768$ 与 $12345678$$12345678$。构造树 $T$$T$ 并求其后序遍历

解：

后序遍历：$13426875$$13426875$

5. 求下图的色多项式及色数

注意 1：使用的方法肯定是「递推计数法」或「理想子图法」

注意 2：先不要纠结使用什么方法，先画出补图，再决定方法

解：画出 $G$$G$ 的补图

求出补图的伴随多项式：$h(\bar{G},x)=(x+x^2)(x^2+4x^3+x^4)=x^3+5x^4+5x^5+x^6$$h(\overline G, x)=(x+x^2)(x^2+4x^3+x^4)=x^3+5x^4+5x^5+x^6$

将 $x^i=[k{]}_i$$x^i = [k]_i$ 代入伴随多项式中得到 $P_k(G)$$P_k(G)$：

$$\begin{array}{rl}{P}_k(G)& =[k{]}_3+5[k{]}_4+5[k{]}_5+[k{]}_6\\ & =k(k-1)(k-2)+5k(k-1)(k-2)(k-3)\\ & +5k(k-1)(k-2)(k-3)(k-4)\\ & +k(k-1)(k-2)(k-3)(k-4)(k-5)\end{array}$$

---

扩展：根据色多项式求原图的的点色数

方法：使 $P_k(G)>0$$P_k(G) > 0$ 最小的 $k$$k$ 值，从 $k=1,2,3\cdots$$k = 1,2,3\cdots$ 一个一个的试

当 $k=1$$k = 1$ 时，$P_k(G)=0$$P_k(G) = 0$

当 $k=2$$k = 2$ 时，$P_k(G)=0$$P_k(G) = 0$

当 $k=3$$k = 3$ 时，$P_k(G)=6>0$$P_k(G) = 6 > 0$

所以原图的点色数为 $3$$3$