Discrete Math Note

Mysteries

空图指的是荒漠
$(\varnothing,\varnothing)$ 不是图
单点不是路径(path)
"邻接矩阵不能表示重边"
当说一条路径的时候,简单=边不同,初级=边不同+点不同(???)由于这条过于神秘,所以后面写笔记的时候常常不管这件事(当我说简单的时候指的边也不同).

I'm pig

平均编码长度是按频率加权的.

20260306

对任意六个点的图 $G$ : $G$ 或 $\overline{G}$ 至少有一个包含 $K_3$ 子图.

先转化成完全图红蓝染色.

随便拿一个点,一定有至少3条同色,拿出3条中对应的3个点,若它们之中的某条边颜色与这3条相同则完事,否则它们之中的3条边子集构成 $K_3$ ,完成.

20260310

若简单图中每个点度数都大于 $3$ ,则图中一定存在有弦的回路

称一个简单回路中连接两个不相邻节点的边是弦

它给的证法是考虑拿一个极长简单路,那么你端点上的邻接点必须都在这条路上,于是离着近的那条就会是离着远的那条成的环的弦.

20260320

把哈密顿这一块的内容写一下:

若 $\forall u,v,d(u)+d(v)\ge n-1$ ,则存在哈密顿路

考虑一条极长简单路 $v_1\ldots v_k$ ,那么对 $v_1,v_k$ 来说必有他们的邻居全都在链上.

此时,如果 $k=n$ 就结束了,否则 $k<n$ .

否则尝试证明有一条包含这个路的回路:如果 $(v_1,v_k)$ 存在显然成立,否则,由 $d(v_1)+d(v_k)\ge n$ 知存在 $1<i<k-1$ 使得 $(v_1,v_{i+1})\in E(G),(v_i,v_k)\in E(G)$ .(因为所有的 $i$ 只有 $k-3\le n-4$ 个,但 $d(v_1)+d(v_k)-2\ge n-3$ ,所以一定有交)

另外能看出显然是连通图:对任意两个点如果他俩不直接相连一定有公共邻居.

所以这个回路与至少某个这个回路外的点相连,此时断掉回路上的一条边你就得到一个更长的简单路,有限次归纳即得到哈密顿路.

若 $\forall u,v,d(u)+d(v)\ge n$ ,则存在哈密顿回路

前面的是在 $k<n$ 的时候证明了一定有回路,现在把那个过程抄一遍用新条件就成了 $k\le n$ 的时候极长简单路一定有回路.于是就证完了.

若 $d(u)+d(v)\ge n$ ,则加入边 $(u,v)$ 不影响哈密顿回路存在性

假设加了这条边后存在一个经过这个边的哈密顿回路,那你把它删了就有哈密顿路,而上面的结论告诉我们 $d(u)+d(v)\ge n$ 时以他俩为单点的简单图一定有哈密顿回路.

图的闭合图唯一

几乎是显然的:你加一条边不会导致你不能加本来加能加的边.

所以过程你就假设两个加边顺序中存在某个一个有另一个没有的边,然后说明他可以被加进去.

对图 $G$ ,设 $p(V)$ 表示 $V$ 这个导出子图中的连通支个数,则对任意非空子集 $V_1$ :

若 $G$ 有哈密顿回路,则 $p(G-V)\le |V|$
若 $G$ 有哈密顿道路,则 $p(G-V)\le |V|+1$

假设你有回路,那么删去一个点集回路会变成 $|V|$ 段,那么显然 $p(G-V)\le |V|$ .

同理道路删去一个点集会变成 $|V|-1$ 段,也显然.

有割点一定不存在哈密顿回路

显然.

Midterm Graph Review

做一做往年题

T1

判断

hamilton graph?

是不是哈密顿图

用删掉若干个点后剩下的连通块数.第一个删掉 $a,b,c,d,e$ ,第二个考虑最外面三个点都只有二度,所以他们的边都在哈密顿回路上(如果是),然后你发现已经连出了个环就爆炸了.

T2

这个图里面有没有哈密顿路/回路

hamilton path?

先考虑回路.注意每个点度数都是 $3$ .所以你要找一个完全匹配,使得干掉这些边后度数都是 $2$ .

好吧这没有用.你发现这个图有完美匹配,结果弄出了两个环.

不过这时你随便找一找倒是容易把环拆开弄出哈密顿路.

好吧我没招了.不过其实枚举匹配的话只有三种情况.考试最后有时间就枚举一下吧...可以证明没有回路.

T3

记得完全二叉树是堆的那个结构.

T4

已知引理（教材例 2.1.3）：设 $C$ 是简单图 $G$ 中含结点数大于 3 的一个初级回路。如果结点 $v_i, v_j$ 在 $C$ 中不相邻，而边 $(v_i, v_j) \in E(G)$ ，则称 $(v_i, v_j)$ 是 $C$ 的一条弦。若对每一个 $v_k \in V(G)$ 都有 $d(v_k) \ge 3$ ，则 $G$ 中含有带弦的回路。

证明：在简单图中，若 $n \ge 4$ 且 $m \ge 2n - 3$ ，则 $G$ 中含有带弦的回路。

注意到如果存在一度点,直接删了仍然满足条件.如果存在二度点,把这个点删掉且直接把它连接的两个点连起来仍然满足条件.且删完了的图上有弦原来一定有弦.

太棒了你现在把一度点和二度点一直删,此时如果删完了 $n\ge 4$ 就引理结束.

如果 $n=4$ 时不能删了还剩下一/二度点,那么 $m\ge 5$ .此时如果有一度点你删了的话三元环 $4$ 条边一定有弦,如果二度点缩掉也是 $4$ 条边 $3$ 个点.就结束.

T5

回路长度都是偶数推二分图.

尝试证明可以进行二染色.因为长度都是偶数所以不会有矛盾(考虑一个没染色的点,不可能连到同时两种颜色的已经染色的点)

T6

设 $G$ 是不存在三角形的简单图，节点和边分别为 $n，m$ 证明 $m\le \dfrac{n^2}4$ .

又犯唐了.

限制在于拿出一条边 $(u,v)$ ,删掉所有和它相连的边和这两个点,则肯定没有三角形,有 $m-1-k\le \dfrac{(n-2)^2}4$ .

然后考虑 $k$ 有多大(也就是和这个边相邻的边),因为这里有一条边,所以 $u,v$ 的邻居不交,于是就是 $k\le n-2$ ,带进去就弄完了.

T7

无向完全图定向后 $\sum d_+^2(u)=\sum d_-^2(u)$

\begin{gathered} \sum d_-^2(u) \\ =\sum (n-1-d_+(u))^2 \\ =n(n-1)^2-2(n-1)\sum d_+(u)+\sum d_+^2(u) \end{gathered}

然后 $2\sum d_+(u)=n(n-1)$ 就完事了呗.

证明没有哈密顿回路

pasted-image-1

一个是仍然可以用匹配的方法去枚举.

一个是证明3正则图存在哈密顿回路则可以3-边染色.但感觉证明这个不能3-边染色也要枚举.

一个是考虑哈密顿回路确定后你的弦的跨度是多大.这个图的一个性质是不存在长度小于 $5$ 的环.于是你的步长就必须是 $4$ (跨过 $4$ 条边).那么设你的哈密顿回路上第 $i$ 个节点为 $v_1$ .则 $v_1$ 连到 $v_5$ , $v_2$ 不能连 $v_6$ (否则出现四元环)只能连 $v_8$ ,于是 $v_3$ 连谁都有四元环.