离散数学题目

图论第七章题目

7.1 图的基本概念，顶点集，边集，图的阶，零图

判断题 ：存在1阶零图。 ( )

答案：正确

解析：在图 $G$ 中，若 $E(G)=\emptyset$ ，则称 $G$ 为零图，此时，又若 $\mid V(G)\mid=n$ ，则称 $G$ 为 $n$ 阶零图，记为 $N_n$ ，特别是称 $N_1$ 为平凡图。

7.1 图的基本概念，顶点集，边集，图的阶，零图

判断题 ：存在1阶空图。 ( )

答案：错误

解析：顶点集为空集的图为空图。

7.1 图的基本概念，领域，闭邻域

选择题：

$V_2$的闭邻域是：( )

$A:V_3、V_4、V_0 $ $B:V_3、V_4、V_0、V_2 $

答案：B

解析：闭邻域的定义

7.1 图的基本概念，度数，最大最小度

判断题 ：在有向完全图中，所有节点入度的平方和等于所有节点出度的平方和。（）

答案：正确

解析：设有向完全图具有$n$个节点，对于任意结点 $V_i$ 均有 $\mathrm{deg}^{+}\left(v_{i}\right)+\mathrm{deg}^{-}\left(v_{i}\right)=n-1$
又因边数 $=\frac{1}{2} n(n-1)=\sum_{i=1}^{n} d e g^{+}\left(v_{i}\right)=\sum_{i=1}^{n} \operatorname{deg}^{-}\left(v_{i}\right)$，故而

$\begin{aligned} \sum_{i=1}^{n}\left[\mathrm{deg}^{-}\left(v_{i}\right)\right]^{2}=& \sum_{i=1}^{n}\left[(n-1)-\mathrm{deg}^{+}\left(v_{i}\right)\right]^{2} \\ =& \sum_{i=1}^{n}(n-1)^{2}-\sum_{i=1}^{n} 2(n-1) \mathrm{deg}^{+}\left(v_{i}\right) +\sum_{i=1}^{n}\left[\mathrm{deg}^{+}\left(v_{i}\right)\right]^{2} \\ =& n(n-1)-2(n-1) \sum_{i=1}^{n} \mathrm{deg}^{+}\left(v_{i}\right) +\sum_{i=1}^{n}\left[\mathrm{deg}^{+}\left(v_{i}\right)\right]^{2} \\=& n(n-1)-2(n-1) \cdot \frac{1}{2} n(n-1) +\sum_{i=1}^{n}\left[\mathrm{deg}^{+}\left(v_{i}\right)\right]^{2} \\=& \sum_{i=1}^{n}\left[\operatorname{deg}^{+}\left(v_{i}\right)\right]^{2} \end{aligned}$

7.1 图的基本概念，握手定理

填空题 ：已知图G有11条边, 3个4度顶点, 其余顶点的度数均不⼤于2, G⾄少有___个顶点。

答案：8

解析：由握手定理$4\times3+2\times (X-3)\geq2\times11$，得 $X\geq8$

7.1 图的基本概念，度数列，可简单图化

判断题 ：度数列$(6,6,5,4,3,3,1)$可简单图化。（）

答案：错误

解析： $6+6+5+4+3+3+1=28=0(mod 2).$

$d_1=6=n-1,满⾜n-1≥d_1.$ $r=1,2时,$ $d_1=6≤1(1-1)+min\{1,6\}+min\{1,5\}+ …=6,$ $d_1+d_2=12>2(2-1)+min\{2,5\}+…=11,$

7.1 图的基本概念，子图，补图，自补图

填空题 ：若G为⾃补图,则G的阶n应满⾜___

答案： $n=4k(k \in N)$ 或 $n=4k+1(k \in N)$

解析：G为自补图，易证G是简单图，故有 $|E'|=|E|={n\times (n-1)\over4}$ ，因此$n=4k(k\in N)$ 或 $n=4k+1(k\in N)$

7.1 图的基本概念，边的收缩，图族

判断题 ：$Petersen$图通过边的收缩可以成为$K_5$

答案：正确

解析：边收缩的定义

7.2 通路和回路，周长和围长

填空题 ：

该图的周长是，围长是。

答案：5 3

解析：周长和围长的定义

7.2 通路和回路，圈，完全图

填空题 ：$K_n(n≥3)$中有___种⾮同构的圈。

答案：n-2

解析：⻓度相同的圈都是同构的，因⽽只有⻓度不同的圈才是⾮同构的，

7.2 通路和回路，扩大路径法，圈，最大公约数

判断题 ：G是简单无向图，$delta(G) \geq 3$，G中各圈长度的最大公约数为1。（）

答案：错误，为1或2

解析：

构造一个 “极大路径” $\Gamma=v_{0}, v_{1}, \ldots, v_{l}$ 。

由 $\Gamma$ 是极大路径知, $v_{0}$ 的所有邻接点都在 $\Gamma$ 上。
由 $\delta(G) \geq 3$ 可知, 除 $v_{1}$ 外, 至少还有两个顶点 $v_{i}, v_{j}(2 \leq i<j \leq l)$ 与 $v_{0}$ 相邻。
于是, $v_{0}, v_{1}, \ldots, v_{i}, v_{0}$ 是一个长度为 $i+1$ 的圈, $v_{0}, v_{1}, \ldots, v_{j}, v_{0}$ 是一个长度为 $j+1$ 的圈, $v_{0}, v_{i}, \ldots, v_{j}, v_{0}$ 是一个长度为 $j-i+2$ 的圈。
令 $d$ 为 $G$ 中各圈长度的最大公约数。

则有 $d|i+1 、 d| j+1$ 和 $d \mid j-i+2$, 于是有 $d \mid(i+$ $1)+(j-i+2)-(j+1)=2$ ( $d$ 的倍数的和、差仍是 $d$ 的倍数)。
由 $d \mid$ 得到 $d \leq 2$ (因子总小于它的倍数), 进而由 $d$ 是正整数(公因子的定义)得 $d$ 等于1或2。

7.3 无向图的连通性，二部图

填空题 ：⼀个⽆向图G＝是⼆部图当且仅当G中___。

答案：⽆奇圈.

解析：必要性。
若 $G$ 中无回路, 结论显然成立。
若 $G$ 中有回路, 只需证明 $G$ 中无奇圈。
设 $C$ 为 $G$ 中任意一圈, 令 $C=v_{i_{1}} v_{i_{2}} \ldots v_{i_{s}} v_{i_{t}}$, 易知 $t \geq 2$.
不妨设 $v_{i_{1}} \in V_{1}$, 则必有 $v_{i_{t}} \in V-V_{1}=V_{2}$,而 $t$ 必为偶数, 于是 $C$ 为偶圈,
由 $C$ 的任意性可知结论成立。

充分性。
不妨设 $G$ 为连通图, 否则可对每个连通分支进行讨论. 设 $v_{0}$ 为 $G$ 中任意一个顶点, 令

$V_{1}=\left\{v \mid v \in V(G) \wedge d\left(v_{0}, v\right) \text { 为偶数 }\right\}$ $V_{2}=\left\{v \mid v \in V(G) \wedge d\left(v_{0}, v\right) \text { 为奇数 }\right\}$

易知, $V_{1} \neq \varnothing, V_{2} \neq \varnothing, V_{1} \cap V_{2}=\varnothing, V_{1} \cup V_{2}=V(G)$ 。
下面证明 $V_{1}$ |中任意两顶点不相邻, $V_{2}$ 中任意两点不相邻。若存在 $v_{i}, v_{j} \in V_{1}$ 相邻, 令 $\left(v_{i}, v_{j}\right)=e$,
设 $v_{0}$ 到 $v_{i}, v_{j}$ 的短线程分别为 $\Gamma_{i}, \Gamma_{j}$,则它们的长度 $d\left(v_{0}, v_{i}\right), d\left(v_{0}, v_{j}\right)$ 都是偶数,

故 $\Gamma_{i} \cup \Gamma_{j} \cup e$ 构成奇圈, 这与已知条件矛盾。