基本概念

图

定义 2.1.1

图 $G=(V,E)$, $V$ 是点集, $E$ 是边集.

图的阶数 (order): $|V|$.

图的大小 (size): $|E|$.

空图 (null graph): $|V|=|E|=0$.

完全图 (complete graph): 简单图, 任意两点间有边.

子图 (subgraph): 从原图中删去若干点和若干边 (删除点需删除与其相连的所有边).

补图 (com): 边集对完全图取补集.

团 (clique): 完全的子图.

独立集 (independent set): 两两之间无边.

定理 2.1.2 Ramsey

对任给两个正整数 $r,s$, 那么存在一个正整数 $R(r,s)$, 当简单图 $G$ 的节点数不小于 $R(r,s)$ 时, 这个图至少存在一个大小为 $r$ 的团或者大小为 $s$ 的独立集.

定义 2.1.3 k-partite

k 部图: 可以将点集分成恰 k 个独立集.

定义 2.1.4

染色数 (chromatic number): $\Chi(G)$, 用最少的颜色数给节点染色, 使得任意相邻的点颜色不同.

定义 2.1.5

路径 (path): $(v_1,v_2,\ldots,v_k)$, 存在边 $(v_i,v_{i+1})$, $v_i\neq v_j (i\neq j)$.

环 (cycle): 对于路径 $(v_1,v_2,\ldots,v_k)\ (k\geqslant 3)$, 称 $(v_1,v_2,\ldots,v_k,v_1)$ 为环.

定义 2.1.6

对于一个无自环的图 $G$, $V(G)=\{v_1,v_2,\ldots,v_n\}$, 称 $A\subset \mathbb{N}^{n\times n}$ 为邻接矩阵 (adjacency matrix) 当且仅当 $a_{i,j}=|E'|, E'=\{e_k\in E(G)|e_k={v_i,v_j}\}$.

连接矩阵 $M\subset\{0,1\}^{n\times m}, m=|E(G)|$. $m_{i,j}=1$ 仅当 $v_i$ 是 $e_j$ 的端点.

定义 2.1.7

图同构 (isomorphism): $G\cong H$ 当且仅当存在双射 $f:V(G)\to V(H)$, $uv\in E(G)\Leftrightarrow f(u)f(v)\in E(H)$

命题 2.1.8

对于简单图, 同构关系是一种等价关系.

定义 2.1.9

同构类 (isomorphism class): 等价关系合并.

也称为无标号图 (unlabelled graph).

无标号路径和环记作 $P_n,C_n$.

无标号完全图 (complete graph):$K_n$.

无标号完全二部图 (complete bipartite graph or biclique): $K_{r,s}$ 两部分的节点个数分别为 $r,s$.

定义 2.1.10

Petersen graph: 简单图, 顶点为 $\binom{5}{2}$ 二元对例如 12, 13, 35 等. 两个二元对之间有边当且仅当其顶点两元均不相同.

每个点的度数都是 3.

两个不相连的节点, 恰好有唯一一个公共邻居.

围长 (girth): 最短的环为 5.

Paths, cycles, and trails

图的连通 Connection in graphs

定义 2.1.11

游走/通道 (walk): $(v_0,e_1,v_1,\ldots,e_k,v_k)$, $e_i=\{v_{i-1},v_i\}$.

迹 (trail): 没有重边的游走.

给定端点的游走, 迹, 路径, 记作: $u,v-walk$, $u,v-trail$, $u,v-path$

长度 (length): 边的数量.

闭合的游走/迹: $v_0=v_k$.

当我们不在意闭合的迹的起点时 (仍保留点顺序), 我们也称之为回路 (circuit). $$ {path}\subset{trail}\subset{walk} $$ $$ {cycle}\subset{closed\ trail}\subset{closed\ walk} $$

引理 2.1.12

每一个 u,v-游走中都含有 u,v-路径.

证明

考虑对长度 $l$ 做强数学归纳法.

初始: $l=0$ 只有孤立点, 显然成立.

假设对 $l\leqslant k$ 成立, 下证对 $l=k+1$ 成立.

对于游走 $u,\ldots,v$

若其中没有重复节点, 那么结论成立.

若其中有重复节点 $w$, 那么存在一个 $w,w$ 闭合游走, 长度至少为 $1$, 删除这个闭合游走后剩余长度就小于等于 $k$, 于是根据归纳法成立.

定义 2.1.13

两个顶点连通: 存在一条路径.

图的连通 (connection): 任意两个顶点连通.

连通关系是等价关系.

定义 2.1.14

极大连通子图 (maximal connected subgraph): 连通关系的等价类.

分支 (components): 图的极大连通子图.

非平凡的连通分支 (nontrivial compoment): 至少含有一条边, 即不是孤立点.

命题 2.1.15

$n$ 个点 $k$ 条边的图至少有 $n-k$ 个连通分支.

证明

数学归纳法.

初始: $k=0$, $n$ 个孤立点, 成立.

假设 $k-1$ 成立.

$G$ 是 $n$ 个节点 $k$ 条边的图, 任选 $e\in E(G)$, 设 $G'=G-e$.

$G'$ 中至少有 $n-k+1$ 个连通分支.

由于加一条边至多使连通分支数目减一, 所以 $G$ 至少有 $n-k$ 个连通分支.

推论 2.1.16

$n$ 个点的连通图至少有 $n-1$ 条边.

定义 2.1.17

割边 (cut-edge)/割点 (cut-vertex): 删除该边/点后连通分支数量增加.

定义 2.1.18

诱导子图 (induced subgraph): 通过删除若干顶点得到的子图.

将保留的顶点集为 $T$ 的诱导子图记作 $G[T]$.

定理 2.1.19

一条边是割边的充要条件是它不属于任何一个环.

二部图 Bipartite graph

引理 2.1.20

每个长度为奇数的闭合游走包含一个长度为奇数的环.

定理 2.1.21

一个图是二部图当且仅当其不包含奇环.

欧拉回路 Eulerian circuit

定义 2.1.22

欧拉回路: 一个包含所有边的闭合的迹.

欧拉迹: 一个包含所有边的迹.

欧拉图: 包含欧拉回路的图.

偶图: 所有点的度数都是偶数的图.

注 2.1.23

欧拉图只在意边, 所以增加孤立点仍是欧拉图.

引理 2.1.24

如果图 $G$ 的每个顶点的度数至少为 2, 那么这个图包含环.

证明

考虑极大路径 $x,y-path$, 由于每个点度数至少是 2, 所以 $y$ 存在一条不在路径中的边, 如果这条边的另一个端点在路径中, 那么就找到了一个环. 否则可以找到一个更长的路径, 从而与极大矛盾.

定理 2.1.25

一个图是欧拉图, 当且仅当它含有至多一个非平凡的连通分支且每个点的度数是偶数.

证明

"$\Rightarrow$": 显然.

"$\Leftarrow$": 用数学归纳法. 用引理找到一个环, 删除环上的边后变为若干连通分支, 各自连通分支是子问题存在欧拉回路, 再用一开始找的环将所有欧拉回路拼接.

命题 2.1.26

任意一个偶图都可以分解成若干环.

引理 2.1.27

在偶图中, 每一个不可扩张 (non-extendible) 的迹是闭合的.

利用该引理也可以证明连通的偶图是欧拉图, 更进一步的, 引理所描述的不可扩张的闭合的迹就是欧拉回路. 考虑采用反证法.

命题 2.1.28

对于简单图 $G$, 设其中每个点的度数至少为 $k$, 那么 $G$ 至少包含一个长度为 $k$ 的路径. 当 $k\geqslant 2$ 时, $G$ 至少包含一个长度为 $k+1$ 的环.

定理 2.1.29

设 $G$ 是一个非平凡连通分支, 含有恰好 $2k$ 个度数为奇数的节点, 则至少需要 $\max\{1,k\}$ 条迹分解这个图.

证明

给奇度点两两配对连边, 那么得到一个偶图, 存在欧拉回路, 再将添加的边删除, 得到 $k$ 条迹.

顶点度数和计数

定义 2.1.30

度 (degree): $d(v)$, 边的数量, 自环算两次.

$\Delta(G)$: 最大点度数. $\delta(G)$: 最小点度数.

当 $\Delta(G)=\delta(G)$, 称 $G$ 是正则的.

边数 $e(G)$.

点数 $n(G)$.

命题 2.1.31

$$ \sum\limits_{v\in V(G}d(v)=2e(G). $$

推论 2.1.32

平均度数 $\frac{2e(G)}{n(G)}$, $\delta(G)\leqslant \frac{2e(G)}{n(G)}\leqslant \Delta(G)$.

定义 2.1.33

k 维立方体 / 超立方体 (hypercube), 顶点为长度为 k 的二进制数, 两个顶点连边当且仅当其二进制数恰有一个位置不同. 记作 $Q_k$.

$j$ 维的子立方体记作 $Q_j'$

性质 2.1.34

$Q_k$ 是二部图, 可以按照二进制下 1 的个数的奇偶性划分部集.

$Q_k$ 是 k-正则的.

$d(v)=k$, $n(Q_k)=2^k$, $e(Q_k)=k2^{k-1}$.

$Q_k$ 中 $Q_j'$ 的个数是 $\binom{k}{j}2^{k-j}$.

命题 2.1.35

k-正则的二部图, 两个部集的顶点数量相同.

组合计数问题, 构造双射, 将难以计算的集合映射到计算简单的集合.

例 2.1.36

$n$ 个点有标号的简单偶图个数是 $2^{\binom{n-1}{2}}$.

证明

设 $E_n$ 为简单偶图的集合, $S_n$ 是简单图的集合.

显然有 $|S_n|=2^{\binom{n}{2}}$.

下面构造 $f:E_n\to S_{n-1}$.

删除编号为 $n$ 的点及其边, 那么就得到了一个 $n-1$ 个点的简单图. 从而得到了一个映射 $f$.

考虑 $g:S_{n-1}\to E_n$.

对于所有度数为奇数的点 $u$, 添加边 $(u,n)$, 从而得到一个 $n$ 个点的偶图.

显然 $f(g(G))=G$, 从而 $f,g$ 互为逆映射, 故 $|E_n|=|S_{n-1}|=2^{\binom{n-1}{2}}$.

组合极值问题.

例 2.1.37

$n$ 个点的简单图最多 $\binom{n}{2}$ 条边.

$n$ 个点的简单连通图最少 $n-1$ 条边.

命题 2.1.38

$G$ 是 $n$ 个点的简单图, 如果 $\delta(G)\geqslant\frac{n-1}{2}$, 则有 $G$ 是连通的.

证明

考虑任意不相邻的 $x,y$.

那么 $x,y\notin N(X),N(y)$, 从而 $|N(x)\cup N(y)|\leqslant n-2$, 于是 $|N(x)\cap N(y)|=|N(x)|+|N(y)|-|N(x)\cup N(y)|\geqslant 1$, 从而 $x,y$ 存在公共邻居, 故连通.

定理 2.1.39

$n$ 个顶点的简单图, 如果不含有三元环, 那么最多只能有 $\lfloor\frac{n^2}{4}\rfloor$.

证明

设 $k=\Delta(G)$, 存在 $x\in V(G),\ s.t.\ d(v)=\Delta(G)$.

考虑 $x$ 的邻居 $N(x)$, 由于没有三元环, 所以 $N(x)$ 是独立集, 从而 $e(G)\leqslant (n-k)k$, 因为每条边一定与 $V(G)-N(x)$ 的点相连, 而与 $V(G)-N(x)$ 中的点相连的边最多 $(n-k)k$ 条边, 点数乘最大度数. 而 $(n-k)k$ 的最大值就是 $\lfloor\frac{n^2}{4}\rfloor$.

定理 2.1.40

任意无自环的图 $G$, 一定存在一个二部子图至少含有 $\frac{e(G)}{2}$ 条边.

证明

法一:

任取一个顶点集的二部划分, $X,Y\subset V(G),\ V(G)=X\cup Y,\ X\cap Y=\varnothing$.

令 $H=(V(H),E(H)), V(H)=V(G), E(H)=\{e\in E(G)|\exists x\in X,y\in Y, e=(x,y)\}$.

调整法, 寻找 $d_H(x)<\frac{d_G(v)}{2}$ 的 $x$, 将其放入另一边总边数增加.

法二:

考虑数学归纳法, 对顶点个数归纳.

设 $n=k$ 成立.

$n=k+1$ 时, 先考虑 $\{1,\ldots,k\}$ 的导出子图存在这样一个二部子图, 记起顶点划分为 $X,Y$, 那么考虑 $k+1$ 与 $X,Y$ 之间的边数, 至少存在一个集合的边数不超过 $\frac{d(k+1)}{2}$. 从而将 $k+1$ 放入这个部集.

有向图

定义 2.1.41

有向图 (digraph): 给所有边定向.

有向简单图每个点可以有一个自环.

定义 2.1.42

有限状态机 (finite state machine)

点表示状态.

边表示状态之间的转换.

定义 2.1.43

底图: 不考虑方向得到的无向图.

定义 2.1.44

adjacency matrix: $a_{i,j}=1$, $\exists (v_i,v_j)$.

incidence matrix: 尾 $m_{i,j}=1$, 头 $m_{i,j}=-1$.

定义 2.1.45

弱连通: 底图连通.

强连通: 任意两点可以相互到达.

强分支: 极大的强连通子图.

定义 2.1.46

出度 $d^+(v)$, 入度 $d^-(v)$.

出邻域 $N^+(v)$, 入邻域 $N^-(v)$.

最小和最大入度/出度: $\delta^-(G)/\delta^+(G)$, $\Delta^-(G)/\Delta^+(G)$.

命题 2.1.47

$\sum\limits_{v\in G}d^-(v)=e(G)=\sum\limits_{v\in G}d^+(v)$.

定义 2.1.48

欧拉图, 欧拉路, 欧拉回路定义同无向图.

引理 2.1.49

有向图 $G$, 当 $\delta^+(G)\geqslant 1$ 时, $G$ 中存在环.

类似的的, 条件可改为 $\delta^-(G)\geqslant 1$.

证明

考虑极大路径.

定理 2.1.50

有向图是欧拉图当且仅当 $d^+(v)=d^-(v)\forall v\in V(G)$ 且至多有一个非平凡强连通分支.

证明

同无向图, 注意拼接时顺序即可.

例 2.1.51

对于 $2^n$ 个长度为 $n$ 的二进制串, 是否存在一个长度为 $2^n$ 的二进制串, 将其看成循环串时, 其 $2^n$ 个长为 $n$ 的子串互不相同.

上述序列也被称作 de Brujin sequence. 考虑构造一个 $2^{n-1}$ 个点有向图, 对每个顶点 $(a_1a_2\cdots a_{n-1})$, 向 $(a_2a_3\cdots a_{n-1}0)$ 连一条边权为 $0$ 的边, 向 $(a_2a_3\cdots a_{n-1}1)$ 连 $1$. 称这样的图为 $D_n$.

该图一共 $2^n$ 条边, 在这个图中走一个欧拉回路即可. 因为每一个入边加顶点构成一个长为 $n$ 的二进制数, 并且由于顶点互不相同, 这个二进制数也不同.

定义 2.1.52

定向 (orientation): 给所有边定向.

定向图 (oriented graph): 给简单图定向. 故不存在自环和二环.

竞赛图 (tournament): 对完全图的定向.

定义 2.1.53

有向图的王 (king): 一个节点, 满足其到所有点存在一个长度不超过 2 的路径.

定理 2.1.54

任意竞赛图有一个王.