离散数学小测(3)

作者：MURENzzz

摘要

为学弟学妹们留点排版美观的资料（尽管也是朴素的 $\LaTeX$ ）顺便记录一下，毕竟我在本学院的时光也所剩无几了（）最后燃尽一下。

不过苯人是个菜鸡难免会有疏漏和错误，欢迎指正以及发明更好的解法。

不过感觉这份题课上20来分钟想都写清楚还是挺难的…

测试3题目

(1) 画出 5 阶 4 条边的所有非同构的无向简单图
(2) 画出 4 阶 2 条边的所有非同构的有向简单图
设 $G = \langle V, E \rangle$ 是无向连通图， $G$ 中至少有 3 个顶点，证明 $G$ 中存在 2 个顶点，将它们删除后图仍然是连通的。
证明在任何有向完全图中，所有顶点入度的平方之和等于所有顶点出度的平方之和。

（说明：有向完全图是指以无向完全图为底图的有向图）
若 $G$ 为简单图，且 $m > \binom{n-1}{2}$ ，则 $G$ 是连通的。
其中 $m,n$ 分别为该图的边数和顶点数。
假设 $T$ 是非平凡的无向树， $T$ 中度数最大的顶点有 2 个，并且它们的度数 $k$ 都 $\geq 2$ 。
证明： $T$ 中至少有 $2k - 2$ 片叶。
设 $G$ 有 11 个或更多顶点，证明 $G$ 或 $G$ 的补图 $\bar{G}$ 是非平面图。

个人解析

本来想写得详细严谨些锻炼一下，不过为了可读性（懒）… 一些是证明摘要。

1.

按最大度数降序 / 升序枚举即可，记得去除同构的。

2.

题目的要求意味着两个点必须都不是割点，直接给出构造：最长路 $p$ 的两个端点 $u,v$ 。

证明：

若 $u$ 是割点，与其相邻的两条边为 $e_1, e_2$ ，不妨设 $e_2$ 不在这条最长路里（因为 $u$ 是端点），且 $e_2$ 所连的另一个点 $u'$ 也不在最长路里（否则存在含 $u$ 的环，则 $u$ 不是割点），那么存在一条更长的路： $p + e_2$ ，矛盾。

$v$ 同理。

3.

我的思路是分析一个操作，注意到一个有向完全图中任意两个点确定的边的方向可以随意变换。我们称反转一条有向边的方向为操作 $M$ ，如果结论成立，则对任意两个点唯一确定的边进行操作 $M$ 都应保持结论。

命题：任意两个点操作 $M$ 后两个点的出度平方和 - 入度平方和不变（而其他点的入度出度自然不变），说明整个图的出度平方和 - 入度平方和不变。，只需证明此命题再给出一个令出度平方和-入度平方和为0的构造即可（方便的话）事实上这个构造在这里可以通过对任意图对换出度入度的对称性来省去。

因此只需证明这个命题。

证明如下：

用 $(m, n)$ 表示一个点的出度为 $m$ ，入度为 $n$ 。

设点 $v_A, v_B$ （不考虑两者之间的边）的度数为 $(a, n-2-a), (b, n-2-b)$

加上之间的边后变为：

$(a+1, n-2-a), (b, n-2-b+1)$ 或
$(a, n-2-a+1), (b+1, n-2-b)$

$\begin{aligned} \sum_{v_A, v_B} \text{出度}^2 - \text{入度}^2 &= (a+1)^2 + b^2 - (n-2-a)^2 - (n-2-b+1)^2 \\ &= -(n-2)^2 - (n-1)^2 + 2(n-1)(a+b) \\ &= (b+1)^2 + a^2 - (n-2-b)^2 - (n-2-a+1)^2 \end{aligned}$

4.

这题思路比较简单，不过严谨的证明需要注意一些细节。

注意到 $\binom{n-1}{2}$ 等于 $K_{n-1}$ 的边数。

容易想到一种极限情况是 $K_{n-1}$ 完全图加一个孤立点,这时多一个边不得不与孤立点连通.但仍需证明这是极限情况

有义务说明为什么其他情况的边数一定小于这个,比如两个边数差不多的连通分支,不过连通分支数是2是极限情况是显然的。(有没有直观且严谨的理解呢？我没太想到)

证明：

设有 $\omega(G)$ 个连通分支（ $\omega(G) > 1$ ），我们要证其边数 $\leq \binom{n-1}{2}$ 。

设某一连通分支 $\omega_p$ 包含 $k \leq n - 1$ 个顶点，其余分支共含 $n - k$ 个顶点：

$\begin{aligned} &\sum_{v_{i} \in w_{p}} d(v_{i}) + \sum_{v_{j} \notin \omega_{p}} d(v_{j}) \leq \binom{k}{2}+\binom{n-k}{2} \\ &k=1\text{或}n-1\text{时},\text{显然有} \sum_{v_{i} \in w_{p}} d(v_{i}) + \sum_{v_{j} \notin \omega_{p}} d(v_{j}) \leq \binom{n-1}{2} \\ &\text{k为其余时} \\ &\text{比较 } \binom{k}{2} + \binom{n-k}{2} \text{ 与 } \binom{n-1}{2} \\ &\text{经整理差为：} (k - 1)[k - (n - 1)] < 0 \Rightarrow \text{边数小于等于 } \binom{n-1}{2} \end{aligned}$

证毕

5.

这道题和我不太来电，水一下（\；如果有好的证明我再改 QAQ）

证明两个非叶子节点至少产生其「度数 - 1」个私有叶子（不朝向另一个节点的分支里的叶子）。

证明：

移除点 $u$ ，则树会变为 $k$ 个连通分支，必然有某个分支中包含 $v$ 。

其余 $k - 1$ 个子树至少产生 $k - 1$ 个叶子，记为集合 $A$ 。同理， $v$ 对应 $B$ 。

若 $A \cap B \neq \emptyset$ ，则存在 $l \in A \cap B$ ，根据定义， $u \to l$ 的路径不含 $v$ ， $v \to l$ 的路径不含 $u$ ， $u \leftrightarrow v$ 有路径 —— 三者形成环，矛盾。

故 $A \cap B = \emptyset$ ，至少有 $2k - 2$ 个叶子。

6.

判断图是否非平面，可用 Kuratowski 定理（含有 $K_{3,3}$ 或 $K_5$ 的同胚子图）但不好用。

另一个思路便是用一些可平面的必要条件，(逆否命题),不满足这些必要条件当然就是非平面的。

这里11阶图或其补图是非平面的，大概率是因为11实在是太大了。

能够联想到书上利用欧拉定理导出的必要条件：

若 $G$ 是简单平面图， $n \geq 3$ ，则 $m \leq 3n - 6$

考虑 $K_{11}, |E(K_{11})| = 55$

由抽屉原理， $G$ 或 $\bar{G}$ 至少有一个边数 $\geq 28$

$28 > 3 \times 11 - 6 = 27$

证毕。