图

贡献者：零穹; xiaokuc; huanglei0829

预备知识　映射

　　 [1] [2] 直观上，图要描述的是一些带有两端点的边和一些点构成的对象。这样的对象有以下几种情况：

　　两种可能的边：1.有方向的边，这是指边的端点有起止点之分的情形，此时的图称为有向图；2.无方向的边，这是指边的端点没有起止的差异，无论两个点在边的哪一头都被认为是相同的，这样的图叫无向图。

　　两种可能的点：1.有边连接的点，即这样的点是某些边的端点；2.无边连接的点，即这样的点不是任何边的端点，这样的点叫做孤立点。

　　 3 种可能的图：1.无点无边的图，这是个空集；2.有点无边的图，这被称为空图；3.有点有边的图。因为边必然包含点，所以没有无点有边的图。

　　图论的所有基本概念都是为了建立起以上图像及对图的操作的严格化语言。本文旨在建立上述图像的严格化语言。

1. 图的定义

　　当建立起某一对象的数学语言时，我们应当首先借助集合论的基本工具。首先，图包含两个代表点和边的集合。而边是连接两个端点的边，因此若对不同的点最多只有一边连接它们，就可以通过指定端点确定边。这时，对于无连接顺序之分的无向边，可以用代表集合的无序符号 " ${*}$ " 把它们括起来；而对于有向的边，则用代表有序对的符号 " $(*)$ " 把它们括起来。然而若允许图的两点之间可以有不同的点相连时，就不能用端点来确定边了，并且边集 ${{x, y}, {x, y}}$ 因为有重复元而不满足集合的定义。但是边始终被认为是有端点的，因此我们总可以指定边的端点。这样就在边集和点集之间建立了一个关联，因此一般的图应当包含所谓的关联函数。

　　值得注意的是，很多教材将图定义为只有点集和边集组成的二元组对象，使得它们在建立具有相同端点的不同边的模型的时候，而在 “图” 的前面加上一些形容词。本文认为，图的概念应当尽可能包含充分多的图，而不限于不同边只能对应不同端点，而把众多已经建立的（带有形容词的）图概念包含在图中来，从而 “某某图” 只是具有 “某某” 限制的图。因此，我们采用文献 [2] 的观点。

定义 1　 $n$ 元子集的族

　　设 $A$ 是集合，则记 $A$ 的所有 $n$ 元子集的全体为 $[A]^{n}$ 。即

\begin{matrix} (1) & [A]^{n} = {{x_{1}, \dots, x_{n}} | x_{i} \in A, i = 1, \dots n} . \end{matrix}

定义 2　有序对和 2 元子集的族

　　设 $A$ 是集合，则记 $A$ 的所有 2 元子集和有序对的全体为 $P_{2} (A)$ 。即

\begin{matrix} (2) & P_{2} (A) = [A]^{2} \cup (A \times A) . \end{matrix}

定义 3　图，顶点，边，关联函数，阶数

　　设 $V, E$ 是集合， $φ : E \to P_{2} (A)$ 是 $E$ 到 $V$ 的二元对族的映射。则称三元组 $G = (V, E, φ)$ 为图（graph）。 $V$ 的元素称为 $G$ 的顶点（vertex）， $E$ 的元素称为 $G$ 的边（edge）或弧 (arc)， $φ$ 称为关联函数（incidence function）。 $V$ 的基数（元素个数）称为图 $G$ 的顶点数或阶（order），记作 $| G |$ ，而 $E$ 的基数称为 $G$ 的边数（size），记作 $‖ G ‖$ 。

　　当然，顶点也可以称为节点（node）或点（point），边还能叫做线（line），具有顶点集 $V$ 的图也能称为 $V$ 上的图（a graph on $V$ ），往往图 $G$ 的顶点集记作 $V (G)$ ，边集记作 $E (G)$ ，而 $x \in V (G), e \in E (G)$ 直接记作 $x \in G, e \in G$ 等等，这都是习惯的问题，熟悉它们往往是有好处的。

　　值得强调的是，图中可能有端点相同的边出现，但是 $P_{2} (V)$ 中包含了 $(x, x)$ ，它相当于端点相同的边。因此我们无需在 $P_{2} (V)$ 中加入 $V$ 的单点子集来表示端点相同的边。由于代表边的序对 $(x, x)$ 交换 $x$ 不变，因此可以认为 $(x, x)$ 是无向的。

2. 点和边的关系及分类

　　下面概念给出了边的有向性。

定义 4　边的有向性，端点

　　设 $G = (V, E, φ)$ 是图， $e \in E$ 。若 $φ (e) \in [V]^{2} \cup {(x, x) | x \in V}$ ，则称 $e$ 是无向的（undirected）；若 $φ (e) \in V \times V$ ，则称 $e$ 是有向的（directed）。若 $φ (e) = {v_{1}, v_{2}}$ ，则简记 $e = {v_{1}, v_{2}}$ ，而 $v_{1}, v_{2}$ 称为 $e$ 的端点；若 $φ (e) = (v_{1}, v_{2})$ ，则简记 $e = (v_{1}, v_{2})$ 。对有向边 $e = (v_{1}, v_{2})$ ，称 $v_{1}$ 是 $e$ 的起点（origin）， $v_{2}$ 是 $e$ 的终点（terminus）。 $e$ 的起点和终点也称为 $e$ 的端点（end vertex）。若 $x$ 是 $e$ 的端点，则记 $x \in e$ 。

定义 5　边的交

　　设 $e, f$ 是两个边，则它们共同的端点的全体

\begin{matrix} (3) & {x | x \in e, x \in f} \end{matrix}

称为

e, f

的交，记作

e \cap f

。

　　下面的概念通过边的端点给出了边之间的关系。

定义 6　环，对称，平行

　　设 $G = (V, E, φ)$ 是图， $e_{1}, e_{2} \in E$ 。若 $φ (e_{1}) = (v, v)$ ，则称 $e$ 为环（loop）。若 $φ (e_{1}) = (v_{1}, v_{2}), φ (e_{2}) = (v_{2}, v_{1})$ ，则称 $e_{1}, e_{2}$ 为对称边（symmetric edges）。若 $e_{1}, e_{2}$ 分别是起止点相同的有向边，则称 $e_{1}, e_{2}$ 为平行边（parallel edges）或重边（multi-edges）。

　　显然，无向图中端点相同的边是平行的。

　　下面的概念用于表达点和边之间的关系的。

定义 7　关联，端点，连接，相邻，独立

　　设 $G = (V, E, φ)$ 是图， $x, y \in V, e, f \in E$ 。若 $x, y \in e$ ，则：

称 $x$ （ $y$ 也是同样的）和 $e$ 是关联的（incident）；
$x$ 和 $y$ 称为相邻的(adjacent 或 adjacent)。
$v$ 称为在 $x$ 上的边。
$x$ 和 $y$ 也称为 $e$ 的端点（endvertex）或顶端（end）；
$e$ 也称为连接（join） $x$ 和 $y$ 的边；
若 $x \in X, y \in Y$ ，则称边 $x y$ 为 $X - Y$ 边（ $X - Y$ edge）。
所有 $X - Y$ 边的全体记作 $E (X, Y)$ 。而 $E ({x}, Y), E (X, {y})$ 则分别简记作 $E (x, Y), E (X, y)$ 。所有和 $v \in V$ 关联的边的全体记作 $E (v)$ 。
若 $e \cap f \neq \emptyset$ ，则称 $e$ 和 $f$ 是相邻的。
不相邻的点或边称为是独立的（independent）。
若一个点集或边集中没有两个元是相邻的，则称该集是独立的（或稳定的（stable））。

　　上面的概念显然反映了我们日常生活中对 “关联”，“相邻"等的理解。

3. 图的分类

　　根据图的阶的分类，又将图分为有限图、可数图和无限图。

定义 8　有限图，可数图，无限图，空图，平凡图

　　设 $G$ 是图，若 $| G |, ‖ G ‖ \in N$ ，则称 $G$ 是有限的（finite）；若 $V (G), E (G)$ 有一个是可数集，另一个不是不可数集（见集合的基数），则称 $G$ 是可数的（countable）；若不是以上两种情况，则称 $G$ 是无限的（infinite）。 $| G | = 0, 1$ 的有限图 $G$ 称为平凡的¹（trival）。其中 $‖ G ‖ = 0$ 的图 $G$ 称为空图（empty graph）。

　　根据边集的分类，图又可分为无向图、有向图和混合图

定义 9　无向图，有向图，混合图

　　设 $G = (V, E, φ)$ 是图，若 $φ (E) \subset [V]^{2}$ ，则称 $G$ 为无向图（undirected graph）；若 $φ (E) \subset V \times V$ ，则称 $G$ 为有向图（directed graph）；若 $φ (E) \cap [V]^{2} \neq \emptyset, φ (E) \cap (V \times V) \neq \emptyset$ ，则称 $G$ 为混合图（mixed graph）。

　　有一种图相对来说比较简单，它的不同点之间最多只有一条边，且是无环的图。

定义 10　简单图

　　不同两点之间最多只有一条边的无环图称为简单图（simple graph）。简单图可以简记为 $(V, E)$ 。

　　下面的概念通过将无向图的边都换成一对对称边而得到的图称为对称有向图。

定义 11　对称有向图

　　设 $G = (V, E, φ)$ 是无向图。将 $E$ 的每一条边都用端点和它相同的一对对称边替代得到的边集记作 $E^{'}$ ，并记 $φ^{'}$ 是对应新图的关联函数。则称 $(V, E^{'}, φ^{'})$ 为由 $G$ 得到的对称有向图（symmetric digraph）。

　　下面的概念将不同两个都有边相连的简单无向图称为完全图。

定义 12　完全图

　　设 $G = (V, E)$ 是简单无向图，若任意 $v_{1} \neq v_{2} \in V$ ，存在连接它们的边 $e \in E$ ，则称 $G$ 为完全图（complete graph）。

　　下面的概念将完全图的对称有向图称为完全有向图。

定义 13　完全有向图

　　完全图的对称有向图称为完全有向图（complete diagraph）。

　　下面的概念将点集分为 $n$ 个部分，其中每一部分的点间是互不相邻的图称为 $n$ 部分图。

定义 14　 $n$ 部图

　　设 $G = (V, E, φ)$ 是图。若 $V$ 可分为 $n$ 个不相交的非空点集 $V_{1}, \dots, V_{n}$ ，且任一边的端点在不同的 $V_{i}$ 中，则称 $G$ 是 $n$ 部图（partite graph）。二部图也称为偶图。

　　由定义可知， $n$ 部图是无环的，否则因为环的端点相同，环的端点就在同一集中。此外，同一 $V_{i}$ 中的点不可能相邻。

定义 15　完全 $n$ 部分图

　　设 $G = (V, E, φ)$ 是简单 $n$ 部无向图， $V_{1}, \dots, V_{n}$ 是对应的划分。若 $\forall x \in V_{i}, y \in V_{j}, i \neq j$ ，都有 $e \in E$ ，使得 $x, y$ 相邻，则称 $G$ 为完全 $n$ 部图。

4. 图的惯用表示

定义 16　图的惯用表示

　　按照习惯，在绘制图的时候，用圆圈来代表点，而用带箭头的线代表有向边（箭头指向终点），用不带箭头的线代表无向边。

　　如何绘制圆圈和线是不重要的，重要的是正确体现点对之间是否有边。

5. 图的同态和同构

　　同一图不同的人有不同的画法，因为重要的仅仅是哪些点之间有边，哪些点之间没边。因此就可能有外观上有很大差异的图，但是本质上是相同的。下面我们将建立同态和同构的概念，它们所起的作用就是帮助我们识别哪些图本质是相同的。为了明白数学上建立它们的思想，这里做一个讨论：

　　在集合中，若两个集合是一一对应的，就被称为是对等的。“对等” 其实表达了数学的思想，这就是指表示集合的名称和元素的具体符号不重要，重要的仅仅是集合的元素的个数，我们可以完全认为它们是同一个集合，只是不同的人表达同一个东西用了不一样的符号标记而已。

　　当集合的元素之间有某些关系的时候，关系的名称也不重要，重要的是哪些元素之间有关系，哪些元素之间没有关系。对于元素之间有某些关系的集合，不同的人²完全可以选择不同的表达方式，即可以使用不同的符号，但应当正确表达哪些元素之间有关系，哪些没有关系。当使用不同的记号来表示元素之间具有关系的集合的时候，若它们都正确的表达了同样的关系，我们称这两种表示是同构的。也有可能，不同的人表达同一个东西，有的人只是表达了该东西的某一部分。另一个人不光表达了前一个人表达的部分，还表达了其它部分，那么就称它们是同态的。

　　有了这一图像，容易理解下面的数学概念。

定义 17　同态，同构，自同构，抽象图

　　设 $G = (V, E, φ), G^{'} = (V^{'}, E^{'}, φ^{'})$ 是两个图。若存在映射

\begin{matrix} (4) & f : V \to V^{'} \end{matrix}

满足

\begin{matrix} (5) & \forall {x_{1}, y_{1}}, (x_{2}, y_{2}) \in E \Rightarrow {f (x_{1}), f (y_{1})}, (f (x_{2}), f (y_{2})) \in E^{'},, \end{matrix}

就称

G

和

G^{'}

是 同态的（homomorphism），相应的

f

称为同态映射（简称同态）；若同态

f

是双射，则称

G

和

G^{'}

同构（isomorphism），并记作

G ≅ G^{'}

（通常我们不区分同构的图，而直接记成

G = G^{'}

），相应的映射

f

称为同构映射（简称同构）。若同构映射

f

的定义域和值域都是图

G

，则称

f

是自同构映射(automorphism)。

　　与给定图同构的所有图的全体被非正式地称为抽象图（abstract graph）。

　　容易验证，完全图及完全有向图在同构意义下是唯一的。

　　很多时候，人们感兴趣的只是图的结构，所以常常略去名称，用一个其顶点和边的名称都没有的图形作为同构图等价类中的代表元素。有时也给图的顶点或边加以标号。

定义 18　标号图

　　在图的表示中，若图的顶点都用记号进行标记了，则称为标号图（labelled graph）。

定义 19　记号约定 $K_{n}$

　　 $n$ 阶完全图和完全有向图的等价类分别记作 $K_{n}, K_{n}^{*}$ 。特别 $K_{3}$ 称为三角形（triangle）。

6. 图的性质

　　既然同构的图本质是相同的，那么若某一图具有某个性质，那么真正和它 “同构” 的图就应当具有该性质。下面的概念表达了这一思想。

定义 20　图性质，图不变量

　　设 $A$ 是图 $G$ 的某种（已有定义的）特征。若与 $G$ 同构的图都有特征 $A$ ，则称 $A$ 是图性质(graph property)。定义在同构图的全体上的恒值映射被称为图不变量（graph invariant）。

定义 21　边极大

　　设图 $G$ 具有图性质 $A$ 。若 $G$ 的任意真子图都没有性质 $A$ ，则称 $G$ 关于 $A$ 是边极大的（edge-maximal）。

7. 图的运算

　　下面的概念表达了将两个图放在一起和取公共部分的思想。

定义 22　图的交并差

　　设 $G = (V, E, φ), G^{'} = (V^{'}, E^{'}, φ^{'})$ 是两个图。记

\begin{matrix} (6) & \begin{aligned} E_{0} = {e \in E \cap E^{'} | φ (e) = φ^{'} (e)}, \\ E_{1} = {e | e \in E \cup E^{'}} ∖ ((E \cap E^{'}) ∖ E_{0}), \\ E_{2} = {e \in E ∖ E^{'} | φ (e) \in V ∖ V^{'}}, \\ φ_{0} : E_{0} \to V \cap V^{'}, φ_{0} (e) = φ (e), \\ φ_{1} : E_{1} \to V \cup V^{'}, φ_{1} (e) = {\begin{aligned} φ (e), e \in E, \\ φ^{'} (e), e \in E^{'} . \end{aligned} \\ φ_{2} : E ∖ E^{'} \to V, φ_{2} (e) = φ (e) . \end{aligned} \end{matrix}

　　则

\begin{matrix} (7) & (V \cap V^{'}, E_{0}, φ_{0}) \end{matrix}

称为

G, G^{'}

的交，记作

G \cap G^{'}

；而

\begin{matrix} (8) & (V \cup V^{'}, E_{1}, φ_{1}) \end{matrix}

称为

G, G^{'}

的并，记作

G \cup G^{'}

；

\begin{matrix} (9) & (V ∖ V^{'}, E_{2}, φ_{2}) \end{matrix}

称为

G, G^{'}

的差，记作

G ∖ G^{'}

。

　　下面的概念表达从一个图删掉一些点或边构建新的图。

定义 23　删除，增加

　　设 $G = (V, E, φ)$ 是一个图， $V^{'}, E^{'}$ 分别是任意的点集和边集。则称 $G [V ∖ V^{'}]$ 为从 $G$ 中删除(delete) $V \cap V^{'}$ 中所有点及相关联的边得到的图，记作 $G - V$ ；称 $(V, E ∖ E^{'}, φ |_{E ∖ E^{'}})$ 为从 $G$ 中删除 $E \cap E^{'}$ （或简称 $E^{'}$ ）中所有边得到的图，记作 $G - E^{'}$ 。设 $G^{'} = (V^{'}, E^{'}, φ^{'})$ ，记

\begin{matrix} (10) & \begin{aligned} E_{1} = {e \in E^{'} | φ^{'} (e) \in P_{2} [V]}, \\ φ_{1} : E \cup E_{1} \to P_{2} [V], φ_{1} (e) = {\begin{aligned} φ (e), e \in E, \\ φ^{'} (e), e \in E^{'} . \end{aligned} \end{aligned} \end{matrix}

　　则称 $(V, E \cup E_{1}, φ_{1})$ 为从 $G$ 中增加 $[V]^{2} \cap E^{'}$ （或简称 $E^{'}$ ）中所有边得到的图，记作 $G + E^{'}$ 。当只删除一点或一边时，记 $G - v := G - {v}, G - e := G - {e}, G + e := G + {e}$ 。

　　下面的概念将有向图变成无向图。

定义 24　无向化映射

　　设 $G = (V, E, φ)$ 是图。设 $φ (e) = {x, y} 或 (x, y) 或 (y, x)$ ，则称映射

\begin{matrix} (11) & \begin{array}{r} π : E \to P_{2} (V), π (e) = {\begin{matrix} {x, y}, x \neq y, \\ (x, y), x = y . \end{matrix} \end{array} \end{matrix}

为（关于

G

的）无向化映射。

8. 图的构造

　　通过交运算定义子母图，反映图的包含关系

定义 25　不交，子图，母图，真子图

　　设 $G = (V, E, φ), G^{'} = (V^{'}, E^{'}, φ^{'})$ 是两个图。若 $E (G \cap G^{'}) = V (G \cap G^{'}) = \emptyset$ ，则称 $G$ 和 $G^{'}$ 是不交的（disjoint）；若 $G \cap G^{'} = G$ ，则称 $G$ 是 $G^{'}$ 的子图（subgraph），而 $G^{'}$ 称为 $G$ 的母图（supergraph），记作 $G \subset G^{'}$ 。若 $G \subset G^{'}, G \neq G^{'}$ ，则称 $G$ 是 $G^{'}$ 真子图（proper subgraph）。

　　在简单无向图的完全图中把简单无向图的边去掉得到的图叫补图。

定义 26　补图，自补图

　　设 $G$ 是简单无向图，若 $G^{'}$ 是它对应的完全图。则称 $(V (G), E (G^{'}) ∖ E (G), φ)$ （ $φ$ 是 $G^{'}$ 的关联函数在 $E (G^{'}) ∖ E (G)$ 上的限制）是 $G$ 的补图（complementary graph），记作 $G^{c}$ 或 $\overset{―}{G}$ 。若 $G = \bar{G}$ ，则称 $G$ 是自补的（self complementary）。

　　下面的概念表达了从一个图如何生成新的图。

定义 27　导出子图，支撑

　　设 $G = (V, E, φ)$ 是图， $V^{'} \subset V$ 。定义端点在 $V^{'}$ 中的所有 $E$ 中的边全体 $E^{'}$ 及其上的映射 $φ^{'}$ 如下，

\begin{matrix} (12) & \begin{array}{r} E^{'} := {e \in E | φ (e) \in V^{'}}, \\ φ^{'} : E^{'} \to V^{'}, φ^{'} (e) = φ (e) . \end{array} \end{matrix}

则称

(V^{'}, E^{'}, φ^{'})

为

G

（关于

V^{'}

）的导出子图（induced subgraph），或称

V^{'}

在

G

中导出（induce）或支撑（span）

(V^{'}, E^{'}, φ^{'})

，记作

G [V^{'}]

。若

H \subset G

，则记

G [H] := G [V (H)]

。

　　若有图 $H = (V (H), E (H), φ_{H})$ ，使得 $V (H) = V (G), E (H) \subset E (G), φ_{H} = φ |_{E (H)}$ （其中 $φ |_{E (H)}$ 是 $φ$ 在 $E (H)$ 上的限制），则称 $H$ 是 $G$ 的支撑子图（spanning subgraph）或生成子图。

　　下面的概念通过无向化映射可以将有向图变为无向图，通过定向操作将无向图变为有向图。

定义 28　基础图，定向图

　　设 $G_{1} = (V_{1}, E_{1}, φ_{2})$ 是有向图， $G_{2} = (V_{2}, E_{2}, φ_{2})$ 是无向图， $π$ 是 $G_{1}$ 的无向化映射。则称

\begin{matrix} (13) & (V_{1}, E_{1}, π) \end{matrix}

为

G_{1}

的基础图（underlying graph）。

　　定义 $G_{2}$ 上（方向任意）的定向化映射

\begin{matrix} (14) & \begin{array}{r} f : E_{2} \to P_{2} (V_{2}), f (e) = (x, y), \\ 其中 φ_{2} (e) = {x, y} . \end{array} \end{matrix}

则称图

\begin{matrix} (15) & (V_{2}, E_{2}, f) \end{matrix}

为

G_{2}

的一个定向图（oriented graph）。

定义 29　竞赛图

　　完全图的定向图称为竞赛图（tornament）。

1. ^ 数学上说某个东西平凡就是代表其仅仅起到建立严格语言的作用，而没有其它研究价值，太普通了这样的含义
2. ^ 这里的 “人” 完全可以换成对同一事物进行反映的客体

[1] ^ Reinhard Diestel. Graph theory,2nd,Springer press.
[2] ^ 徐俊明.图论及应用. 中国科学技术大学出版社, 合肥.1998.

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。

图

1. 图的定义

定义 1 n 元子集的族

定义 2 有序对和 2 元子集的族

定义 3 图，顶点，边，关联函数，阶数

2. 点和边的关系及分类

定义 4 边的有向性，端点

定义 5 边的交

定义 6 环，对称，平行

定义 7 关联，端点，连接，相邻，独立

3. 图的分类

定义 8 有限图，可数图，无限图，空图，平凡图

定义 9 无向图，有向图，混合图

定义 10 简单图

定义 11 对称有向图

定义 12 完全图

定义 13 完全有向图

定义 14 n 部图

定义 15 完全 n 部分图