图的基本概念

图的定义

图是一个有序的二元组 $⟨ V, E ⟩$ 。无向图中， $V$ 称为顶点集， $E$ 是 $V & V$ 的无序积的多重子集，其元素称为无向边；有向图中， $E$ 是笛卡尔积 $V \times V$ 的多重子集，其元素称为有向边。

常用 $G$ 表示无向图， $D$ 表示有向图。 $V (G)$ 和 $E (G)$ 分别表示 $G$ 的顶点集和边集。若 $∣ V (G) ∣ = n$ ，则称 $G$ 为 $n$ 阶图。 $∣ V (G) ∣$ 与 $∣ E (G) ∣$ 均为有限数时称 $G$ 为有限图。边集为空时称为零图。

顶点与边的关系

边 $e = (u, v)$ （无向）或 $⟨ u, v ⟩$ （有向）， $u$ 、 $v$ 称为 $e$ 的端点。若 $u = v$ ，则 $e$ 为环。无边关联的顶点称为孤立点。

在无向图中，邻域 $N (v)$ 是与 $v$ 相邻的顶点集，闭邻域包含 $v$ 自身。
在有向图中，后继元集 $Γ^{+} (v)$ 和先驱元集 $Γ^{-} (v)$ 分别表示从 $v$ 出发可达和到达 $v$ 的顶点集。

关联一对顶点的多条边称为平行边。含平行边的图称为多重图，既无平行边也无环的图称为简单图。

度

无向图中，顶点 $v$ 的度数 $d (v)$ 是 $v$ 作为边的端点的次数之和。最大度 $Δ (G)$ 和最小度 $δ (G)$ 分别是顶点度数的最大值和最小值。度数为 $1$ 的顶点称为悬挂顶点，其边为悬挂边；偶度、奇度顶点按度数奇偶性区分。

有向图中， $v$ 的出度 $d^{+} (v)$ 是 $v$ 作为始点的次数，入度 $d^{-} (v)$ 是作为终点的次数，度数 $d (v) = d^{+} (v) + d^{-} (v)$ 。最大/最小出度、入度分别记作 $Δ^{+}, δ^{+}, Δ^{-}, δ^{-}$ 。

握手定理

定理（握手定理）：任何无向图中，各顶点度数之和等于边数的两倍，即 $\sum d (v) = 2∣ E ∣$ 。

推论：任何图中，奇度顶点的个数是偶数。

可图化：给定非负整数列 $d = (d_{1}, d_{2}, \dots, d_{n})$ ，若存在以这些数为度数的图，则称 $d$ 是可图化的。 $d$ 可图化当且仅当 $\sum d_{i}$ 为偶数。若所得图是简单图，则称 $d$ 是可简单图化的。

定理： $n$ 阶无向简单图中， $Δ (G) \leq n - 1$ 。

子图

设 $G = ⟨ V, E ⟩$ ， $G^{'} = ⟨ V^{'}, E^{'} ⟩$ 为两个图（同为无向或有向）：

若 $V^{'} \subseteq V$ 且 $E^{'} \subseteq E$ ，则 $G^{'}$ 是 $G$ 的子图， $G$ 为 $G^{'}$ 的母图。
生成子图：在原图上保留所有点和其中的一些边，即 $V^{'} = V$ ， $E^{'} \subseteq E$ 。
点导出子图：保留一部分点和这些点直接关系的边，即以 $V^{'}$ 为顶点集，以两端都在 $V^{'}$ 中的边为边集的图，记作 $G [V^{'}]$ 。
边导出子图：保留一部分边和这些边直接关系的点，即以 $E^{'}$ 为边集，以 $E^{'}$ 中边关联的顶点为顶点集的图，记作 $G [E^{'}]$ 。

图同构

设 $G_{1} = ⟨ V_{1}, E_{1} ⟩$ ， $G_{2} = ⟨ V_{2}, E_{2} ⟩$ 为两个无向图，若存在双射 $f : V_{1} \to V_{2}$ ，使得 $(u, v) \in E_{1}$ 当且仅当 $(f (u), f (v)) \in E_{2}$ 且重数相同，则称 $G_{1}$ 与 $G_{2}$ 同构，记作 $G_{1} ≅ G_{2}$ 。同构是等价关系，在图同构意义下数学定义与图形表示一一对应。