离散数学作业 20251030 第八章

8.3

证明在任意一个竞赛图中，所有顶点的入度平方和等于所有顶点出度平方和。

证明：

对于一个 $n$ 阶竞赛图，对于每一个顶点 $v_i$ ，有 $deg^-(v_i)=n-1-deg^+(v_i)$.

两边同时平方，得 $(deg^-(v_i))^2=(n-1)^2+(deg^+(v_i))^2-2(n-1)deg^+(v_i)$.

故有 $\sum_{i=1}^n (deg^-(v_i))^2=\sum_{i=1}^n(n-1)^2+\sum_{i=1}^n(deg^+(v_i))^2-\sum_{i=1}^n2(n-1)deg^+(v_i)$.

下面证明 $\sum_{i=1}^n(n-1)^2=\sum_{i=1}^n2(n-1)deg^+(v_i)<=>\sum_{i=1}^n(n-1)=2\sum_{i=1}^ndeg^+(v_i).(*)$

由于 $n$ 阶竞赛图是 $n$ 阶完全图的定向，对于一个 $n$ 阶完全图 $K_n$ 有 $\sum_{i=1}^n deg(v_i^{'})=n(n-1)$.

对于竞赛图的每条边，有一个顶点贡献一个出度，另一个顶点贡献一个入度。

故 $\sum_{i=1}^n deg(v_i^{'})=\sum_{i=1}^n(deg^-(v_i)+deg^+(v_i))=2\sum_{i=1}^n deg^+{v_i}$.

所以 $(*)$ 式成立，证毕。

8.10

（1）证明 $(4,3,2,2,1)$ 可简单图化.

证明：

$(4,3,2,2,1)$ 可简单图化 $<=>(2,1,1,0)$ 可简单图化 $<=>(0,0,0)$ 可简单图化，证毕.

（2）证明 $(7,6,5,4,3,3,2)$ 和 $(6,6,5,4,3,3,1)$ 不可简单图化.

证明：

$(7,6,5,4,3,3,2)$ 一共 $7$ 个顶点，而最大度数为 $7$ ，说明该顶点连出去的边一定有重边或自环，证毕.

$(6,6,5,4,3,3,1)$ 可简单图化 $<=> (5,4,3,2,2,0)$ 可简单图化，显然度数为 $5$ 的点对剩下四个度数不为 $0$ 的点一定会形成重边或自环，证毕.

（5）利用定理 8.6，判定 $(5,5,3,3,2,2,2)$ 可简单图化.

$(5,5,3,3,2,2,2)$ 可简单图化 $<=>(4,2,2,1,1,2)$ 可简单图化 $(1,1,1,1,0)$ 可简单图化 $<=>(1,1,0,0,0)$ 可简单图化 $<=>(0,0,0,0,0)$ 可简单图化.

8.11

设 $G$ 是简单图，有 $n$ 个顶点，$\delta > \left[ \dfrac{n}{2}\right]-1$. 证明：$G$ 是联通的。

证明：

假设 $G$ 是不连通的。

假设 $v_i,v_j$ 不连通，则由题意有 $deg(v_i)\ge \left[\dfrac{n}{2}\right],deg(v_j)\ge \left[\dfrac{n}{2}\right]$.

则 $deg(v_i)+deg(v_j)\ge n-1$.

去掉 $v_i,v_j$ 两个点后图中还剩 $n-2$ 个点，由抽屉原理知：必存在至少一个点，使得这个点与 $v_i,v_j$ 均存在连边，则 $v_i,v_j$ 连通，矛盾！

所以 $G$ 是连通的。

8.18

设 $G$ 是简单连通图，每个顶点是偶顶点，证明 $\omega(G-v)\le \dfrac{1}{2}d(v)$.

证明：

假设 $\omega(G-v)>\dfrac{1}{2}d(v)$，由抽屉原理，删去 $v$ 后有一个连通分支只和 $v$ 有一条连边，那么这个连通分支是一个只有一个度数为奇数的点，由握手定理，显然不可能。证毕！

8.23

设 G 是二分图，证明 G 的顶点可以适当标号，使得 $M(G)$ 表示为如下形式：

$$M(G) = \begin{pmatrix} 0 & A_{12} \ A_{21} & 0 \end{pmatrix}$$

其中 $A_{21} = A_{12}^T$。

证明：

假设 $G$ 的点集被分为 $S, T$，则 $S,T$ 内任意两个点都没有连边，顶点分别放在左上角和右下角，则这两个矩阵为全零矩阵，由于邻接矩阵是对称矩阵，故证毕。

8.24

证明连通图 $G$ 是欧拉图当且仅当连通图 $G$ 是若干条边不相重的回路之并。

证明：

若 $G$ 是欧拉图，则起可以被一条回路不重不漏地走一遍，必要性成立。

若 $G$ 是若干条边不相重的回路之并，任取一个点作为起点，其任意一条邻接边作为始边。假设走到一个点时，这个点在另若干条回路上，则可以绕着这个回路走一圈回到该点，故可以消掉这一个回路。递归地操作下去则相当于最终仅剩始边所在的回路，走点顺序即为欧拉回路。充分性成立。

8.25

(1) 已知图 $G$ 至少要 $k$ 笔才能画成，删去一边后得到图 $G’$，问 $G’$ 至少需要几笔画成？

解：若 $k=1$，如果有两个奇点，则可能为 $1$ 可能为 $2$，如果没有奇点，则还是 $1$.

若 $k \ne 1$，若删去的边连接两个奇点，则为 $k-1$，若连接一奇一偶，则为 $k$，若连接两偶，则为 $k+1$.

(2) 设连通图 $G$ 具有 $2k$ 个奇顶点，证明 $G$ 中必有 $k$ 条没有公共边的链包含 $G$ 的所有边。

证明：

将这 $2k$ 个奇顶点任意两两配对，得到 $k$ 个顶点对：

$(v_1, v_2), (v_3, v_4), \dots, (v_{2k-1}, v_{2k})$

向图 G 中添加 $k$ 条新边 $e_1, e_2, \dots, e_k$，其中 $e_i = (v_{2i-1}, v_{2i})$.

得到新图 $G^$，它的顶点集与 G 相同，边集 $E(G^) = E(G) \cup {e_1, e_2, \dots, e_k}$，且每个顶点的度数均为偶数，则 $G^*$ 是一个欧拉图，故存在欧拉回路 $C$ 。

在 $C$ 中删去 $e_1,e_2,…e_k$ 则 $C$ 被断成了 $k$ 条不交的链，并且他们覆盖了 $E(G)$。证毕！