迁移来源

旧站标题：定义

新站标题：图论与组合 / 基本概念 / 定义

旧站路径：/math/课程/图论与组合/chapters/基本概念/定义/

旧页面 ID：341

基本概念

图 #

definition

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

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

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

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

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

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

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

团 (clique): 完全的子图.

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

tip

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

definition

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

definition

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

definition

路径 (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)$ 为环.

definition

对于一个无自环的图 $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$ 的端点.

definition

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

tip

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

definition

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

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

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

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

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

definition

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

每个点的度数都是 3.

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

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

Paths, cycles, and trails #

图的连通 Connection in graphs #

definition

游走/通道 (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\}

tip

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

note

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

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

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

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

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

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

definition

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

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

连通关系是等价关系.

definition

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

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

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

tip

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

note

数学归纳法.

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

假设 $k-1$ 成立.

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

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

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

tip

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

definition

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

definition

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

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

tip

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

二部图 Bipartite graph #

tip

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

tip

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

欧拉回路 Eulerian circuit #

definition

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

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

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

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

info

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

tip

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

note

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

tip

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

note

" $\Rightarrow$ ": 显然.

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

tip

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

tip

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

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

tip

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

tip

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

note

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

顶点度数和计数 #

definition

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

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

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

边数 $e(G)$ .

点数 $n(G)$ .

tip

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

tip

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

definition

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

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

abstract

$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}$ .

tip

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

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

example

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

note

设 $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}}$ .

组合极值问题.

example

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

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

tip

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

note

考虑任意不相邻的 $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$ 存在公共邻居, 故连通.

tip

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

note

设 $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$ .

tip

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

note

法一:

任取一个顶点集的二部划分, $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$ 放入这个部集.

有向图 #

definition

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

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

definition

有限状态机 (finite state machine)

点表示状态.

边表示状态之间的转换.

definition

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

definition

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

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

definition

弱连通: 底图连通.

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

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

definition

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

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

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

tip

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

definition

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

tip

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

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

note

考虑极大路径.

tip

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

note

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

example

对于 $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$ 的二进制数, 并且由于顶点互不相同, 这个二进制数也不同.

definition

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

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

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

definition

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

tip

任意竞赛图有一个王.

基本概念

图 #

Paths, cycles, and trails #

图的连通 Connection in graphs #

二部图 Bipartite graph #

欧拉回路 Eulerian circuit #

顶点度数和计数 #

有向图 #

评论