5.8.1 基本概念和记号

1. 无向图和有向图

图 $G$ 是顶点集合 $V$ 和边集合 $E$ 的有序对. 存在一个定义在 $E$ 上的称作关联函数的映射,对 $E$ 的每个元素指派一个 $V$ 的 (不一定互异的) 元素的有序或无序对. 如果对 $E$ 的每个元素指派的是无序对,那么 $G$ 称为无向图(图 5.25). 如果指派的是有序对,那么 $G$ 称为有向图(图 5.26),并且 $E$ 的元素称为弧或有向边. 所有其他的图称作混合图.

在图的表示中, 用点记图的顶点, 用箭记有向边, 并用没有方向的线记无向边.

$◼\mathbf{A}$: 对于图 5.27 中的图 $G$ :

$$V=\left\{v_1,v_2,v_3,v_4,v_5\right\},E=\left\{e_1,e_2,e_3,e_4,e_5,e_6,e_7\right\},$$$$f_1\left(e_1\right)=\left\{v_1,v_2\right\},f_1\left(e_2\right)=\left\{v_1,v_2\right\},f_1\left(e_3\right)=\left\{v_2,v_3\right\},$$$$f_1\left(e_4\right)=\left\{v_3,v_4\right\},f_1\left(e_5\right)=\left\{v_3,v_4\right\},f_1\left(e_6\right)=\left\{v_4,v_2\right\},$$$$f_1\left(e_7\right)=\left\{v_5,v_5\right\}.$$

• $\mathbf{B}$ :对于图 5.26 中的图 $G$ :

$$V=\left\{v_1,v_2,v_3,v_4,v_5\right\},E^{\prime }=\left\{e_1^{\prime },e_2^{\prime },e_3^{\prime },e_4^{\prime }\right\},$$$$f_2\left(e_1^{\prime }\right)=\left(v_2,v_3\right),f_2\left(e_2^{\prime }\right)=\left(v_4,v_3\right),f_2\left(e_3^{\prime }\right)=\left(v_4,v_2\right),$$$$f_2\left(e_4^{\prime }\right)=\left(v_5,v_5\right).$$

$◼\mathbf{C}$: 对于图 5.25 中的图 $G$ :

$$V=\left\{v_1,v_2,v_3,v_4,v_5\right\},E^{\prime \prime }=\left\{e_1^{\prime \prime },e_2^{\prime \prime },e_3^{\prime \prime },e_4^{\prime \prime }\right\},$$$$f_3\left(e_1^{\prime \prime }\right)=\left(v_2,v_3\right),f_3\left(e_2^{\prime \prime }\right)=\left(v_4,v_3\right),f_3\left(e_3^{\prime \prime }\right)=\left(v_4,v_2\right),f_3\left(e_4^{\prime \prime }\right)=\left(v_5,v_5\right).$$

2. 邻接性

如果 $\left(v,w\right)\in E$ ,那么称顶点 $v$ 与顶点 $w$ 邻接. 顶点 $v$ 称为(v, w)的始点, $w$ 称为(v, w)的终点,并且 $v$ 和 $w$ 称为(v, w)的端点

无向图中邻接性及无向边的端点可以类似地定义.

3. 简单图

如果多个边或弧指派给同一个顶点的有向对或无向对, 那么它们称为重边. 具有相同的端点边称为环. 没有环和重边及重弧的图称为简单图.

4. 顶点的次数

与一个顶点 $v$ 关联的边或弧的个数称为顶点 $v$ 的次数 $d_G\left(v\right)$ . 一个环被两次计数. 次数为零的顶点称为孤立顶点.

对于有向图 $G$ 的每个顶点 $v$ ,我们区分 $v$ 的外次数 $d_G^{+}\left(v\right)$ 和内次数 $d_G^{-}\left(v\right)$ 如下:

$$\begin{array}{}\text{(5.316a)}& d_G^{+}\left(v\right)=\left|\{w\mid \left(v,w\right)\in E\}\right|,\end{array}$$$$\begin{array}{}\text{(5.316b)}& d_G^{-}\left(v\right)=\left|\{w\mid \left(w,v\right)\in E\}\right|.\end{array}$$

5. 特殊的图类

有限图有有限的顶点集和有限的边集. 不然称图是无限的. 在 $r$ 次正则图中每个顶点有次数 $r$ .

对于顶点集为 $V$ 的无限简单图,若 $V$ 中任何两个顶点都被一条边连接,则将它称为完全图. 顶点集有 $n$ 个元素的完全图记为 $K_n$ .

如果一个无向简单图 $G$ 的顶点集可以分拆为两个不相交的类 $X$ 和 $Y$ ,使得 $G$ 的每条边连接 $X$ 的一个顶点和 $Y$ 的一个顶点,那么 $G$ 称为二部图. 一个二部图称为完全二部图,如果 $X$ 的每个顶点都有边与 $Y$ 的每个顶点连接. 如果 $X$ 有 $n$ 个元素, $Y$ 有 $m$ 个元素,那么这个图记作 $K_{n,m}$ . 图 5.28 表示有 5 个顶点的完全图. 图 5.29 表示具有 2 元素集 $X$ 和 3 元素集 $Y$ 的完全二部图. 其他特殊的图类有平面图, 树和运输网络. 它们的性质将在后节讨论.

6. 图的表示

有限图可以直观表示: 对于每个顶点指定平面上一个点, 并且用有向或无向曲线连接两个点 (如果图中有相应的边). 图 5.30 的出一些例子. 图 5.33 给出一些例子. 图 5.33 给出彼得森 (Petersen) 图, 它是几个还没有一般性地证明的图论猜想中的一个著名的反例.

7. 图的同构

图 $G_1=\left(V_1,E_1\right)$ 称作与图 $G_2=\left(V_2,E_2\right)$ 同构,当且仅当存在与关联函数相容的从 $V_1$ 到 $V_2$ 的双射 $\phi$ ,以及从 $E_1$ 到 $E_2$ 的双射 $\psi$ ,即如果 $u,v$ 是一条边的端点, 或者 $u$ 是一条弧的始点,而 $v$ 是其终点,那么 $\phi \left(u\right)$ 和 $\phi \left(v\right)$ 是一条边的端点,或者 $\phi \left(u\right)$ 和 $\phi \left(v\right)$ 分别是一条弧的始点和终点. 图 5.34 和图 5.35 给出两个同构的图, 使得 $\phi \left(1\right)=a,\phi \left(2\right)=b,\phi \left(3\right)=c,\phi \left(4\right)=d$ 的映射 $\phi$ 是同构. 在此情形,每个从 $\{1,2,3,4\}$ 到 $\{a,b,c,d\}$ 的双射是同构,因为两个图是顶点个数相同的完全图.

8. 子图、因子

如果 $G=\left(V,E\right)$ 是一个图,并且 $V^{\prime }\subseteq V,E^{\prime }\subseteq E$ ,那么图 $G^{\prime }=\left(V^{\prime },E^{\prime }\right)$ 称作 $G$ 的子图. 如果 $G^{\prime }$ 恰好含有 $E$ 的与 $V^{\prime }$ 的顶点相连接的边,那么 $G^{\prime }$ 称为 $G$ 的由 $V^{\prime }$ 导出的子图 (导出子图).

使得 $V^{\prime }=V$ 的 $G=\left(V,E\right)$ 的子图 $G^{\prime }=\left(v^{\prime },E^{\prime }\right)$ 称为 $G$ 的部分图.

图 $G$ 的因子 $F$ 是 $G$ 的含有 $G$ 的所有顶点的正则子图.

9. 邻接矩阵

有限图可以用矩阵刻画: 设 $G=\left(V,E\right)$ 是一个图,其中 $V=\left\{v_1,v_2,\cdots ,v_n\right\}$ 和 $E=\left\{e_1,e_2,\cdots ,e_m\right\}$ . 设 $m\left(v_i,v_j\right)$ 是从 $v_i$ 到 $v_j$ 的边的个数. 对于无向图,环要两次计数; 对于有向图,环计数一次.(n, n)型的矩阵 $\mathbf{A}=\left(m\left(v_i,v_j\right)\right)$ 称为邻接矩阵. 如果还设 $G$ 是简单图,那么邻接矩阵有下列形式:

$$\begin{array}{}\text{(5.317)}& \mathbf{A}=\left(a_{ij}\right),\text{ 其中 }{a}_{ij}=\{\begin{array}{ll}1,& \left(v_i,v_j\right)\in E,\\ 0,& \left(v_i,v_j\right)\notin E,\end{array}\end{array}$$

即当且仅当存在一条从 $v_i$ 到 $v_j$ 的边时,矩阵 $\mathbf{A}$ 中第 $i$ 行和第 $j$ 列位置是 1 . 无向图的邻接矩阵是对称的.

$◼\mathbf{A}$ : 图 5.36 旁边是有向图 $G_1$ 的邻接矩阵 ${\mathbf{A}}_1=\mathbf{A}\left(G_1\right)$ .

$◼\mathbf{B}$: 图 5.37 旁边是无向简单图 $G_2$ 的邻接矩阵 ${\mathbf{A}}_2=\mathbf{A}\left(G_2\right)$ .

$${\mathbf{A}}_1=\left(\begin{array}{llll}0& 1& 0& 0\\ 0& 0& 0& 0\\ 0& 1& 0& 3\\ 0& 1& 0& 0\end{array}\right)$$$${\mathbf{A}}_2=\left(\begin{array}{llllll}0& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 0\end{array}\right)$$

10. 关联矩阵

对于无向图 $G=\left(V,E\right)$ ,其中 $V=\left\{v_1,v_2,\cdots ,v_n\right\}$ 和 $E=\left\{e_1,e_2,\cdots ,e_m\right\}$ , 由

$\mathbf{I}=\left(b_{ij}\right)$ ,其中 $b_{ij}=\{\begin{array}{ll}0,& v_i\text{ 不与 }{e}_j\text{ 关联,}\\ 1,& v_i\text{ 与 }{e}_j\text{ 关联,并且 }{e}_j\text{ 不是环,}\\ 2,& v_i\text{ 与 }{e}_j\text{ 关联,并且 }{e}_j\text{ 是环 }\end{array}$(5.318)

给出的(n, m)型矩阵 $\mathbf{I}$ 称为关联矩阵.

对于有向图 $G=\left(V,E\right)$ ,其中 $V=\left\{v_1,v_2,\cdots ,v_n\right\}$ 和 $E=\left\{e_1,e_2,\cdots ,e_m\right\}$ , 关联矩阵 $\mathbf{I}$ 是一个由

$\mathbf{I}=\left(b_{ij}\right)$ ,其中 $b_{ij}=\{\begin{array}{ll}0,& v_i\text{ 不与 }{e}_j\text{ 关联,}\\ 1,& v_i\text{ 是 }{e}_j\text{ 的始点,并且 }{e}_j\text{ 不是环,}\\ -1,& v_i\text{ 是 }{e}_j\text{ 的终点,并且 }{e}_j\text{ 不是环,}\\ 0,& v_i\text{ 与 }{e}_j\text{ 关联,并且 }{e}_j\text{ 是环 }\end{array}$(5.319)

定义的(n, m)型矩阵.

11. 加权图

如果 $G=\left(V,E\right)$ 是一个图,而 $f$ 是对每条边指派一个实数的映射,那么将 (V, E, f)称为一个加权图,并且称 $f\left(c\right)$ 为边 $c$ 的权或

在应用中, 这些边的权表示由构建、维护或通信产生的费用.