图论作业 1

一、填空题

1. 非同构的 $4$$4$ 阶和 $5$$5$ 阶树的个数分别为 $2$$2$ 和 $3$$3$

方法：按照树中存在的最长路进行枚举 (从 $2$$2$ 开始)

注意：对于 $n\ge 2$$n \ge 2$ 的树来说，路的最短长度为 $2$$2$

2. $n$$n$ 阶 $k$$k$ 正则图 $G$$G$ 的补图的边数为 $[n(n-1)-nk]/2$$[n(n-1) - nk]/2$

考点一：完全图每个点的度数是 $(n-1)$$(n-1)$ ✨

考点二：一个图和其补图的并是完全图 $\Rightarrow$$\Rightarrow$ 一个点在原图和补图中的度数和为 $(n-1)$$(n-1)$

图 $G$$G$ 是 $k$$k$ 正则，那么图 $G$$G$ 的补图为 $(n-1-k)$$(n-1-k)$ 正则。故补图的度数之和为 $d(\bar{G})=n(n-1-k)$$d(\overline G)=n(n-1-k)$

根据握手定理：$m=d(\bar{G})/2=n(n-1-k)/2$$m=d(\overline G)/2=n(n-1-k)/2$

3. 设图 $G=(n,m)$$G=(n,m)$ 中各顶点度数均为 $3$$3$，且 $2n=m+3$$2n=m+3$，则 n = $6$$6$，m = $9$$9$

考点：握手定理

根据握手定理：$2m=3n$$2m=3n$

4. 设简单图 $G$$G$ 的邻接矩阵为 $A$$A$，且

则图 $G$$G$ 的边数为 $6$$6$

考点：邻接矩阵的性质

定理 10：令 $G$$G$ 是一个有推广邻接矩阵 $A$$A$ 的 $p$$p$ 阶标定图，则 $A^n$$A^n$ 的 $i$$i$ 行 $j$$j$ 列元素 $a_{ij}^{(n)}$$a^{(n)}_{ij}$ 等于由 $v_i$$v_i$ 到 $v_j$$v_j$ 的长度为 $n$$n$ 的途径的数目

推论：设 $A$$A$ 为简单图 $G$$G$ 的邻接矩阵，则：$A^2$$A^2$ 的元素 $a_{ii}^{(2)}$$a^{(2)}_{ii}$ 是 $v_i$$v_i$ 的度数。$A^3$$A^3$ 的元素 $a_{ii}^{(3)}$$a^{(3)}_{ii}$ 是含 $v_i$$v_i$ 的三角形的数目的两倍 （考过填空）

5. 设 $G$$G$ 是一个完全 $l$$l$ 部图，$n_i$$n_i$ 是第 $i$$i$ 部分的顶点数，则它的边数为 $\sum _{1\le i\le j\le l}{n}_i{n}_j$$\sum\limits_{1 \le i \le j \le l}n_in_j$

考点：完全多部图的概念与结构

完全 $l$$l$ 部图 $K_{n_1,n_2,\cdots ,n_l}$$K_{n_1,n_2,\cdots,n_l}$ 的点数：$\sum _{i=1}^l{n}_i$$\sum \limits^l_{i=1} n_i$；边数：$\sum _{1\le i<j<\le l}{n}_i{n}_j$$\sum \limits_{1\le i < j < \le l} n_in_j$ （考过填空）

6. 设 $G$$G$ 是 $n$$n$ 阶简单图，且不含完全子图 $K_3$$K_3$，则其边数一定不会超过 $\lfloor n^2/4\rfloor$$\left \lfloor n^2/4 \right \rfloor$

考点：Turán 定理

定理 18 (Turán)：若 $G$$G$ 是 $n$$n$ 阶简单图，并且不包含 $K_{l+1}$$K_{l+1}$，则边数 $m(G)\le m(T_{l,n})$$m(G) \le m(T_{l,n})$。此外，仅当 $G\cong T_{l,n}$$G \cong T_{l,n}$ 时，$m(G)=m(T_{l,n})$$m(G)=m(T_{l,n})$

✨ 计算公式： $K_{l+1}\notin G$$K_{l+1} \notin G$，则 $m(T_{l,n})=C_l^2(n/l{)}^2$$m(T_{l,n}) = C^2_l (n/l)^2$

• 例： $n$$n$ 阶简单图 $G$$G$，$K_3\notin G$$K_3 \notin G$，则 $G$$G$ 最多有 $\lfloor n^2/4\rfloor$$\left \lfloor n^2/4 \right \rfloor$ 条边 $\Rightarrow m(G)\le m(T_{2,n})=C_2^2(n/2{)}^2=(n/2{)}^2$$\Rightarrow m(G) \le m(T_{2,n}) = C^2_2(n/2)^2 = (n/2)^2$
• 例： 9 阶简单图 $G$$G$，$K_4\notin G$$K_4 \notin G$，则 $G$$G$ 最多有 27 条边 $\Rightarrow m(G)\le m(T_{3,9})=C_3^2(9/3{)}^2=3\times (9/3{)}^2=27$$\Rightarrow m(G) \le m(T_{3,9}) = C^2_3(9/3)^2 = 3 \times (9/3)^2 = 27$

7. 设 $n$$n$ 阶图 $G$$G$ 是具有 $k$$k$ 个分支的森林，则其边数为 $n-k$$n - k$

树的边数 = 顶点数 - 1

森林的边数 = 顶点数 - 连通分支数

8. 一棵树有 $n_i$$n_i$ 个度为 $i$$i$ 的结点，$i=2,3,\cdots ,k$$i=2,3,\cdots,k$，则它有 $\sum _{i=2}^k{n}_i(i-2)+2$$\sum\limits^k_{i=2}n_i(i-2)+2$ 个度数为 $1$$1$ 的顶点

考点：握手定理 + 树的性质（边数 = 顶点数 - 1）

$m=n-1$$m = n - 1$，其中 $n=\sum _{i=1}^k{n}_i$$n = \sum\limits_{i=1}^k n_i$

由握手定理：$2m=d(T)=\sum _{i=1}^k(i\times n_i)$$2m=d(T)=\sum\limits_{i=1}^k (i \times n_i)$

故：$2(\sum _{i=1}^k{n}_i-1)=\sum _{i=1}^k(i\times n_i)$$2(\sum\limits_{i=1}^k n_i - 1) = \sum\limits_{i=1}^k (i \times n_i)$

整理得：$n_1=2+(3-2)n_3+(4-2)n_4+\cdots +(k-2)n_k=\sum _{i=2}^k{n}_i(i-2)+2$$n_1=2+(3-2)n_3+(4-2)n_4+\cdots+(k-2)n_k=\sum\limits^k_{i=2}n_i(i-2)+2$

9. 完全图 $K_5$$K_5$ 的生成树的个数为 $5^{5-2}=125$$5^{5-2}=125$

定理 27：$\tau (K_n)=n^{n-2}$$\tau(K_n)=n^{n-2}$

二、不定项选择题

1. 关于图的度序列，下列命题正确的是（ABCD）

• A. 同构的两个图的度序列相同
• B. 非负整数序列 $(d_1,d_2,\cdots ,d_n)$$(d_1,d_2,\cdots,d_n)$ 是图的度序列当且仅当 $d_1+d_2+\cdots +d_n$$d_1+d_2+\cdots+d_n$ 是偶数
• C. 如果正整数序列 $(d_1,d_2,\cdots ,d_n)$$(d_1,d_2,\cdots,d_n)$是一棵树的度序列且 $n\ge 2$$n \ge 2$，那么序列中至少有两个 $1$$1$
• D. 正整数序列 $(d_1,d_2,\cdots ,d_n)$$(d_1,d_2,\cdots,d_n)$ 是非平凡树的度序列当且仅当 $d_1+d_2+\cdots +d_n=2(n-1)$$d_1+d_2+\cdots+d_n = 2(n-1)$
• E. 若图 $G$$G$ 的顶点度数之和大于等于图 $H$$H$ 的顶点度数之和，则图 $G$$G$ 度优于图 $H$$H$ ❌
• F. 如果非负整数序列 $(d_1,d_2,\cdots ,d_n)$$(d_1,d_2,\cdots,d_n)$ 是简单图的度序列，那么在同构意义下只能确定一个图 ❌

考点：度序列 && 图序列

关系：简单图的度序列简称图序列

注意：判断非负整数序列是否为简单图的度序列暂无好的方法，只有等价转换的方法

A 显然正确（已经默认递增或递减排列）

B 正确：定理 3：非负整数组 $(d_1,d_2,\cdots ,d_n)$$(d_1,d_2,\cdots ,d_n)$ 是图的度序列的充分必要条件是：$\sum d_i$$\sum d_i$ 为偶数

C 正确： 定理 20：每棵非平凡树至少有两片树叶

D 正确：存在一棵非平凡树，以该序列为度序列的充要条件 $d_1+d_2+\cdots +d_n=2(n-1)=2m\Rightarrow$$d_1+d_2+\cdots+d_n = 2(n-1) = 2m \Rightarrow$ 握手定理

E 错误：先有度弱或度优，才有度数之和小于或大于；反过来不成立

F 错误：不止确定一个图

2. 对于序列 $(7,5,4,3,3,2)$$(7,5,4,3,3,2)$，下列说法正确的是（BD）

• A. 可能是简单图的度序列 ❌
• B. 一定不是简单图的度序列
• C. 只能是简单图的度序列 ❌
• D. 只能是非简单图的度序列
• E. 不是任意图的度序列 ❌

考点：度序列 && 图序列

对于简单图，顶点的最大度 $\le$$\le$ 顶点数 - 1

A 错 B 对 C 错：对于该题，长度为 6，说明有 6 个点，同时最大度为 7，显然不是简单图！！

D 对 E 错：定理 3：非负整数组 $(d_1,d_2,\cdots ,d_n)$$(d_1,d_2,\cdots ,d_n)$ 是图的度序列的充分必要条件是：$\sum d_i$$\sum d_i$ 为偶数

3. 下列说法错误的是（ACE）

• A. 若一个图中存在闭途径，则一定存在圈 ❌
• B. 偶图中不存在奇圈
• C. 若图 $G$$G$ 不含三角形，则 $G$$G$ 为偶图 ❌
• D. 图的顶点之间的连通关系一定是等价关系
• E. 存在每个顶点的度数互不相同的非平凡简单图 ❌

A 错误： 闭途径（$u\to v\to u$$u \rightarrow v \rightarrow u$），但不存在圈

B 正确：定理 9：一个图是偶图当且仅当它不包含奇圈

C 错误：可能存在长度不为 3 的奇圈，如 5，7 等等

D 正确：即便在有向图中，也存在弱连通

E 错误：定理 5：一个简单图 $G$$G$ 的 $n$$n$ 个点的度不能互不相同

4. 关于简单图 $G$$G$ 的邻接矩阵 $A$$A$，下列说法错误的是（C）

• A. 矩阵 $A$$A$ 的行和等于该行对应顶点的度数
• B. 矩阵 $A$$A$ 的所有元素之和等于该图边数的 $2$$2$ 倍
• C. 矩阵 $A$$A$ 的所有特征值之和等于该图边数的 $2$$2$ 倍 ❌
• D. 矩阵 $A$$A$ 的所有特征值的平方和等于该图边数的 $2$$2$ 倍
• E. 矩阵 $A^2$$A^2$ 的主对角线的元素之和等于该图边数的 $2$$2$ 倍
• F. 若 $G$$G$ 是非连通图，则 $A$$A$ 相似于某个准对角矩阵

考点：简单图邻接矩阵的性质

A 正确：矩阵 $A$$A$ 的「行和」或「列和」等于该「行」或「列」对应顶点的度数

B 正确：所有元素之和等于度数之和，根据握手定理判断正确

C 错误：矩阵的所有特征值之和等于矩阵的迹；矩阵的迹又是矩阵主对角线上的元素之和；对于简单图，邻接矩阵主对角线元素均为 0

D 正确：所有特征值的平方和等于 $A^2$$A^2$ 的所有特征值之和；$A^2$$A^2$ 的迹就是主对角线之和，也就是图的所有度数之和，就等于边数的两倍

E 显然正确

F 正确：无法解释，因为不懂！！！😭😭😭

5. 图 $G=(n,m)$$G=(n,m)$ 一定是树的是（BDE）

• A. 连通图 ❌
• B. 无回路但任意添加一条边后有回路的图
• C. 每对顶点间都有路的图 ❌
• D. 连通且 $m=n-1$$m=n-1$
• E. 无圈且 $m=n-1$$m=n-1$

考点：树的基本性质

A 错误：树是连通的无圈图

B 正确：回路是边不重圈的并；无回路肯定无圈，加一条边有回路，肯定就有圈

C 错误：每对顶点间存在唯一的一条路

D E 显然正确

三、解答题

1. 设无向图 $G$$G$ 有 $10$$10$ 条边，$3$$3$ 度与 $4$$4$ 度顶点各 $2$$2$ 个，其余顶点度数均小于 $3$$3$，问 $G$$G$ 中至少有几个顶点？在顶点数最少的情况下，写出 $G$$G$ 的度序列，该度序列是一个图序列吗？

考点：握手定理 + 图序列

解：由于求顶点数量最少，故假设 0 度顶点为 0 个，1 度顶点为 0 个，同时设 2 度顶点有 $d_2$$d_2$ 个

根据握手定理得：$10\times 2=2\times d_2+2\times 3+2\times 4$$10 \times 2 = 2 \times d_2 + 2 \times 3 + 2 \times 4$；解得：$d_2=3$$d_2 = 3$

所以 $G$$G$ 中至少有 7 个顶点；图 $G$$G$ 的度序列为 $(4,4,3,3,2,2,2)$$(4,4,3,3,2,2,2)$

根据 Havel-Hakimi 定理，可得下面推导过程：

${\pi }_1=(3,2,2,1,2,2)\Rightarrow {\pi }_1=(3,2,2,2,2,1)$$\pi_1 = (3,2,2,1,2,2) \Rightarrow \pi_1 = (3,2,2,2,2,1)$

${\pi }_2=(1,1,1,2,1)\Rightarrow {\pi }_2=(2,1,1,1,1)$$\pi_2 = (1,1,1,2,1) \Rightarrow \pi_2 = (2,1,1,1,1)$

${\pi }_3=(0,0,1,1)$$\pi_3 = (0,0,1,1)$

显然 ${\pi }_3$$\pi_3$ 是可图的，所以 $(4,4,3,3,2,2,2)$$(4,4,3,3,2,2,2)$ 是可图的

2. 证明整数序列 $(6,3,4,2,2,5,2)$$(6,3,4,2,2,5,2)$ 是简单图的度序列，并构造一个对应的简单图。

考点：图序列

注意：利用等价转换的方法，前提需要对度序列排序（递减）

证明：根据 Havel-Hakimi 定理，首先排序 $\pi =(6,5,4,3,2,2,2)$$\pi = (6,5,4,3,2,2,2)$

${\pi }_1=(4,3,2,1,1,1)\to {\pi }_2=(2,1,0,0,1)$$\pi_1 = (4,3,2,1,1,1) \rightarrow \pi_2 = (2,1,0,0,1)$

显然 ${\pi }_2$$\pi_2$ 是可图的，因此 $(6,3,4,2,2,5,2)$$(6,3,4,2,2,5,2)$ 是可图的

3. 设 $G$$G$ 与其补图的边数分别为 $m_1$$m_1$ 和 $m_2$$m_2$，求 $G$$G$ 的阶数。

解：设图 $H=G\bigcup \bar{G}$$H = G \bigcup \overline G$，图 $G$$G$ 的阶数为 $n$$n$

显然图 $H$$H$ 为完全图 $K_n$$K_n$

根据握手定理得：$n(n-1)=2(m_1+m_2)$$n(n-1)=2(m_1+m_2)$

解得：$n=\frac{1\pm \sqrt{1+8(m_1+m_2)}}{2}$$n=\frac{1 \pm \sqrt{1+8(m_1+m_2)} }{2}$ ，其中正整数解即为所求

4. 设 $G$$G$ 为 $n$$n$ 阶简单图，$n>2$$n>2$ 且 $n$$n$ 为奇数，$G$$G$ 与其补图中度数为奇数的顶点个数是否相等？并给出理由。

解：由补图定义知，任意点 $v$$v$ 在图 $G$$G$ 及其补图 $\bar{G}$$\overline G$ 中的度数之和为 $n-1$$n-1$，即：$d_G(v)+d_{\bar{G}}(v)=n-1$$d_G(v)+d_{\overline G}(v)=n-1$

因此，若 $G$$G$ 中有 $b_i$$b_i$ 个度为奇数的顶点，其度数为 $d_i$$d_i$，则这 $b_i$$b_i$ 个顶点在 $\bar{G}$$\overline G$ 中的度数为 $n-1-d_i$$n-1-d_i$

因为 $n$$n$ 为奇数，故 $n-1$$n-1$ 为偶数，所以 $n-1-d_i$$n-1-d_i$ 为奇数

综上所述，$G$$G$ 与其补图中度数为奇数的顶点个数相等

5. 证明：任何一个人群中至少有两个人认识的朋友数相同。

注意：此类题目考试中经常出现

证明：以人为顶点，如果两个人相识，对应的顶点之间连一条边，得到的图记为 $G$$G$

显然图 $G$$G$ 是简单图

当一个人的朋友数等于他在图中对应顶点的度数

因为简单图中一定存在度数相等的顶点，所以在任何一个人群中至少有两个人认识的朋友数相同

6. 证明：若 $k$$k$ 正则二部图具有二分类 $V=V_1\cup V_2$$V=V_1\cup V_2$，则 $|V_1|=|V_2|$$|V_1|=|V_2|$。

证明：对于二部图来说，因为边是建立在顶点集的二部划分之间的，所以边数既等于 $V_1$$V_1$ 中顶点的度数之和，也等于 $V_2$$V_2$ 中顶点的度数之和

故有：$k\times |V_1|=m=k\times |V_2|$$k \times |V_1| = m = k \times |V_2|$

所以：$|V_1|=|V_2|$$|V_1|=|V_2|$

注意：梳理 $k$$k$ 正则二部图结论

7. 证明：若图 $G$$G$ 的直径大于 $3$$3$，则图 $G$$G$ 的补图的直径小于 $3$$3$

摆烂吧！！！

不会！！！！

考试难度远远低于本题。。。

所以 哈哈哈哈哈

放弃吧！！！！！