图、节点和边

一个具有三个顶点和三条边的简单无向图。每个顶点的度数为二，因此它也是一个正则图。

一个图是一个有序对 $G=(V,E)$ ，其中：

V 是顶点集，其元素是图的顶点或节点。这个集合通常用 $V(G)$ 或简写为 $V$ 表示。
E 是边集，其元素是图的边或顶点之间的连接。这个集合通常用 $E(G)$ 或简写为 $E$ 表示。如果图是无向的，个体边是无序对 $\left\{u,v\right\}$ ，其中 $u$ 和 $v$ 是 $V$ 中的顶点。如果图是有向的，边是有序对 $(u,v)$ 。

两个图 $G$ 和 $H$ 被认为相等，当 $V(G)=V(H)$ 和 $E(G)=E(H)$ 。

图的阶数是指图中顶点的数量，通常用 $|V|$ 或 $|G|$ 表示，有时也用 $n$ 表示。图的边数是指图中边的数量，用 $|E|$ 或 $\Vert G\Vert$ 表示，有时也用 $m$ 表示。如果 $n=0$ 和 $m=0$ ，该图被称为空图或零图。如果 $n=1$ 和 $m=0$ ，该图被称为平凡图。如果 $1\leq n$ 和 $m=0$ ，该图被称为离散图。

无向图

无向图是指边没有方向的图。边 (a, b) 与边 (b, a) 相同，即它们不是有序对，而是顶点 {u, v}（或 2-多重集）的集合。

有向图

有向图或有向图是一个有序对 D = (V, A) ，其中

V 是一个集合，其元素被称为顶点或节点，并且
A 是一个顶点有序对的集合，称为弧、有向边或箭头。

弧 a = (x, y) 被认为是从 x 指向 y 的；y 被称为弧的头部，x 被称为弧的尾部；y 被称为 x 的直接后继，x 被称为 y 的直接前驱。如果一条路径从 x 到 y，则 y 被称为 x 的后继，并且可以从 x 到达，而 x 被称为 y 的前驱。弧 (y, x) 被称为弧 (x, y) 反向。

如果对于 D 中的每个弧，相应的反向弧也属于 D，则有向图 D 被称为对称。一个对称的无环有向图 D = (V, A) 等价于一个简单的无向图 G = (V, E)，其中 A 中的反向弧对一一对应于 E 中的边；因此，G 中的边数量 |E| = |A|/2，即 D 中弧数量的一半。

这个定义的一个变体是有向图，其中 (x, y) 和 (y, x) 中最多只有一个可以是弧。

示例

在图像中，你可以看到一个图。

图的顶点集是 $V(G)=\left\{1,2,3,4,5,6\right\}$ .

图的边集是 $E(G)=\left\{\left\{1,2\right\},\left\{1,5\right\},\left\{2,3\right\},\left\{2,5\right\},\left\{3,4\right\},\left\{4,5\right\},\left\{4,6\right\}\right\}$ .

该图的阶数是 $|V(G)|=6$ .

该图的大小是 $|E(G)|=7$ .

子图、收缩和图的次图

子图

给定一个图 $G=(V,E)$ 和一个图 $G'=(V',E')$ ， $G'$ 是 $G$ 的子图当且仅当 $V'\subseteq V$ 且 $E'\subseteq E$ 。由此可以明显看出，每个图 $G$ 至少包含空图和自身作为子图，因为空图 $\varepsilon$ 的顶点集和边集都是空集，它们都是所有集合的子集，并且 $V(G)\subseteq V(G)$ 且 $E(G)\subseteq E(G)$ 。此外，某个图 $G$ 的所有子图 $G'$ 都可以通过从 $G$ 中进行一系列边删除和顶点删除操作来构造。形式上，存在一个序列 $G_{0},G_{1},...,G_{n}$ ，其中 $G_{0}=G$ 且 $G_{n}=G'$ ，对于每个 $1\leq i\leq n$ ，都是通过从 $G_{i-1}$ 中删除一条边或一个顶点来构造的。

边收缩

给定一个图 $G=(V,E)$ ，以及图中顶点 $x,y$ 之间的某条边 $e$ ，通过收缩边 $e$ 得到的图是图 $G'$ ，其顶点集等于 $V\setminus \{x,y\}\cup \{v_{xy}\}$ ，其中 $v_{xy}$ 是收缩 $e$ 所形成的顶点，它与 $x$ 的所有邻居以及 $y$ 的所有邻居相邻。

图的子图

给定一个图 $G$ ，以及另一个图 $G'$ ， $G'$ 被称为 $TG$ ，如果 $G'$ 是通过在 $G$ 的边中插入度数为 2 的顶点形成的。这个过程称为 **细分**， $G$ 的顶点被称为 $G'$ 的 **分支顶点**，而 $G'$ 中的其他顶点被称为 **细分顶点**。现在，如果某个图 $H$ 包含 $TG$ 作为子图，那么 $H$ 被称为具有 $G$ 作为 **拓扑小图**。

给定一个图 $G$ ，以及另一个图 $G'$ ， $G'$ 被称为一个 $IG$ ，如果 $G'$ 是由 $G$ 通过用连通图替换 $G$ 的顶点形成的，使得如果一个顶点 $v$ 被一个连通图 $G_{v}$ 替换，则存在连接 $G_{v}$ 到替换 $v$ 在 $G$ 中相邻的顶点的每个图的边，并且仅限于那些图。这个过程称为 **膨胀**，因此用一个 $I$ 来表示它，而替换 $G$ 中顶点的图被称为 $G'$ 的 **分支集**。现在，如果某个图 $H$ 包含一个 $IG$ 作为子图，那么 $H$ 被认为具有 $G$ 作为 **次要图**，记为 $G\preceq H$ 。

定理：如果 $G$ 是 $H$ 的拓扑次要图，那么 $G\preceq H$ 。

证明：由于 $G$ 是 $H$ 的拓扑次图，因此存在 $TG$ 是 $H$ 的子图。将该 $TG$ 称为 $G'$ 。将 $G'$ 的分支顶点从 $1$ 到 $|G|$ 编号。现在，对于 $G'$ 中的每个细分顶点 $v$ ，将 $v$ 添加到包含距离 $v$ 最小的分支顶点的分支集中。如果 $v$ 具有两个距离最小的分支顶点，则将其添加到包含编号较小的分支顶点的分支集中。现在，每个顶点都在一个分支集中，并且分支集是不相交的，并且每个分支集都是连通的。这产生了 $IG$ 是 $H$ 的子图，因此 $G\preceq H$ 。

关联、邻接、度

关联的概念将边与由该边连接的节点相关联。例如，边 $\left\{u,v\right\}$ 与节点 $u$ 和 $v$ 关联。

如果一条边连接了两个节点，我们就说这两个节点是相邻的。更正式地说， $u,v\in V(G)$ 如果 $\left\{u,v\right\}\in E(G)$ 相邻。节点 v 的邻域，记为 $N(v)$ ，是所有与它相邻的节点的集合。

节点 v 的度，记为 $\deg(v)$ ，是与它关联的边的数量。在一个有向图中，入度和出度分别计算进入和离开顶点的有向边的数量。

图 $G$ 的最小度，记为 $\delta (G)$ ，是 $\min \limits _{v\in V(G)}d(v)$ ，即 $G$ 中所有顶点的度数的最小值。

类似地，图 $G$ 的最大度，记为 $\Delta (G)$ ，是 $\max \limits _{v\in V(G)}d(v)$ ，即 $G$ 中所有顶点的度数的最大值。

握手引理

握手引理是度数和公式（有时也称为握手引理）的结果，

\sum _{v\in V}\deg(v)=2|E|

证明欧拉证明度数和公式使用了双重计数技巧：他用两种不同的方法计算了关联对 $\left\{v,e\right\}$ 的数量，其中e是边，顶点v是它的一个端点。顶点v属于 deg(v) 个对，其中 deg(v)（v 的度数）是与它关联的边的数量。因此，关联对的数量是度数的总和。然而，图中的每条边都属于正好两个关联对，一个对应它的每个端点；因此，关联对的数量是 2|E|。由于这两个公式计算的是同一组对象，因此它们的值必须相等。

在整数的和中，和的奇偶性不受和中偶数项的影响；当奇数项的数量为偶数时，总和为偶数；当奇数项的数量为奇数时，总和为奇数。由于度数和公式的一侧是偶数 2|E|，因此另一侧的和必须包含偶数个奇数项；也就是说，必须存在偶数个奇度顶点。

曼特尔定理

一个n个顶点的无三角形图中边的最大数量是 $\lfloor n^{2}/4\rfloor .$

证明

假设 $G(V,E)$ 是一个有 $n$ 个顶点的图。我们来算一下这个图最多可以有多少条边。

对于每条边 $\left\{u,v\right\}$ ，如果存在一个与 $u$ 和 $v$ 都相邻的顶点 $w$ ，那么就会形成一个三角形。因此我们知道这样的顶点不存在，也就是说 $u$ 的邻域与 $v$ 的邻域不相交。

$N(v)\cap N(u)=\emptyset$

这意味着任何其他顶点要么与 $u$ 相邻，要么与 $v$ 相邻。当我们计算 $u$ 和 $v$ 的度数时，我们发现它们的和最多为 $n$ ，因为一个顶点要么被计入 $u$ 的邻域，要么被计入 $v$ 的邻域。

$d(u)+d(v)<n$

上面的不等式对于每条边都成立。因此我们有与边数一样多的不等式。如果我们将所有这些不等式加起来，我们会发现每个顶点的度数 $d(v)$ 会出现 $d(v)$ 次，所以我们必须加上 $d(v)^{2}$ 。不等式变为

$\sum _{v\in V(G)}d(v)^{2}<n\cdot |E(G)|$

因为每条边都有两个端点，所以所有顶点的度数之和恰好是边数的两倍。

$\sum _{v\in V(G)}d(v)=2\cdot |E(G)|$

在具有标准内积的 $\mathbb {R} ^{n}$ 中，柯西-施瓦茨不等式为

$\left(\sum _{i=1}^{n}x_{i}y_{i}\right)^{2}\leq \left(\sum _{i=1}^{n}x_{i}^{2}\right)\left(\sum _{i=1}^{n}y_{i}^{2}\right).$

上面两个公式推导出

$\left(2\cdot |E(G)|\right)^{2}=\left(\sum _{v\in V(G)}d(v)\cdot 1\right)^{2}\leq n\cdot \sum _{v\in V(G)}d(v)^{2}\leq n\cdot (n\cdot |E(G)|)$

解出 $|E(G)|$ ，得到

$|E(G)|\leq n^{2}/4$

遍历

在研究图时，我们经常需要知道从一个顶点到另一个顶点的各种路径，以及这些路径的不同类型。为了理解遍历的概念，我们可以想象图中的节点是城市里的方块，边是连接这些方块的道路。假设你必须从一个方块步行到另一个方块，并且在你的目的地之间有一些中间方块。你可以写下所有你必须经过的道路的列表，路径的概念就是对这个直观概念的正式化。

路径、闭路径、回路和圈

一个 *u-v* **路径** 定义为一个从 *u* 开始到 *v* 结束的顶点序列，其中序列中连续的顶点是图中相邻的顶点。
一个带标签的图形在 6 个顶点和 7 个边上的绘制。
- 一个 **闭路径** 是一个路径，其中第一个和最后一个顶点相同。
一个 *u-v* **迹** 是一个 *u-v* 路径，其中没有边被重复（每条边最多使用一次）。
- 一个 **回路** 或者 **闭迹** 是一个迹，其中第一个和最后一个顶点相同。
一个 *u-v* **通路** 是一个 *u-v* 路径，其中没有顶点被重复（每个顶点最多使用一次）。
- 一个 **圈** 是一个闭合通路，其中第一个和最后一个顶点相同。

例如，在右边的图中， $(6,4,5,1)$ 是一个行走。而 $(4,5,2,3,4)$ 和 $(1,5,2,1)$ 是循环。

图中的距离

现在，我们需要在图中定义一个距离的概念；这有助于我们在图中编码更多数据。

行走的长度: 在特定行走中使用的边的数量。

如果一条边被使用多次，那么它就被计算多次。
平凡行走是长度为 0 的行走。

定理

如果图G包含一个长度为 $\ell$ 的 u-v 行走，那么G包含一个长度 ≤ $\ell$ 的 u-v 路径。

证明

令P是长度最短的u-v行走。我们断言P是一条路径（因为是最短的，所以它消除了重复的顶点）。

假设不是。假设P不是一条路径。然后，至少有一个顶点被重复（使用两次）。然后，设置

P:u=u_{0},u_{1},\ldots ,u_{\ell }=v

，其中

\ell

是P的长度。

并且，我们知道

u_{i}=u_{j}

对于某些

0\leq i<j\leq \ell

。

然后，删除重复的顶点(顶点)得到

P':u=u_{0},u_{1},\ldots ,u_{i},u_{j+1},\ldots ,u_{\ell }=v

。但是，然后我们得到P'的长度小于P的长度，这与我们假设P是最短长度的行走相矛盾。

所以，P必须是一条路径，而且它比任何其他在P中具有顶点的行走都要短。

因此，存在一个长度最多为

\ell

的u-v路径。

图距离

两个顶点 $u$ 和 $v$ 之间的图距离 $d(u,v)$ 是连接它们的路径的最小长度。也是图测地线的长度。
图中两个顶点 $(u,v)$ 之间最短的路径被称为测地线。
如果不存在这样的路径（如果顶点位于不同的连通分量中），则距离设置为 $\infty$ .

测地线

对于图G中的任意两个顶点u和v，u和v之间的距离定义为u和v之间最短路径的长度，记为d(u,v)。

长度为d(u,v)的路径被称为测地线。

d(u,v)的性质：
对于测地线P:u=u₀u₁u₂...u_k=v和一些0≤i,j≤k

d(u₀u_k) = k
d(u_iu_i) = 0（没有移动）
d(u₀u_i) = i
d(u_iu_j) = |j-i|

连通性

是否可以从图中的一个顶点遍历到另一个顶点，取决于图的连通性。

连通性的定义

如果在G中存在一条u-v路径，那么我们说u和v是连通的
如果在G中对于每一对顶点u和v都存在一条u-v路径，那么我们说G是连通的

关于连通性的定理

定理：设G是一个至少有3个顶点的图。如果在G中存在不同的顶点u和v，使得G-u和G-v都是连通的，那么G也是连通的。

证明：设w是G中的一个顶点，它不同于u和v。我们要证明连通性，即对于G中每对顶点（x,y），在G中存在一条x-y路径。我们可以考虑三种（部分重叠）情况

如果x和y都不是u，那么在G-u中存在一条x-y路径，这在G中也是一条x-y路径。
如果x和y都不是v，那么在G-v中存在一条x-y路径，这在G中也是一条x-y路径。
如果{x,y} = {u,v}，那么根据前两种情况我们可以看到，存在一条u-w路径和一条w-v路径。将它们组合起来就得到一条u-v路径。

顶点和边连通性

如果对于图 *G* 中的任意一个子集 $S\subseteq V(G)$ ，只要 $|S|<k$ ， $G-S$ 仍然连通，并且 $|G|>k$ ，那么称图 *G* 为 *k* 连通图。

类似地，如果对于图 *G* 中的任意一个子集 $S\subseteq E(G)$ ，只要 $|S|<\ell$ ， $G-S$ 仍然连通，并且 $|G|>1$ ，那么称图 *G* 为 $\ell$ 边连通。

*G* 的**连通度**是使 *G* 为 *k* 连通的最大的 *k*，记作 $\kappa (G)$ 。

类似地，*G* 的**边连通度**是使 *G* 为 $\ell$ 边连通的最大的 $\ell$ ，记作 $\lambda (G)$ 。

连通度定理

定理： 设 *G* 是一个 *k* 连通图，那么对于任意自然数 $\forall i\in \mathbb {N} ,0\leq i\leq k$ ，*G* 都是 *i* 连通的。

证明： 因为 *G* 是 *k* 连通的，所以对于所有子集 $S\subseteq V(G),|S|<k$ ， $G-S$ 是连通的。由于 $i\leq k$ ，因此对于所有子集 $S\subseteq V(G),|S|<i\leq k$ ， $G-S$ 也是连通的。

定理： 令G为非平凡图。则， $\lambda (G)\leq \delta (G)$ .

证明： 取G中度数为 $\delta (G)$ 的顶点v。然后，移除G中与v关联的所有边将v与图的其余部分分离，前提是 $|G|>\delta (G)+1$ 。因此，G不能是 $\delta (G)$ 边连通的，因此 $\lambda (G)\leq \delta (G)$ .

练习：连通性

如果G是 $\ell$ 边连通的，证明G也是i边连通的 $\forall i\in \mathbb {N} ,0\leq i\leq \ell$ .

同构

图G和H的同构是G和H的顶点集之间的双射

f\colon V(G)\to V(H)\,\!

使得G中的任意两个顶点u和v在G中相邻当且仅当ƒ(u)和ƒ(v)在H中相邻。这种双射通常被称为“边保持双射”，这与同构的一般概念是保持结构的双射相一致。

在上述定义中，图被理解为无向非标记非加权图。然而，同构的概念可以应用于图概念的所有其他变体，方法是添加保持相应结构元素的要求：弧方向、边权重等，但以下情况除外。当谈论具有唯一标签的图标签时，通常从整数范围 1,...,n 中获取，其中n 是图的顶点数，两个标记图被称为同构，如果对应的底层未标记图是同构的。

如果两个图之间存在同构，那么这两个图被称为同构，我们写 $G\simeq H$ 。在双射是图到自身的映射的情况下，即当G和H是同一个图时，双射被称为G的自同构。

图同构是图上的等价关系，因此它将所有图的类划分为等价类。一组相互同构的图被称为图同构类。

示例

下面显示的两个图是同构的，尽管它们的绘制方式不同。

图 G	图 H	同构 G 和 H 之间
		ƒ(a) = 1 ƒ(b) = 6 ƒ(c) = 8 ƒ(d) = 3 ƒ(g) = 5 ƒ(h) = 2 ƒ(i) = 4 ƒ(j) = 7

动机

“同构”的正式概念，例如“图同构”，捕捉了非正式的概念，即一些对象具有“相同的结构”，如果忽略所讨论对象的“原子”组件的个体区别，请参见上面的示例。每当“原子”组件（对于图，顶点和边）的个体性对于正确表示由图建模的内容很重要时，模型会通过对结构施加额外的限制来改进，并且使用其他数学对象：有向图、标记图、彩色图、有根树等等。同构关系也可以针对所有这些图的概括来定义：同构双射必须保留定义所讨论的对象类型的结构元素：弧、标签、顶点/边颜色、有根树的根等等。

“图同构”的概念使我们能够区分图本身的结构固有的图属性与与图表示相关的属性：图绘制、图数据结构、图标签等等。例如，如果一个图只有一个循环，那么它同构类的所有图也只有一个循环。另一方面，在顶点由整数 1、2、... N（表示）的常见情况下，则表达式

\sum _{v\in V(G)}v\cdot {\text{deg }}v

对于两个同构图可能不同。

补图

图G的补图或逆图是一个具有相同顶点的图H，其中H的两个顶点相邻当且仅当它们在G中不相邻。也就是说，为了生成一个图的补图，需要填充所有形成完全图所需的缺失边，并删除之前存在的边。然而，它并不是图的集合补；只有边被补充了。

正式构造

图 $G=(V,E)$ 的补图是图 ${\bar {G}}=(V,E')$ ，使得对于所有顶点对 $u,v\in G$ ，存在边 $(u,v)\in E'$ 当且仅当 $(u,v)\not \in E$ 。如果我们令 $K=V\times V$ ，我们发现 $E'=K\setminus E$ 。

应用和示例

几个图论概念通过补图彼此相关

无边图的补图是完全图，反之亦然。
任何无三角图的补图是无爪图。
自补图是与自身补图同构的图。
互补图的定义是可以通过不相交并集和补运算构建的图，它们构成一个自补图族：任何互补图的补图是另一个（可能不同的）互补图。

树

树是一种连通图。有向图如果连通且无环，则为树。无向图如果连通，有 $|V|-1$ 条边，且无环（满足其中两个性质的图也满足所有三个性质）。

练习：等价定义

证明以下是对树的等价定义

具有最小边数且连通的图。
具有最大边数且无环的图。
无环，添加任何边都会产生环的图。
具有 n 个节点和 n-1 条边且连通的图。
任何两个节点都通过唯一路径连接的图（路径边只能遍历一次）。

提示：为了使总证明简短，以合适的顺序排列定义，然后证明 A=>B=>C=>D=>E=>A。对具有零个和一个节点的图要特别小心。

有根树

如果一个顶点被指定为根，则树被称为有根树，在这种情况下，边具有自然的定向，朝向或远离根。树序是树顶点的偏序关系，其中u ≤ v 当且仅当从根到v 的唯一路径经过u。如果某个图G 的子图是有根树，并且G 中的每条边的端点在该树序中都是可比较的，那么这个有根树就是正常树。

在有根树中，顶点的父节点是连接到它的通往根的路径上的顶点；除根之外的每个顶点都只有一个父节点。顶点v 的子节点是指以v 为父节点的顶点。

在有根树中，所有顶点最多只有一个父节点。

完全图

完全图是指所有顶点对都由边连接的图。具有 $n$ 个顶点的完全图表示为 $K_{n}$ 。

任何包含与 $K_{5}$ 同构的子图的图都是非平面的。

练习：平面性

$K_{5}$ 可以画在环面上吗？
$K_{5}$ 可以画在克莱因瓶的表面上吗？

练习：子图和同构

在 $K_{n+1}$ 中包含了多少个不同的 $K_{n}$ 的副本？
$K_{n}$ 有多少个自同构？

二部图

如果图 $G=(V,E)$ 的顶点集 $V$ 可以被划分为两个不相交的子集，使得对于每条边 $(u,v)\in E$ ， $u$ 和 $v$ 位于相反的子集中，那么这个图就是二部图。

此外，一个图是二部图当且仅当它不包含奇环。

证明

设

G=(V,E)

是一个任意的、固定的图，它包含一个奇环。

$G$ 是二部图 $\Longrightarrow G$ 不包含奇环

为了反证法，假设

G

包含一个奇环。

设

G_{1},G_{2}

是两个不相交的子集，它们在

G

上形成二部划分。

选择一个奇数环

C

在

G

中，并且，不失一般性地，选择一个节点

v_{1}\in C

来自

G_{1}

。从

v_{1}

开始遍历

C

，注意根据二分图的定义，每个节点都在与它的邻居不同的子集中

G_{1},G_{2}

。

遍历的最后一个节点，

v_{n}

，必须在

G_{1}

中，因为

C

是一个奇数环。然而，

v_{n}

与

v_{1}

相邻，根据环的定义，这与

G_{1}

包含两个相邻节点相矛盾，所以

G

不能包含奇数环。

由于我们已经查看了任意的

C

，并且不失一般性地从

G_{1}

中选择了

v

，我们已经证明了蕴含关系。

$G$ 不包含奇数环 $\Longrightarrow G$ 是二分图

我们提供一个算法将节点排序成两个不相交的集合。

固定一个任意节点 $v\in V$ 。
对于图中的每个节点 $x$ ，计算从 $x$ 到 $v$ 的最短路径。
设 $A,B$ 为节点集合，使得从 $x$ 到 $v$ 的最短路径分别为偶数和奇数。

为了证明该算法的正确性，我们不妨仅考虑集合

A

。

假设存在两个相邻的节点

v_{1},v_{2}\in A

。设

P_{1},P_{2}

分别表示从

v

到

v_{1},v_{2}

的最短路径。

如果 $P_{1}$ 和 $P_{2}$ 不相交，则 $P_{1},(v_{1},v_{2}),P_{2}$ 构成一个奇数长度的环，因为 $P_{1}$ 和 $P_{2}$ 显然具有相同的奇偶性，这与假设矛盾。
如果 $P_{1}$ 和 $P_{2}$ 相交，我们选择与 $v_{1}$ 最近的交点 $v'$ 。注意 $v'$ 不能是 $v_{1}$ 或 $v_{2}$ ，因为从 $v_{1}$ 到 $v_{2}$ 的最短路径不会有相同的奇偶校验。观察到 $v'$ 到 $v_{1}$ 和 $v_{2}$ 的距离必须相同，否则到 $v_{1},v_{2}$ 的最短路径将穿过另一个节点。然而，这是一个矛盾，因为 $(v',v_{1}),(v_{1},v_{2}),(v',v_{2})$ 将是一个奇数环。

因此，

A

中的任何两个节点都不能相邻，并且由于我们无损一般性地考虑了

A

，我们已经证明了算法的正确性，因此反向蕴涵也成立。

完全二部图

完整二分图 $K_{m,n}$ 是一个图，它由两个不相交的子集 $A,B$ 组成，它们的基数分别为 $m,n$ ，使得 $K_{m,n}$ 包含 $A$ 中每个节点和 $B$ 中每个节点之间的边。

图论/定义