# 路与圈

# 途径 (way)

在图 $G=(V,E,\gamma)$ 中，G 的有限非空点边交错序列
$w=v_0,e_1,v_1,e_2,v_2,\dots,e_k,v_k$ ，若满足以下条件：
1. $\gamma(e_i)=\{v_{i-1},v_i\}$ （或 $(v_{i-1},v_i)(1\leq i \leq k)$ 。
2. 当 $e_i$ 和 $e_{i+1}$ 不是自环时，有 $e_{i+1}\neq e_i(1\leq i \leq n)$ （对于无向图）。

则称其为 G 的一条从 $v_0$ 到 $w$ 的途径， $v_0$ 称为途径 $w$ 的起点， $v_k$ 称为途径 $w$ 的终点，而 $k$ 称为途径的长度。

# 路 (path)、圈 (cycle)

设 $G=(V,E,)$ 是一图， $w=（v_0,e_1,v_1,e_2,v_2,\dots,e_k,v_k）$ 是一途径。

若 $v_0\ne v_k$ ，则称此途径 w 是从 v0 到 vk 的一条路；记为
$P=（v_0,e_1,v_1,e_2,v_2,\dots,e_k,v_k）$ ，并称 k 为路 P 的长度 (即 | P|=k)。
若 $v_0= v_k$ ，则称此途径 w 是一个圈；记为
$C=（v_0,e_1,v_1,e_2,v_2,\dots,e_k,v_k）$ ，并称 k 为圈 C 的长度 (即 | C|=k)。

# 可达性 (reachablility)、连通性 (connectivity)

设 $G=(V,E,)$ 是一无向图， $u,v\in V$

若存在着从结点 u 到结点 v 的一条路 P，则称从结点 u 到结点 v 是可达的；
若图 G 中任何两结点都是可达的，则称此图 G 是连通的。否则，称图 G 是非连通的

可达概念可以看作结点间的一个二元关系 —— 可达关系；

在无向图中，规定任一结点自己到自己总是可达的，即可达关系具有自反性；

在无向图中，可达性是相互的，从结点 u 可达结点 v，则从结点 v 也可达结点 u ，即可达关系是对称的；

可达关系是传递的，即若从结点 u 可达结点 v，又从结点 v 可达结点 w，则从结点 u 也可达结点 w；

一般地，当从结点 u 可达结点 v 时，它们之间不一定只有一条路，可能会有若干条路。称从结点 u 到结点 v 的所有路中长度最短的那一条为短程线，并将短程线的长度叫做从结点 u 到结点 v 的距离，用 d (u, v) 表示。

规定：
1. $d(u, u)=0$ ；
2. 若结点 u 到结点 v 不可达，则 $d(u, v)=\infty$ 。

短程线不一定是唯一的，有时可能会有好几条；
按照通常的理解，距离概念一般都具有下列性质：

非负性： $d(u, v)\geq0$ ；
对称性； $d(u, v)= d(v, u)$ ；
三角不等式： $d(u, v)+ d(v, w) \geq d(u, w)$ \

对无向图，上述性质全成立；
对有向图来说，第二条，对称性质不成立。

连通性是有强弱之分的；
(1) 若图 G 中任二结点间都至少存在着一条路可达，则称图 G 是 1 - 连通的；
(2) 若图 G 中任二结点间都至少存在着 k 条不同的路可达，则称图 G 是 k - 连通的 $(k\geq2)$ ；

通常所说的连通性实际上是指 1 - 连通。 1 - 连通的连通性较差，重要的信道图网络，比如军事信道图网络，其连通性至少在 2 - 连通以上。

# 简单路 (simple path) 简单圈 (simple cycle)

无重复边的路称为简单路；
无重复边的圈称为简单圈。

# 初级路 (elementary path) 初级圈 (elementary cycle)

无重复点的路称为初级路；
无重复点的圈称为初级圈

# 定理 1

设 G=(V,E) 为一简单图，若 | V|= n ，则

G 中任一初级路的长度均不超过 n-1；
G 中任一初级圈的长度均不超过 n。

# 连通支 (分图 (connected component))

无向图中极大的连通子图称为一个连通支。

# 强连通单向连通弱连通设

设 $G=(V,E,)$ 是一有向图。如果 G 中

任意两结点间都是相互可达的，则称图 G 是强连通的 (strongly connected)；
任意两结点间至少有一结点可达另一结点，则称图 G 是单向连通的 (single directed connected)；
略去边的方向后，任意两结点间都是可达的 (即图 G 的无向图是连通的)，则称图 G 是弱连通的 (weakly connected)。

・强连通 $\implies$ 单向连通；反之？单向连通 $\implies$ 弱连通；反之？

# 强分图单向分图弱分图

设 $G=(V,E,)$ 是一简单有向图。

称 G 的极大的强连通子图为 G 的强连通支 (强分图 ( strongly fragments))；
称 G 的极大的单向连通子图为 G 的一个单向连通支 (单向分图 (single directed fragments))；
称 G 的一个极大的弱连通子图为 G 的一个弱连通支 (弱分图 (weakly fragments))。

有向图中的强连通性建立了图 G 的结点集 V 上的一个等价关系，因而诱导出了图 G 的结点集 V 上的一个划分，图 G 的每一个强连通支就是一个 “划分块”；但是却不能在图 G 的边集 E 上建立一个划分；

有向图中的弱连通性在图 G 的结点集 V 上以及边集 E 上都建立了一个等价关系，因而在图 G 的结点集 V 上以及边集 E 上都诱导出了一个划分，图 G 的每一个弱连通支就是一个 “划分块”；

有向图中的单向连通性，由于单向可达关系不具有对称性，所以这种关系并不能在图 G 的结点集 V 上及边集 E 上建立一个等价关系，因而也不能在图 G 的结点集 V 上及边集 E 上诱导出一个划分，图 G 的每一个单向连通支也就不会是 (由某种等价关系所确定的) 一个 “划分块。

# 定理 2

每一个结点及每一条边都恰在一弱连通支中；
每一个结点都恰在一个强连通支中；
每一个结点、每一条边都至少属于一个单向连通支。