离散数学03

路径、迹、路

路径（通路）

图G的一个非空点、边交替序列$W＝v_0e_1v_1e_2v_2…e_k v_k $称为一条从$v_0到v_k$的路径(通路)或$(v_0,v_k)$路径， 其中，$v_{i-1}$，$v_i$ 是$e_i $的端点(1≤i≤k)。 称$v_0$为W的起点，$v_k$为W的终点，$v_i (1≤i≤k－1)$为W的内点，k为W的路长。

$W^{-1}$是W逆转后的一条路径。

W的子序列（首尾是顶点）也是一条路径，成为W的节。

拼接两条路径，连着写就行，如：WW’.

简单图中，路径可以只写顶点即可，如$v_0v_1v_2…v_k $

迹与路

在一条路径中，若他们的边都互不相同，则称该路径为迹；若他们的顶点互不相同，则称该路径为路。

设 $v_0e_1v_1e_2v_2…e_kv_k$ 是图G中的一条路径且k≥1，如果$v_0 ＝v_k$，则称该路径为闭路径(环路Circle)，否则称为开路径。 特别地，若$v_0e_1v_1e_2v_2…e_kv_k是一条迹，k≥1，当v_0 ＝v_k$时称为闭迹，否则称为开迹。 闭迹也称为回路。

设$v_0e_1v_1e_2v_2…e_kv_0$是一条闭迹， 如果$v_0，v_1，…，v_{k-1}$互不相同， 则称该闭迹为圈或k圈， 且当k为偶数时称为偶圈， k为奇数时称为奇圈。

路一定是迹（显然），但迹不一定是路（如闭迹）.

自环和两条平行边都自成一圈.

定理

若图G（有限图）中每个顶点度数至少为２，则G中必含有圈。

构造性证明：设G的顶点集为$\{v_1,v_2,...,v_n\}$，

(1)若G中有自环或平行边，则显然成立。

(2)若G中无自环或平行边，则任取一个点$v_i$，因为其度数不小于2，所以其总边数至少为n，若G无圈，则总边数应为n-1，所以G中必含有圈。

连通

定义

设G是一个图，u，v∈V(G)， 如果存在从u到v的路，则称u，v是相连的或连通的，若G中任意两点都连通，则称 图G是连通的。

定理

图G中顶点之间的连通关系是一个等价关系

根据该关系可将V(G)划分成一些等价类V1，V2，…，Vn，每个Vi 导出的子图G(Vi )称为G的一个连通分支

G的连通分支数通常用ω(G)表示

G是连通的⇔ω(G)＝1

距离

定义

设u，v∈V(G)，若u，v连通，则称最短(u，v)路的长为u，v距离，记为d(u，v)， 当u，v不连通时，认为u，v的距离是∞

定理1

一个图G是二分图⇔G中不含奇圈。

不想证了，我忘了

定理2

设G是具有n个顶点的简单图，若G有ε条边，ω个连通分支，则

$$n-\omega\leq \varepsilon\leq\frac 1 2 (n-\omega)(n-\omega+1)$$

即

$$n-\omega\leq \varepsilon\leq C_{n-\omega+1}^2$$

证明

左边：

右边：

结论

• 边最少的情况：让所有的点自成一个连通分支，即没有边。
• 边最多的情况：让G中的$n-\omega+1$个点形成一个完全图的连通分支，其余$\omega-1$个点是孤立点。
• 当$\omega=1$（G是连通图）时，$\varepsilon\geq n-1$，即n个定点的连通图至少有n-1条边。
• 具有n个顶点，n－1条边的连通图称为最小连通图。

有向图中的通路及连通性

• 有向路径：一个非空有限点、弧交替序列 $W＝v_0a_1v_1a_2v_2…a_kv_k 对于i＝1，2，…，k，弧a_i 的头为v_i ，尾为v_{i-1}$.
• 有向路径$v_0a_1v_1a_2v_2…a_kv_k$也常用它的顶点序列$v_0v_1v_2…v_k$表示.
• 有向迹，有向路，有向回路，有向圈。有向回路与有向圈的区别参照回路与圈的区别。而且，有向回路不是路，因为路是要求顶点不同的.
• 存在有向(u，v)路，则称v是从u可达的.
• 若u，v互相可达，则称u，v是双向连通的.
• 若对D中任何两顶点，至少有一顶点可从另一顶点可达，则称D是单向连通图.
• 若D中任何两顶点都是双向连通的，则称D是双向连通图或强连通图.
• 若G的底图是连通图，则G是连通图，此时其中任意两点不一定是可达的.
• 双向连通关系是D的顶点集V上的一个等价关系.
• 双向分支或强连通分支.
• Ｄ强连通$\iff$Ｄ恰有一个强连通分支

定理3

内容

设G是带有相对于顶点顺序$v_1, v_2, . . . v_n$的邻接 矩阵A的图（允许带有向边或无向边，带多重边和环）。 从 $v_i 到v_j $的长度为r的不同通路的数目等于$A^r$ 的第 (i, j) 项，其中r是正整数。

解释

设G的邻接矩阵为A，记为$(a_{ij}^{(r)})_{n\times n}$，有下面一一对应关系

含义	矩阵中	图论中
$a_{ij}$	第i行，第j列	从 $v_i 到v_j $的通路数
®	A的指数	通路的长度

所以，我们可以通过矩阵运算来处理路的长度、条数问题。

证明

使用数学归纳法：

（1）当r=1时，$a_{ij}$取值0或1，表示$v_i与v_j$是否邻接，显然成立。

（2）假设当r=k时，对应关系成立，那么

我们取其中的一步分析：

$$\begin{bmatrix} a_{i1}^{(k)}&a_{i2}^{(k)}\cdots a_{ij}^{(k)}\cdots a_{in}^{(k)} \end{bmatrix} \begin{bmatrix} a_{1j}^{(1)}\\ a_{2j}^{(1)}\\ \vdots\\ a_{ij}^{(1)}\\ \vdots\\ a_{nj}^{(1)} \end{bmatrix}$$

$$=\underset{s=1}{\overset{n}{\sum}}a_{is}^{(k)}a_{sj}^{(1)}$$

由于从$v_i$到$v_s$已经有通路，如果$v_s$与$v_j$邻接，那么从$v_i$到$v_j$的路径数就是从$v_i$到$v_s$的路径数；

然后，遍历所有这样的$v_s$求和，这样就得到了所有从$v_i$到$v_j$的路径数。

应用

如果我们想查找从$v_i$到$v_j$长度为r的路径数的话，只需要计算$A^r$，然后查看$a_{ij}$的值即可。

一点概念

有时删除一个顶点和它所关联的边，就产生带有比原图更多的连通分支的子图。把这样的顶点称为割点（或节点）。

从连通图里删除割点，就产生不连通的子图。 同理，把一旦删除就产生带有比原图更多的连通分支的子图的边称为割边或桥。

我们还可以使用通路特征来判断同构。