图

一、图的基本概念

1、图

定义：一个图(Graph)是一个序偶$\langle V,E \rangle$，记为$G= \langle V,E \rangle$，其中：
（1）$V= { v_1,v_2,\cdots v_n }$是有限非空集合，$v_i$称为结点(Nodal Point)，简称点(Point)，$V$称为结点集(Nodal Set)。
（2）$E$是有限集合，称为边集(Frontier Set)。$E$中的每个元素都有$V$中的结点对与之对应，称之为边(Edge)。
与关系类似，图也有集合表示，图形表示，邻接矩阵三种表示方法。

一些名词：在图$G= \langle V,E \rangle$中，
(1)若两个结点$v_i$和$v_j$是边$e$的端点，则称$v_i$与$v_j$互为邻接点(Adjacent Point)，否则$v_i$与$v_j$不邻接
(2)具有公共结点的两条边称为邻接边(Adjacent Edge)
(3)两个端点相同的边称为环(Ring)或自回路(Self-Loop)
(4)图中不与任何结点相邻接的结点称为孤立结点(Isolated Point)
(5)仅由孤立结点组成的图称为零图(Null Graph)
(6)仅含一个结点的零图称为平凡图(Trivial Graph)
(7)含有$n$个结点，$m$条边的图，称为$(n, m)$图
(8)在有向图中，两结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边(Parallel Edge)；在无向图中，两结点间(包括结点自身间)若有几条边，则这几条边称为平行边。
(9)两结点$a$、$b$间相互平行的边的条数称为边$( a,b )$或$\langle a,b \rangle$的重数。

2、图的操作

操作	符号表示	具体操作
删除边	$G-e= \langle V,E- { e } \rangle$	直接从图中去掉边$e$
删除边集	$G-E’= \langle V,E-E’ \rangle$
删除结点	$G-v= \langle V- { v } ,E- { e\mid v关联e } \rangle$	去掉结点$v$及其关联的所有边
删除结点子集	$G-V’= \langle V-V’,E- { e\mid v\in V’\wedge v关联e } \rangle$
边的收缩	$G\setminus e$	去掉边$e$，再将两端点变为一个新结点$w$
加新边	$G\cup (u,v)$	在$u$和$v$之间增加一条边

3、图的分类

(1)按边有无方向分类：
每条边都是无向边的图称为无向图(Undirected Graph)；每条边都是有向边的图称为有向图(Directed Graph)；有些边是无向边，而另一些边是有向边的图称为混合图(Mixed Graph)。环既可以看成有向边，也可以看成无向边。
(2)按有无平行边分类：
含有平行边的图称为多重图；非多重图称为线图；无环的线图称为简单图。
(3)按边或结点是否含权分类：
赋权图(Weight Graph)G是一个三重组$\langle V,E,g \rangle$或四重组$\langle V,E,f,g \rangle$，其中$V$是结点集合，$E$是边的集合，$f$是从$V$到非负实数集合的函数，$g$是从$E$到非负实数集合的函数。非赋权图称为无权图。

4、子图与补图

子图：
设有图$G= \langle V,E \rangle$和图$G_1= \langle V_1,E_1 \rangle$。
(1)若$V_1\subseteq V$，$E_1\subseteq E$，则称$G_1$是$G$的子图，记为$G_1\subseteq G$；
(2)若$G_1\subseteq G$，且$G_1\ne G$(即$V_1\subset V$或$E_1\subset E$)，则称$G_1$是$G$的真子图，记为$G_1\subset G$；
(3)若$V_1 = V$，$E_1\subseteq E$，则称$G_1$是$G$的生成子图；
(4)设$V_2\subseteq V$且$V_2\ne \emptyset$，以$V_2$为结点集，以两个端点均在$V_2$中的边的全体为边集的$G$的子图，称为$V_2$导出的$G$的子图，简称$V_2$的导出子图。

注意：生成子图与$G$有相同的结点集，导出子图可以由$G$删除结点子集得到。每个图都是它自己的生成子图，导出子图和子图。

题型：子图类型的判断

完全图与补图：设$G= \langle V,E \rangle$为一个具有$n$个结点的无向简单图，如果$G$中任意两个结点间都有边相连，则称$G$为无向完全图(Undirected Complete Graph)，简称$G$为完全图(Complete Graph)，记为$K_n$。
设$G= \langle V,E \rangle$为一个具有$n$个结点的有向简单图，如果$G$中任意两个结点间都有两条方向相反的有向边相连，则称$G$为有向完全图(Directed Complete Graph)，在不发生误解的情况下，也记为$K_n$。
设$G= \langle V,E \rangle$为简单图，$G’= \langle V,E_1 \rangle$为完全图，则称$G_1= \langle V,E_1-E \rangle$为$G$的补图，记为$G^C$。

注意：对于完全图来说，其邻接矩阵除主对角元为0外，其它元素均为1；计算补图时，先将原图补全为完全图，再删去原图的所有边；完全图的补图是$n$个结点的零图。

题型：补图的计算

二、握手定理

度数：
(1)图$G= \langle V,E \rangle$中以结点$v\in V$为端点的边数(有环时计算两次)称为结点$v$的度数(Degree)，简称度，记为$deg(v)$。
(2)有向图$G= \langle V,E \rangle$中以结点$v$为始点的边数称为$v$的出度(Out-Degree)，记为$deg^+(v)$；以结点$v$为终点的边数称为$v$的入度(In-Degree)，记为$deg^-(v)$。显然，$deg(v) = deg^+(v)+deg^-(v)$。
(3)对于图$G= \langle V,E \rangle$，度数为1的结点称为悬挂结点(Hanging Point)，以悬挂结点为端点的边称为悬挂边(Hanging Edge)。

利用邻接矩阵计算度数：
(1)若$G$是无向图，则$A$中第$i$行元素是由结点$vi$为端点的边所决定，其中为1的元素数目等于$v_i$的度数，即$deg(v_i)=a{ii}+\sum{k=1}^{n}a{ik}$或$deg(vi)=a{ii}+\sum{k=1}^{n}a{ki}$。
(2)若$G$是有向图，则$A$中第$i$行元素是由结点$vi$为始点的边所决定，其中为1的元素数目等于$v_i$的出度，即$deg^+(v_i)=\sum{k=1}^{n}a{ik}$；$A$中第$i$列元素是由$v_i$为终点的边决定，其中为1的元素数目等于$v_i$的入度，即$deg^-(v_i)=\sum{k=1}^{n}a_{ki}$。

题型：结点度数的计算

握手定理：图中结点度数的总和等于边数的二倍，即设图$G= \langle V,E \rangle$，则有$\sum_{v\in V}^{} deg(v)=2 | E |$。

推论：图中度数为奇数的结点个数为偶数。

定理：有向图中各结点的出度之和等于各结点的入度之和，等于边数，即设有向图$G= \langle V,E \rangle$，则有$\sum{v\in V}^{} deg^+(v)=\sum{v\in V}^{} deg^-(v)= | E |$。

度数序列：设$V= { v_1,v_2,v_3,\cdots v_n }$为图G的结点集，称$(deg(v_1), deg(v_2),\cdots, deg(v_n))$为$G$的度数序列(Degree Sequence)。

三、图的同构

同构：设两个图$G= \langle V,E \rangle$和$G’= \langle V’,E’ \rangle$，如果存在双射函数$g:V\to V’$，使得对于任意的$e = (v_i, v_j)$(或者$\langle v_i,v_j \rangle$)$\in E$当且仅当$e’=(g(v_i),g(v_j))$(或者$\langle g(v_i),g(v_j) \rangle$)$\in E’$，并且$e$与$e’$的重数相同，则称$G$与$G’$同构(Isomor- phism)，记为$G\cong G’$。

图同构的必要条件：
(1)结点数目相同；
(2)边数相同；
(3)度数相同的结点数相同。

图不同构的充分条件：
(1)结点数目不同；
(2)边数不同；
(3)度数相同的结点数不同。

注意：证明图同构，只需给出一种满足的双射函数即可；证明图不同构，首先考虑必要条件是否满足，均满足时可采用反证法。

题型：图同构的判断与证明

四、通路与回路

1、概念

定义：给定图$G= \langle V,E \rangle$中结点和边相继交错出现的序列$\Gamma =v0e_1v_1e_2v_2\cdots e_kv_k$。
(1)若$\Gamma$中边$e_i$的两端点是$v{i-1}$和$vi$（$G$是有向图时要求$v{i-1}$与$v_i$分别是$e_i$的始点和终点），$i = 1, 2,\cdots , k$，则称$\Gamma$为结点$v_0$到结点$v_k$的通路(Entry)。$v_0$和$v_k$分别称为此通路的始点和终点，统称为通路的端点。 通路中边的数目k称为此通路的长度。当$v_0 = v_n$时，此通路称为回路(Circuit)。

类型：若通路中的所有边互不相同，则称此通路为简单通路(Simple Entry)或一条迹；若回路中的所有边互不相同，则称此回路为简单回路(Simple Circuit)或一条闭迹。若通路中的所有结点互不相同（从而所有边互不相同），则称此通路为基本通路(Basic Entry)或者初级通路、路径；若回路中除$v_0 = v_k$外的所有结点互不相同（从而所有边互不相同），则称此回路为基本回路(Basic Circuit)或者初级回路、圈。

注意：回路也是一种通路；基本通路（回路）一定是简单通路（回路），但反之不真。

题型：通路类型的判断

2、计算

通路数目的计算定理：设$G= \langle V,E \rangle$为线图，$V= { v1,v_2,v_3,\cdots v_n }$，$A = (a{ij})_{n\times n}$为$G$的邻接矩阵，

$$A^m = (a_{ij}^{(m)})_{n\times n} = \underbrace{ \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix} \cdot \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix} \cdot \cdots \cdot \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix}}_{m\text{次}}$$

则：$a{ij}^{(m)}$为从结点$v_i$到$v_j$的长度为$m$的通路数目；$a{ii}^{(m)}$为从结点$vi$到自身的长度为$m$的回路数目；$\sum{i=1}^{n} \sum{j=1}^{n}a{ij}^{(m)}$为$G$中长度为$m$的通路（含回路）总数。

题型：通路数目的计算

3、可达与距离

定义：在图$G= \langle V,E \rangle$中，$v_i,v_j\in V$。
（1）如果$v_i$到$v_j$存在通路，则称$v_i$到$v_j$是可达的，否则称$v_i$到$v_j$不可达。规定：任何结点到自己都是可达的。
（2）如果$v_i$到$v_j$可达，则称长度最短的通路为$v_i$到$v_j$的短程线(Geodesic)；$v_i$到$v_j$的短程线的长度称为$v_i$到$v_j$的距离(Distance)，记为$d(v_i, v_j)$。如果$v_i$到$v_j$不可达，则通常记为$d(v_i, v_j) = \infty$。

显然，d(vi, vj)满足下列性质：
$d(v_i, v_j)\ge 0$；
$d(v_i, v_i)=0$；
$d(v_i,v_k)+d(v_k,v_j)\ge d(v_i,v_j)$；
对于无向图，一定有若$v_i$到$v_j$可达，则$v_j$到$v_i$可达；也有$d(v_i, v_j) = d(v_j, v_i)$；
对于有向图，若$v_i$到$v_j$可达，$v_j$到$v_i$不一定可达；也不一定有$d(v_i, v_j) = d(v_j, v_i)$。

定理：在一个具有$n$个结点的图中，如果从结点$v_i$到结点$v_j$（$v_i\ne v_j$）存在一条通路，则从$v_i$到$v_j$存在一条长度不大于$n-1$的通路。
推论：在一个具有$n$个结点的图中，如果从结点$v_i$到结点$v_j$（$v_i\ne v_j$）存在一条通路，则从$v_i$到$v_j$存在一条长度不大于$n-1$的基本通路。
定理：在一个具有$n$个结点的图中，如果存在经过结点$v_i$的回路，则存在一条经过$v_i$的长度不大于$n$的回路。
推论：在一个具有$n$个结点的图中，如果存在经过结点$v_i$的回路，则存在一条经过$v_i$的长度不大于$n$的基本回路。

可达的判断与距离的计算：设矩阵$Bm=I+A+A^2+A^3+\cdots +A^m$（$I$为$n$阶单位阵），则$B_m$中的元素$b{ij}^{(m)}$表示图$G$中结点$vi$到$v_j$的长度小于等于$m$的通路总数，若$i = j$，$b{ii}^{(m)}$为$G$中结点$vi$到自身的长度小于等于$m$的回路总数。
定理：设$G= \langle V,E \rangle$为线图，$V= { v_1,v_2,v_3,\cdots v_n }$，若$b{ij}^{(n-1)} >0$，那么从$v_i$到$v_j$可达，否则不可达；并且

$$d(v_i,v_j)=\{\begin{matrix}\infty &,& (a_{ij}^{(1)}=0\wedge a_{ij}^{(2)}=0 \wedge \cdots \wedge a_{ij}^{(n-1)}=0)\vee (b_{ij}^{(n-1)}=0) \\k &,& k=min \{ m\mid a_{ij}^{(m)}\ne 0,m=1,2\cdots ,n-1 \} \end{matrix}.(i\ne j)$$

可达性矩阵：设$G= \langle V,E \rangle$是一个线图，其中$V= { v1,v_2,v_3,\cdots v_n }$，并假定结点已经有了从$v_1$到$v_n$的次序，称$n$阶方阵$P = (p{ij}){n\times n}$为图$G$的可达性矩阵(Accessibility Matrix)，其中$p{ij}={\begin{matrix} 1, & v_i到v_j可达\ 0, & 否则\end{matrix}.(i,j=1,2,\cdots,n)$；$P=I\vee A\vee A^{(2)}\vee A^{(3)}\vee \cdots \vee A^{(n-1)}$。$A^{(i)}$表示$A$的布尔积$i$次幂。

题型：可达的判断与距离的计算

4、无向赋权图的最短通路

Dijkstra算法：在赋权图中，边的权也称为边的长度，一条通路的长度指的就是这条通路上各边的长度之和。从结点vi到vj的长度最小的通路，称为vi到vj的最短通路。算法的基本思路如下：
(1)初始化：将$v_1$置为$P$标号，$d(v_1)＝0$，$P＝ { v_1 }$，对于$\forall v_i\in V$，$i \ne 1$，置$v_i$为$T$标号，即$T＝V－P$且$d(v_i)={\begin{matrix} w(v_1,v_i), & (v_1,v_i)\in E & \ \infty, & (v_1,v_i)\notin E &\end{matrix}.$
(2)找最小：寻找具有最小值的T标号的结点。若为$v_k$，则将$v_k$的$T$标号改为$P$标号，且$P=P\cup { v_k }$，$T=T- { v_k }$。
(3)检查修改：修改与$v_k$相邻的结点的$T$标号值。$\forall v_i\in V$，如果$d(v_k)+w(v_k,v_i)<d(v_i)$，则将$d(v_i)$修改为$d(v_k)+w(v_k,v_i)$。
(4)重复：循环进行(2)(3)步骤，直到所求$v_n\in P$，此时$d(v_n)$即为通路的最小值。

	第一次	第二次	第三次	第四次	第六次	第七次
$v_2$	$1(1\to 2)$	$P$	$P$	$P$	$P$	$P$
$v_3$	$4(1\to 3)$	$3(1\to 2\to 3)$	$P$	$P$	$P$	$P$
$v_4$	$\infty$	$8(1\to 2\to 4)$	$8(1\to 2\to 4)$	$7(1\to 2\to 3\to 5\to 4)$	$P$	$P$
$v_5$	$\infty$	$6(1\to 2\to5)$	$4(1\to 2\to 3\to 5)$	$P$	$P$	$P$
$v_6$	$\infty$	$\infty$	$\infty$	$10(1\to 2\to 3\to 5\to 6)$	$9(1\to 2\to 3\to 5\to 4\to 6)$	$P$

题型：利用Dijkstra算法求两点间最短通路

Floyd算法：从矩阵$D^{(0)}＝(w{ij}){n\times n}$（这里$w{ij}＝w(v_i,v_j)$，称为图的长度矩阵）开始，依次构造出$n$个矩阵$D^{(1)}, D^{(2)},\cdots ,D^{(n)}$，这里$n$为图中结点的个数。第$k$个矩阵$D^{(k)}＝(d{ij}^{(k)}){n×n}$的元素$d{ij}^{(k)}$表示从结点$vi$到$v_j$而中间结点仅属于$v_1$到$v_k$的$k$个结点的所有通路中的最短通路长度。若已知$D^{(k-1)}＝(d{ij}^{(k-1)}){n×n}$，则$D^{(k)}＝(d{ij}^{(k)}){n×n}$的元素规定为$$d{ij}^{(k)}=min { d{ij}^{(k-1)},d{ik}^{(k-1)}+d{kj}^{(k-1)} } $$运算过程从$k＝1$开始，让$i$和$j$分别取遍从$1$到$n$的所有值，然后$k$增加$1$，如此反复进行，直到$k＝n$为止。这时$D^{(n)}＝(d{ij}^{(n)}){n×n}$的元素$d{ij}^{(n)}$就是从$v_i$到$v_j$的最短通路长度。

$$\begin{pmatrix} 0 & 12 & \infty & \infty & \infty & 16 & 14\\ 12 & 0 & 10 & \infty & \infty & 7 & \infty\\ \infty & 10 & 0 & 3 & 5 & 6 & \infty\\ \infty & \infty & 3 & 0 & 4 & \infty & \infty\\ \infty & \infty & 5 & 4 & 0 & 2 & 8\\ 16 & 7 & 6 & \infty & 2 & 0 & 9\\ 14 & \infty & \infty & \infty & 8 & 9 & 0\end{pmatrix}$$

$$\begin{pmatrix} 0 & 12 & \infty & \infty & \infty & 16 & 14\\ 12 & 0 & 10 & \infty & \infty & 7 & {\color{Green} 26}\\ \infty & 10 & 0 & 3 & 5 & 6 & \infty\\ \infty & \infty & 3 & 0 & 4 & \infty & \infty\\ \infty & \infty & 5 & 4 & 0 & 2 & 8\\ 16 & 7 & 6 & \infty & 2 & 0 & 9\\ 14 & {\color{Green} 26} & \infty & \infty & 8 & 9 & 0\end{pmatrix}$$

$$\begin{pmatrix} 0 & 12 & {\color{Green} 22} & \infty & \infty & 16 & 14\\ 12 & 0 & 10 & \infty & \infty & 7 & 26\\ {\color{Green} 22} & 10 & 0 & 3 & 5 & 6 & {\color{Green} 36}\\ \infty & \infty & 3 & 0 & 4 & \infty & \infty\\ \infty & \infty & 5 & 4 & 0 & 2 & 8\\ 16 & 7 & 6 & \infty & 2 & 0 & 9\\ 14 & 26 & {\color{Green} 36} & \infty & 8 & 9 & 0\end{pmatrix}$$

$$\begin{pmatrix} 0 & 12 & 22 & {\color{Green} 25} & {\color{Green} 27} & 16 & 14\\ 12 & 0 & 10 & {\color{Green} 13} & {\color{Green} 15} & 7 & 26\\ 22 & 10 & 0 & 3 & 5 & 6 & 36\\ {\color{Green} 25} & {\color{Green} 13} & 3 & 0 & 4 & {\color{Green} 9} & {\color{Green} 39}\\ {\color{Green} 27} & {\color{Green} 15} & 5 & 4 & 0 & 2 & 8\\ 16 & 7 & 6 & {\color{Green} 9} & 2 & 0 & 9\\ 14 & 26 & 36 & {\color{Green} 39} & 8 & 9 & 0\end{pmatrix}$$

$$\begin{pmatrix} 0 & 12 & 22 & 25 & 27 & 16 & 14\\ 12 & 0 & 10 & 13 & 15 & 7 & 26\\ 22 & 10 & 0 & 3 & 5 & 6 & 36\\ 25 & 13 & 3 & 0 & 4 & 9 & 39\\ 27 & 15 & 5 & 4 & 0 & 2 & 8\\ 16 & 7 & 6 & 9 & 2 & 0 & 9\\ 14 & 26 & 36 & 39 & 8 & 9 & 0\end{pmatrix}$$

$$\begin{pmatrix} 0 & 12 & 22 & 25 & 27 & 16 & 14\\ 12 & 0 & 10 & 13 & 15 & 7 & {\color{Green} 23}\\ 22 & 10 & 0 & 3 & 5 & 6 & {\color{Green} 13}\\ 25 & 13 & 3 & 0 & 4 & {\color{Green} 6} & {\color{Green} 12} \\ 27 & 15 & 5 & 4 & 0 & 2 & 8\\ 16 & 7 & 6 & {\color{Green} 6} & 2 & 0 & 9\\ 14 & {\color{Green} 23} & {\color{Green} 13} & {\color{Green} 12} & 8 & 9 & 0\end{pmatrix}$$

$$\begin{pmatrix} 0 & 12 & 22 & {\color{Green} 22} & {\color{Green} 18} & 16 & 14\\ 12 & 0 & 10 & 13 & {\color{Green} 9} & 7 & {\color{Green} 16}\\ 22 & 10 & 0 & 3 & 5 & 6 & 13\\ {\color{Green} 22} & 13 & 3 & 0 & 4 & 6 & 12 \\ {\color{Green} 18} & {\color{Green} 9} & 5 & 4 & 0 & 2 & 8\\ 16 & 7 & 6 & 6 & 2 & 0 & 9\\ 14 & {\color{Green} 16} & 13 & 12 & 8 & 9 & 0\end{pmatrix}$$

$$\begin{pmatrix} 0 & 12 & 22 & 22 & 18 & 16 & 14\\ 12 & 0 & 10 & 13 & 9 & 7 & 16\\ 22 & 10 & 0 & 3 & 5 & 6 & 13\\ 22 & 13 & 3 & 0 & 4 & 6 & 12 \\ 18 & 9 & 5 & 4 & 0 & 2 & 8\\ 16 & 7 & 6 & 6 & 2 & 0 & 9\\ 14 & 16 & 13 & 12 & 8 & 9 & 0\end{pmatrix}$$

题型：求简单无向赋权图中的所有最短通路

五、图的连通性

连通图与非连通图：若无向图$G$中的任何两个结点都是可达的，则称$G$是连通图(Connected Graph)，否则称$G$是非连通图(Unconnected Graph)或分离图(Separated Graph)。无向完全图$K_n(n\ge 1)$都是连通图，而多于一个结点的零图都是非连通图。利用邻接矩阵$A$和可达性矩阵$P$，显然有：非平凡无向线图$G$是连通图当且仅当它的可达性矩阵$P$的所有元素均为1。

可达等价定理：无向图$G= \langle V,E \rangle$中结点之间的可达关系$R$定义如下：$R = { \langle u,v \rangle \mid u, v\in V，u到v可达 }$，则$R$是$V$上的等价关系。

注意：由于有向图中边都有方向性，因此有向图结点之间的可达关系仅仅具有自反性和传递性，而不具有对称性。因此，有向图中可达关系不是等价关系。

连通分支：无向图$G= \langle V,E \rangle$中结点之间的可达关系$R$的每个等价类导出的子图都称为$G$的一个连通分支(Connected Component)。用$p(G)$表示$G$中的连通分支个数。无向图$G$是连通图当且仅当$p(G) = 1$；每个结点和每条边都在且仅在一个连通分支中。

定义：设$G= \langle V,E \rangle$是一个有向图，
(1)略去$G$中所有有向边的方向得无向图$G’$，如果无向图$G’$是连通图，则称有向图$G$是连通图或称为弱连通图。否则称$G$是非连通图；
(2)若$G$中任何一对结点之间至少有一个结点到另一个结点是可达的，则称$G$是单向连通图；
(3)若$G$中任何一对结点之间都是相互可达的，则称$G$是强连通图。

注意：强连通图一定是单向连通图；单向连通图一定是（弱）连通图。

强连通图的充要条件：有向图$G$是强连通图的充分必要条件是：$G$中存在一条经过所有结点的回路。
单向连通图的充要条件：有向图$G$是单向连通图的充分必要条件是：$G$中存在一条经过所有结点的通路。

题型：有向图连通性的判断

有向图连通性的判断方法：
(1)能够找到一条经过所有结点的回路（可以经过重复的边或结点），则是强连通图。
(2)能够找到一条经过所有结点的通路（可以经过重复的边或结点），则是单向连通图。
(3)将有向边看作无向边的无向图是连通图，则是弱连通图；否则是非连通图。
(4)利用邻接矩阵$A$和可达性矩阵$P$来判断有向图的连通性，适用于计算机处理。(具体来说，有向线图$G$是强连通图当且仅当它的可达性矩阵$P$的所有元素均为1；有向线图$G$是单向连通图当且仅当它的可达性矩阵$P$及其转置矩阵$P^T$经过布尔并运算后所得的矩阵$P’= P\vee P^T$中除主对角元外其余元素均为1；有向线图$G$是弱连通图当且仅当它的邻接矩阵$A$及其转置矩阵$A^T$经布尔并运算所得的矩阵$A’= A\vee A^T$作为邻接矩阵而求得的可达性矩阵$P’$中所有元素均为1。)

连通分支：在有向图$G= \langle V,E \rangle$中，设$G’$是$G$的子图，如果
(1)$G’$是强连通的（单向连通的、弱连通的）；
(2)对任意$G’’\subseteq G$，若$G’\subset G’’$，则$G’’$不是强连通的（单向连通的、弱连通的）；
那么称$G’$为$G$的强连通分支（单向连通分支、弱连通分支）(Strongly/Unilaterally/Weakly Connected Component)，或称为强分图（单向分图、弱分图）。

注意：
(1)如果不考虑边的方向，弱连通分支对应相应的无向图的连通分支。
(2)注意把握强（单向、弱）连通分支的极大性特点，即任意增加一个结点就不是强（单向、弱）连通的了。
(3)与无向图的连通性类似，强（弱）连通分支确定的关系也是等价关系，但由于单向连通分支确定的关系不具有传递性，只是一个相容关系。

题型：有向图中连通分支的计算

有向图中连通分支的计算方法：
(1)从某个结点开始逐渐增加结点，使得这些结点导出的子图是强（单向或弱）连通的，直到不能增加结点为止。
(2)强（弱）连通分支相对简单，因为每个结点在且仅在一个强（弱）连通分支中；而单向连通分支的计算比较难，因为某些结点可能在多个单向连通分支中。

定理：在有向图$G= \langle V,E \rangle$中，它的每一个结点位于且仅位于一个强（弱）连通分支中。
在有向图$G= \langle V,E \rangle$中，它的每一个结点至少位于一个单向连通分支中。
在有向图$G= \langle V,E \rangle$中，它的每一条边至多在一个强连通分支中；至少在一个单向连通分支中；在且仅在一个弱连通分支中。

六、习题

1、邻接矩阵的几大应用

(1)利用邻接矩阵求度数：对于无向图，$vi$点的度数等于邻接矩阵第$i$行所有元素的和，再加上$a{ii}$。对于有向图，$vi$的出度等于第$i$行所有元素的和，入度等于第$i$列所有元素的和。
(2)利用邻接矩阵求长度为$m$的通路数量：先计算邻接矩阵$A$的$m$次幂，$a{ij}^{(m)}$为从结点$vi$到$v_j$的长度为$m$的通路数目；$a{ii}^{(m)}$为从结点$v_i$到自身的长度为$m$的回路数目。
(3)利用邻接矩阵求可达性矩阵：$P=I\vee A\vee A^{(2)}\vee A^{(3)}\vee \cdots \vee A^{(n-1)}$。$A^{(i)}$表示$A$的布尔积$i$次幂。
(4)利用邻接矩阵判断有向图的连通性。

2、同构与不同构的证明

证明图同构，只需给出一种满足的双射函数即可；证明图不同构，首先考虑必要条件是否满足，均满足时可采用反证法。

3、生成子图与导出子图的判断与计算

生成子图可以由原图删除边集得到，导出子图可以由原图删除点集得到。