第一章 图的概念¶
1.1 引例¶
-
七桥问题
-
四色猜想
-
哈密顿问题
1.2 图的定义¶
图的基本定义¶
-
定义：一个图通常表示为
\[ G=(V,E) \]其中：
-
\(V\) 是顶点集（vertex set），其元素称为顶点或节点；
-
\(E\) 是边集（edge set），其元素称为边；
-
\(|V|\) 是图的顶点数，称为图的阶（order）；
-
\(|E|\) 是图的边数。
-
-
无向图（undirected graph）：边没有方向，边的两个端点之间不存在方向区别。
-
有向图（directed graph）：边具有方向，通常称为弧（arc）。有向图可表示为顶点集和弧集。
-
从顶点发出的弧称为出边
-
指向顶点的弧称为入边
-
图的基本术语¶
-
关联（incident）：称边与该边的两个顶点相关联。
-
相邻（adjacent）：
-
由同一条边连接的两个顶点称为相邻顶点。
-
具有公共端点的两条边称为相邻边。
-
-
端点（endpoint）：一条边所连接的两个顶点称为该边的端点。
-
环（loop）：两个端点相同的边。
-
棱（link）：两个端点不同的边。
-
重边（multiple edges）：连接同一对顶点的多条边。
-
简单图（simple graph）：没有环且没有重边的图。
-
边数上界：对于一个阶为 \(n\) 的简单图，每两个不同顶点之间至多有一条边，且不存在环，因此边数满足
\[ |E|\leq\frac{n(n-1)}{2} \]当且仅当任意两个不同顶点之间都有边时取等号，此时图为完全图。
-
-
完全图（complete graph）：任意两个不同顶点之间都有边的简单图，记为 \(K_n\)。
-
平凡图（trivial graph）：只有一个顶点的图，\(|V|=1,|E|=0\)。
-
空图（null graph）：没有边的图，\(|E|=0\)。
-
度（degree）：与顶点 \(v\) 关联的边数，记作 \(d(v)\)，其中每个环计数为 \(2\)
-
最大度：\(\Delta(G)\)；
-
最小度：\(\delta(G)\)；
-
奇点（odd vertex）：度为奇数的顶点；
-
偶点（even vertex）：度为偶数的顶点。
-
孤立点（isolated vertex）：度为 \(0\) 的顶点。
-
悬挂点（end vertex）：度为 \(1\) 的顶点。
-
悬挂边（end edge）：与悬挂点关联的边。
-
出度（out-degree）与入度（in-degree）：有向图中，顶点 \(v\) 的出度记为 \(d^{+}(v)\)，入度记为 \(d^{-}(v)\)，则有
\[ d(v)=d^{+}(v)+d^{-}(v) \] -
握手定理：无向图中所有顶点的度之和等于边数的两倍。
\[ \sum_{v\in V}d(v)=2|E| \]因此，图中奇度顶点的个数必为偶数。
-
Ramsey 数¶
对于正整数 \(a,b\)，Ramsey 数 \(R(a,b)\) 是满足下列性质的最小正整数：
任意给定 \(R(a,b)\) 个顶点的完全图，并将每条边染成两种颜色之一，则必然存在：
-
一个由 \(a\) 个顶点构成的同色完全子图，或
-
一个由 \(b\) 个顶点构成的另一种颜色的完全子图。
典型结果包括
1.3 图的同构¶
图的恒等与同构¶
-
图恒等：若两个图的顶点集和边集分别相同，则称两个图恒等，记为
\[ G=H \]图恒等要求图的顶点和边本身相同，而不仅仅是结构相同。
-
图同构：设
\[ G=(V_G,E_G),\quad H=(V_H,E_H) \]若存在顶点集之间的一一映射和边集之间的一一映射，并且这两个映射保持关联关系，则称图 \(G\) 与图 \(H\) 同构，记为
\[ G\cong H \] -
图同构的核心是两个图具有相同的结构，只是顶点标号、边标号或绘图方式可能不同。
-
图同构必须保持以下结构关系：
-
顶点之间的相邻关系；
-
边与顶点之间的关联关系；
-
顶点的度；
-
环和重边等结构特征。
-
-
判定两个图是否同构是个未解决的困难问题。
二部图¶
-
二部图/偶图（bipartite graph）：若图 \(G=(V,E)\) 的顶点集可以划分为两个互不相交的集合 \(V_1\) 和 \(V_2\)，满足
\[ V=V_1\cup V_2,\quad V_1\cap V_2=\varnothing \]且 \(V_1\) 和 \(V_2\) 都是独立集，则称 \(G\) 为二部图，记为 \(G=(V_1,V_2;E)\)。
- 独立集：其中任意两个顶点都不相邻的顶点集。
-
完全二部图（complete bipartite graph）：完全二部图 \(K_{m,n}\) 是一个二部图，其两个部分分别含有 \(m\) 个和 \(n\) 个顶点，并且两个部分之间的每一对顶点都相邻。
\[ |V|=|V_1|+|V_2|=m+n,\quad |E|=mn \]- 完全二部图 \(K_{n,n}\) 中每个顶点的度均为 \(n\)，因此它是 \(n\)-正则图。
-
二部图的判定：染色法
-
任取一个顶点，将其染成第一种颜色。
-
将其所有相邻顶点染成另一种颜色。
-
继续扫描已经着色但尚未处理的顶点，将其相邻顶点染成相反颜色。
-
如果整个过程中没有出现相邻顶点颜色相同的情况，则图是二部图。
-
如果出现相邻顶点必须被染成相同颜色的矛盾，则图不是二部图。
-
1.4 子图¶
子图及相关概念¶
设
-
子图（subgraph）：若 \(H\) 的顶点集和边集都是 \(G\) 的顶点集和边集的子集，即
\[ V_H\subseteq V,\quad E_H\subseteq E \]则称 \(H\) 为 \(G\) 的子图，记为
\[ H\subseteq G \] -
真子图：若子图 \(H\) 不与 \(G\) 相等，即
\[ H\subseteq G,\quad H\neq G \]则称 \(H\) 为 \(G\) 的真子图，记为
\[ H\subset G \]- 相应地，\(G\) 称为 \(H\) 的母图或超图（super graph）
-
生成子图（spanning subgraph）：若子图 \(H\) 与原图 \(G\) 具有相同的顶点集，即
\[ H \subseteq G,\quad V(H)=V(G) \]则称 \(H\) 为 \(G\) 的生成子图（spanning subgraph）。
- 相应的，\(G\) 称为 \(H\) 的生成母图
-
基础简单图（underlying simple graph）：从一个图中删除所有环和重边后得到的简单图，称为该图的基础简单图。
-
点导出子图（induced subgraph）：设 \(V'\subseteq V\) 且 \(V'\neq\varnothing\)。以 \(V'\) 为顶点集，并包含原图中两个端点都属于 \(V'\) 的全部边所构成的子图，称为点导出子图，记为
\[ G[V']=\{V',E'\},\quad \begin{cases} V'\subseteq V,\\ E'=\{uv\in E:u,v\in V'\} \end{cases} \]-
完全图的每个导出子图是完全图
-
偶图的每个导出⼦图是偶图
-
-
边导出子图（edge-induced subgraph）：设 \(E'\subseteq E\) 且 \(E'\neq\varnothing\)。以 \(E'\) 为边集，并以 \(E'\) 中所有边的端点构成顶点集所得到的子图，称为边导出子图，记为
\[ G[E']=\{V',E'\},\quad \begin{cases} E'\subseteq E,\\ V'=\{v\in V:uv\in E'\text{ 或 }vu\in E'\} \end{cases} \]
子图的运算¶
-
点删除：从图中删除顶点集 \(V'\) 以及所有与 \(V'\) 中的顶点关联的边，记作
\[ G-V' = \{V-V',E'\},\quad E'=\{uv\in E:u,v\in V-V'\} \]有 \(G-V' = G[V \backslash V']\)，即所得图是原图的点导出子图。
-
边删除：从图中删除边集 \(E'\)，记作
\[ G-E' = \{V,E-E'\} \]注意 \(G-E'\) 不一定等于 \(G[E \backslash E']\)，前者一定是生成子图，而后者不一定。
-
边添加：向图中添加边集 \(E'\)，记作
\[ G+E' = \{V,E\cup E'\} \]有 \(G+E'\) 是原图的母图。
子图的关系¶
设 \(G_1,G_2 \subseteq G\)，则有：
-
不相交（disjoint）：两个子图没有公共顶点
\[ V(G_1)\cap V(G_2)=\varnothing,\quad E(G_1)\cap E(G_2)=\varnothing \] -
边不相交（edge-disjoint）：两个子图没有公共边，但可能具有公共顶点
\[ E(G_1)\cap E(G_2)=\varnothing \] -
并图：由两个子图的顶点集和边集分别取并集得到
\[ G_1\cup G_2=\{V(G_1)\cup V(G_2),E(G_1)\cup E(G_2)\} \] -
交图：由两个子图的顶点集和边集分别取交集得到
\[ G_1\cap G_2=\{V(G_1)\cap V(G_2),E(G_1)\cap E(G_2)\} \]
正则图¶
-
正则图：若图中每个顶点具有相同的度，则称该图为正则图。若每个顶点的度均为 \(k\)，则称该图为 \(k\)-正则图。
-
推论：
-
奇数度的正则图必然含有偶数个顶点。
-
具有 \(n\) 个顶点的 \(k\)-正则图存在的必要和充分条件是 \(n\geq k+1\) 且 \(nk\) 是偶数。
-
补图¶
-
补图（complement graph）：设 \(G=(V,E)\) 是一个图。补图 \(G^c\) 是一个与 \(G\) 具有相同顶点集的图，其边集为所有在 \(G\) 中不相邻的顶点对构成的边集。
\[ V(G^c)=V(G), \quad E(G^c)=\{(u,v):u,v\in V,\ u\neq v,\ uv\notin E\} \]有
\[ G^{c} = K_n - E(G) \] -
自补图：若图 \(G\) 与其补图同构，即
\[ G\cong G^c \]则称 \(G\) 为自补图。
-
定理：若 \(G\) 是阶为 \(n\) 的自补图，则 \(|E(G)|=|E(G^c)|=\frac{n(n-1)}{4}\)，则 \(n(n-1)\equiv0\pmod 4\)，从而自补图的阶满足
\[ n\equiv0\text{ 或 }1\pmod 4 \]
-
1.5 路和连通性¶
途径、迹与路¶
-
途径（walk）：由顶点和边交替组成的有限非空序列。
-
途径中允许顶点和边重复出现。
-
途径可以写成
\[ W=\{v_0,e_1,v_1,e_2,\ldots,e_k,v_k\} \]其中每条边 \(e_i\) 连接相邻的两个顶点 \(v_{i-1}\) 和 \(v_i\)。
-
-
基本术语：
-
起点（origin）：途径的第一个顶点；
-
终点（terminus）：途径的最后一个顶点；
-
内部顶点（internal vertex）：除起点和终点外的顶点；
-
途径长度（walk length）：途径中边的数量，重复出现的边重复计数；
-
节/段（section）：途径中的子序列；
-
逆途径：\(W^{-1}\)，将原途径 \(W\) 方向反转后得到的途径；
-
衔接：\(WW'\)，若一个途径 \(W\) 的终点是另一个途径 \(W'\) 的起点，则可以将两者衔接。
-
迹（trail）：不存在重复边的途径，但顶点可以重复出现。
-
路（path）：不存在重复顶点的途径，因此边也不会重复出现。
-
-
距离（distance）：若图 \(G\) 中存在连接顶点 \(u\) 和 \(v\) 的路，则所有这类路中长度最短者的长度称为 \(u\) 到 \(v\) 的距离，记为
\[ d_G(u,v) \]若 \(u\) 和 \(v\) 之间不存在路，则通常规定
\[ d_G(u,v)=\infty \] -
直径：
-
连通图的直径定义为任意两个顶点之间距离的最大值：
\[ d(G)=\max\{d_G(u,v)\mid u,v\in V\} \] -
不连通图，图的直径通常定义为无穷大:
\[ d(G)=\infty \]
-
-
距离的性质：
-
距离满足：
\[ d_G(u,v)\ge 0, \quad d_G(u,u)=0 \] -
在无向图中：
\[ d_G(u,v)=d_G(v,u) \] -
三角不等式：
\[ d_G(u,w)\leq d_G(u,v)+d_G(v,w) \]
-
连通性¶
无向图的连通性¶
-
\(G\) 中顶点 \(u\) 和 \(v\) 连通（connected）\(\iff G\) 中存在 \((u,v)\)-路 \(\iff G\) 中存在 \((u,v)\)-迹 \(\iff G\) 中存在 \((u,v)\)-途径。
-
分支（component）：根据 \(G\) 中顶点间的连通性，可将其划分为等价类：\(V_1,V_2,\ldots,V_k\)，使得 \(V_i\) 中的任意两个顶点连通，而不同 \(V_i\) 中的顶点不连通。称每个 \(G[V_i]\) 为 \(G\) 的分支，\(\omega(G)=k\) 为 \(G\) 的分支数。
-
无向图的连通性：在无向图中，如果一个图的任何两个顶点之间都有一条路，那么我们称这个图是连通的，否则是不连通的。
-
\(G\) 是连通图 \(\iff \omega(G)=1\)
-
\(G\) 是不连通图 \(\iff \omega(G)>1\)
-
有向图的连通性¶
-
可达：在有向图中，若存在一条从 \(u\) 到 \(v\) 的有向路，则称 \(u\) 可达 \(v\)。
-
有向图的连通性：
-
单向连通：任意两个顶点中，至少有一个顶点可以到达另一个顶点。
-
强连通：任意两个顶点都可以相互到达。
-
弱连通：去掉所有边的方向后，所得无向图是连通图。
-
-
性质：
\[ \text{强连通}\implies\text{单向连通}\implies\text{弱连通} \] -
强连通分支：若有向图的一个子图是强连通的，且不存在包含它的更大强连通子图，则称其为强连通分支，也称强连通分图。
连通性性质¶
-
定理：若图 \(G\) 不连通，则其补图 \(G^c\) 连通。
-
割边：设 \(V\) 是图的顶点集，\(S\) 是 \(V\) 的非空真子集。记两端点分别属于 \(S\) 和 \(\overline{S} = V\setminus S\) 的边集合为割边集，可表示为
\[ [S,\overline{S}]_G=\{uv\in E:u\in S,v\in V\setminus S\} \]- \(G\) 是连通图 \(\iff \forall S\subset V\)，都有 \([S,\overline{S}]_G\neq\varnothing\)
-
定理:
-
设图顶点数 \(|V|\ge 2\)，边数 \(|E|\leq |V|-2\)，则图不连通。
-
若图是连通图，则其边数至少为顶点数减一，即
\[ |E|\geq |V|-1 \] -
设 \(G\) 是阶为 \(n\) 的简单图。若
\[ \delta(G)\geq\frac{n-1}{2} \]则 \(G\) 连通。
-
赋权图¶
-
边赋权图：在图 \(G\) 的每条边 \(e\) 上标记一个实数 \(w(e)\)，称 \(G\) 为边赋权图，称 \(w(e)\) 为边的权值。
-
子图的权值：若 \(H\) 是赋权图 \(G\) 的子图，则 \(H\) 的权值定义为其所有边的权值之和：
\[ w(H)=\sum_{e\in E(H)}w(e) \] -
赋权图中最短路：设 \(G\) 是边赋权图，\(u,v\) 是图中的两个顶点。在所有连接 \(u\) 和 \(v\) 的路中，边权值之和最小的路称为 \(u\) 和 \(v\) 之间的最短路。
-
最短路算法：
-
Dijkstra 算法；
-
Bellman-Ford 算法；
-
Floyd-Warshall 算法。
-
-
1.6 圈¶
-
闭途径（closed walk）：起点与终点相同且长度大于 \(0\) 的途径。
-
闭迹（closed trail）：起点和终点相同的迹，边各不相同，也称为回路（circuit）。
-
圈（cycle）：起点和终点相同的路，顶点各不相同。
-
\(k\)-圈（\(k\)-cycle）：长为 \(k\) 的圈。
-
奇圈（odd cycle）：长为奇数的圈。
-
偶圈（even cycle）：长为偶数的圈。
-
-
定理：
-
图 \(G\) 为二部图，当且仅当 \(G\) 不含奇圈。
-
无向图 \(G\) 中，若最小度满足 \(\delta(G)\geq2\)，则 \(G\) 中含圈；若 \(G\) 是简单图，则含长度至少为 \(\delta(G)+1\) 的圈。
-
1.7 图的数据结构¶
邻接矩阵¶
-
邻接矩阵：设 \(G\) 为 \(n\) 阶图，顶点集为
\[ V=\{v_1,v_2,\ldots,v_n\} \]图 \(G\) 的邻接矩阵记为 \(A(G)=(a_{ij})_{n\times n}\)，其中 \(a_{ij}\) 表示顶点 \(v_i\) 与 \(v_j\) 之间的边数。
-
性质：
-
非负性：由邻接矩阵定义知，\(a_{ij}\) 是非负整数，即邻接矩阵是非负整数矩阵。
-
对称性：在无向图中，若顶点 \(v_i\) 与 \(v_j\) 邻接，则 \(v_j\) 与 \(v_i\) 邻接，即
\[ a_{ij}=a_{ji} \]所以，\(A(G) = A^T(G)\)。
-
相似性：同一图的不同形式的邻接矩阵是相似矩阵。
-
度：若 \(G\) 是无环图，则 \(A(G)\) 中的第 \(i\) 行（列）的元素之和等于 \(v_i\) 的度：
\[ \sum_{j=1}^{n}a_{ij}=d(v_i) \] -
如果 \(G\) 为简单图，则：
-
\(A(G)\) 为布尔矩阵；
-
行和（列和）等于对应顶点的度数；
-
矩阵元素总和为图的总度数，也就是 \(G\) 的边数的 \(2\) 倍：
\[ \sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}=2|E| \]
-
-
连通性：图 \(G\) 连通的充分必要条件是 \(A(G)\) 不能与如下矩阵相似：
\[ \begin{pmatrix} A_{11}&0\\ 0&A_{22} \end{pmatrix} \] -
无向图途径数量：给定无向无权图 \(G\)，\(A(G)\) 为图 \(G\) 的邻接矩阵，则图 \(G\) 中长度为 \(k\) 的 \((v_i,v_j)\)-途径的数目等于
\[ a_{ij}^{(k)}=[A^k(G)]_{ij} \]-
推论：
-
设图 \(G\) 是 \(n\) 阶无向图，则 \(G\) 是连通图的充分必要条件是矩阵
\[ X = A(G)+A^2(G)+\cdots+A^{n-1}(G) \]中的每一个元素都是非 \(0\) 的。
-
连通图 \(G\) 中的两个顶点 \(v_i\) 和 \(v_j\) 之间的距离等于满足
\[ a_{ij}^{(k)}\neq 0 \]的最小正整数 \(k\)，其中 \(i\neq j\)。
-
-
-
有向图途径数量：给定有向无权图 \(D\)，\(A(D)\) 为有向图的邻接矩阵，则图 \(D\) 中长度为 \(k\) 的 \((v_i,v_j)\)-有向途径的数目等于
\[ a_{ij}^{(k)}=[A^k(D)]_{ij} \]
-
关联矩阵¶
-
关联矩阵：给定图 \(G=(V,E)\)，其关联矩阵记为 \(M_G=(a_{ij})_{n\times m}\)，其中 \(n=|V|\)，\(m=|E|\)，其中
\[ a_{ij}= \begin{cases} 2,&\text{顶点 }v_i\text{ 与边 }e_j\text{ 关联且 }e_j\text{ 是环},\\ 1,&\text{顶点 }v_i\text{ 与边 }e_j\text{ 关联},\\ 0,&\text{顶点 }v_i\text{ 与边 }e_j\text{ 不关联}. \end{cases} \] -
性质
-
关联矩阵的元素为 \(0\)、\(1\) 或 \(2\)。
-
关联矩阵的每列和为 \(2\)。
-
每行的和为对应顶点的度数。
-
握手定理：无向图 \(G\) 的关联矩阵中的所有元素之和等于图 \(G\) 边数量的两倍，即
\[ \sum_{i=1}^{n}\sum_{j=1}^{m}a_{ij}=2|E| \]
-