第一章 图的概念¶
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 \]
-