离散数学笔记（12）——图论的基本概念

wzf2000
2019年12月2日

离散数学笔记（12）——图论的基本概念

图论

图的基本概念

无向图的概念

设 $A,B$ 是两个非空集合，记：
$$A \times B = \{\langle a,b \rangle | a \in A \land b \in B\} \\ A \& B = \{(a,b) | a \in A \land b \in B\}$$
定义 1：一个无向图 $G$ 定义为一个二元组 $\langle V,E \rangle$，记作 $G = \langle V,E \rangle$，其中：

1. $V$ 是一个非空集合，称为 $G$ 的顶点集，它的元素称为顶点。
2. $E \subseteq V \& V$，称为 $G$ 的边集，其元素称为边，$V \& V$ 中的元素可以在 $E$ 中出现不止一次。

定义 2：没有任何边的图称为空图，只有一个点的图称为平凡图。

定义 3：图中顶点的个数称为图的阶，若 $|V(G)| = n$，则称 $G$ 为 $n$ 阶图；连接两个相同顶点的边的条数称为边的重数，这些边称为平行边或多重边。

邻接点：与一边关联的两个结点。

邻接边：关联同一个点的两条边。

环：只关联一个结点的边。

简单图：没有环以及没有重数大于 $1$ 的边的图。

孤立点：不与任何点邻接的点。

以下记 $|V(G)| = n,|E(G)| = m$。

无向图结点 $v$ 的度

$G$ 是无向图，$v \in V(G)$，结点 $v$ 所关联边数，称之为结点 $v$ 的度，记作 $d(v)$，环对度贡献为 $2$。

奇点：度为奇数的点。

偶点：度为偶数的点。

无向图的结点度序列

令 $G = \langle V,E \rangle$ 是无向图，$V = \{v_1,v_2,\cdots,v_n\}$，则称 $(d(v_1),d(v_2),\cdots,d(v_n))$ 为图 $G$ 的结点度序列。

图的最大度和最小度

最大度：$\Delta(G) = \max \{d(v) | v \in G\}$

最小度：$\delta(G) = \min \{d(v) | v \in G\}$

相关定理

定理 1：每个无向图所有结点度总和等于边数的 $2$ 倍，即：
$$\sum_{v \in V} d(v) = 2 |E|$$
定理 2：每个无向图中，奇数度的结点必为偶数个。

$k$-正则图

一个无向简单图 $G$ 中，如果 $\Delta(G) = \delta(G) = k$，则称 $G$ 为 $k$-正则图。

完全图

$G$ 是个简单图，如果每对不同结点之间，都有边相连，则称 $G$ 是个无向完全图。如果 $G$ 有 $n$ 个结点，记为 $K_n$。

定理：完全图 $K_n$ 有边数 $\dfrac{n(n – 1)}{2}$。

补图

定义 1：设 $G$ 是简单图，$H$ 是一个以 $V(G)$ 为顶点集的图，且两个顶点在 $H$ 中邻接当且仅当它们则在 $G$ 中不邻接，则称 $H$ 是 $G$ 的补图，记作 $H = \overline{G}$。

定义 2：由 $G$ 的所有结点和为使 $G$ 称为完全图，所需要添加的那些边组成的图，称之为 $G$ 的补图。

图的同构

设 $G = \langle V,E \rangle$ 和 $G’ = \langle V’,E’ \rangle$ 是图，如果存在双射 $f : V \to V’$ 且任何 $e = (v_i,v_j) \in E$，有 $e’ = (f(v_i),f(v_j)) \in E’$，并且边 $e$ 与 $e’$ 的重数相同。

则称 $G$ 与 $G’$ 同构，记作 $G \stackrel{\backsim}{=} G’$。

两个图同构的必要条件：

1. 结点个数相等。
2. 边数相等。
3. 度数相同的结点数相等。
4. 对应的结点的度数相等。

子图

定义 1：称图 $H$ 为图 $G$ 的子图，如果 $V(H) \subseteq V(G)$，$E(H) \subseteq E(G)$，且 $H$ 中边的重数不能超过 $G$ 中对应边的重数。

定义 2：设 $G = \langle V,E \rangle$，一个满足 $H = \langle V,E_1 \rangle$，$E_1 \subseteq E$ 的子图称为 $G$ 的生成子图。

定义 3：设 $V’$ 是图 $G$ 的顶点集 $V$ 的一个非空子集，以 $V’$ 作为顶点集，以两端点均在 $V’$ 的边的全体为边集的子图，称为由 $V’$ 导出的 $G$ 的子图，记为 $G[V’]$，称其为 $G$ 的导出子图。

定义 4：设 $E’$ 是图 $G$ 的边集 $E$ 的一个非空子集，以 $E’$ 为边集，以 $E’$ 中边的全体端点为顶点集组成的子图称为由 $E’$ 导出的子图，记为 $G[E’]$。

注：$G$、空图均为 $G$ 的子图，而且是非空子图，称为平凡子图。其中，$G$ 为 $G$ 的点导出子图。

路与回路

路（walk）

给定图 $G = \langle V,E \rangle$，设 $v_0,v_1,\cdots,v_k \in V,e_1,e_2,\cdots,e_k \in E$，其中 $e_i$ 是关联 $v_{i – 1}$ 和 $v_i$ 的边，则称结点和边的交叉序列 $v_0e_1v_1\cdots e_kv_k$ 是连接 $v_0$ 和 $v_k$ 的路。

$v_0$ 是此路的起点，$v_k$ 是此路的终点。路中含有的边数 $k$ 称之为路的长度。

如果 $G$ 是个简单图，则路可以只用结点序列表示。

回路

如果一条路的起点和终点是同一个结点，则称此路是一个回路。

迹（chain）和闭迹

如果一条路中，所有边都不同，则称此路为迹。

如果一条回路中，所有边都不同，则称此回路为闭迹。

通路（path）和圈（cycle）

如果一条路中，所有结点都不同，则称此路为通路。

如果一条回路中，除起点和终点外，其余结点都不同，则称此回路为圈。

 离散数学 笔记