链、路、圈、回

                     

贡献者： 零穹

预备知识　图

　　 本节介绍图中一类特殊的结构——链，而路、圈和回都是一类特殊的链。

1. 定义

　　 [1] 生活中我们习惯把环环相扣的东西叫做链，图论中把点边交叉组成的序列称作链（不同位置的点和边可以相同）。

定义 1　链

　　 设 G=(V,E,φ) 是一个图，vi∈V,ej∈E,i=0,⋯,k,j=1⋯n 分别是其上的 n+1 个点和 n 条边。若序列1

(1)W=v0e1v1e2⋯vk−1envn, 
对所有的 i=0,⋯,k 满足 vi−1,vi∈ei，则称 W 是 G 中的端点为 v0,vn 长为 n 的链（chain）或途径（walk），并且 W 连接 v0,vn。除 v0,vn 的 W 中的点称作 W 的内点（internal vertex）。端点为 x,y 的链通长简称为 xy 链。

　　 对于简单图而言，其链显然可以通过指定端点确定。

　　 人们习惯将不同时刻物体的位置在时空坐标系下的曲线叫做物体的轨迹，而将空间坐标系下的物体的运动曲线称为路径。尽管不同时刻物体可以在同一空间点，使得它在空间上的路径是可以相交的，但是它的轨迹始终都是不能相交的（因为时间只能往前）。在图中人们习惯将边彼此不同的链称为迹，点彼此不同的链称为路，而端点相同的 “路” 称为圈。

定义 2　迹，路，圈，回

　　 设 W 是图 G 的链，若组成 W 的边彼此不同，则称 W 是迹(trail)。若组成 W 的边彼此不同，则称 W 是路(path)。端点相同内点不同的链称为圈(cycle)。端点相同的迹称为回（circult）。对应端点 x,y 的迹和路称为 xy 迹，xy 路。

　　 注：有的文献也会把圈称为闭路，这时候的路就被定义为内点互不相同的迹了。还是一样的，遇到这种情况时只需要注意文献所遵循的约定就好了。

例 1　无圈图无环，无回图无环

　　 试证明：无圈图，无回图都是简单图。

　　 证明： 1.设 G 有环 e，其端点为 x。则 xex 是 G 的圈又是 G 的回。与 G 无圈（或无环）矛盾。

　　 2.设 x,y∈V(G)，且有以它们为端点的两不同边 e1,e2，那么 xe1ye2x 是环又是回。与 G 无圈（或无环）矛盾。

　　 证毕！

2. 相关定义

定义 3　独立

　　 若 W1,W2 是两条链，若 W1,W2 的一条链不包含另一条链的内点，则称它们是独立的（independent）。

定义 4　H-链

　　 设 H 是图，W 是 G 的链，若 W 有端点属于 H，而内点不属于 H，则称 W 为 H-链（H-chain）。

　　 链的连续子序列称为段。

定义 5　段

　　 设 W 是序列为 xe1x1⋯eky 的链，则子序列 xiei+1⋯xj−1ejxj 称为 W 的 (xi,xj) 段（section），记作 W(xi,xj)。

定义 6　围长，周长，弦

　　 图 G 中最短圈的长度叫做 G 的围长（girth），记作 g(G)。最长圈的长度叫做 G 的周长（circumference）。图中不在圈上但连接圈中两个点的边称为圈的弦（chord）。

定义 7　最长路，最短路

　　 设 G 是图，则 G 中具有最大长度的路称为 G 的最长路（longest path），具有最小长度的路称为 G 的最短路（shortest path）。

定义 8　距离，直径

　　 设 G 是图，x,y∈V(G)。则称 G 的最短 xy 路的长度为 x,y 在 G 中的距离，记作 dG(x,y)。G 中点间的最大距离称为 G 的直径（diameter），记作 diam G。

　　 可能有这样的情况出现，即有一条迹通过图的所有点和所有边。

定义 9　Euler 迹

　　 设 G 是一个图，则 G 上包含 G 的所有点和所有边的迹称为Euler 迹。闭的迹称为Euler 回。

　　 还可能有这样的情况出现，即有一条路（或圈）通过图的所有点。

定义 10　Hamilton 路，Hamilton 圈

　　 设 G 是一个图，则 G 上包含 V(G) 所有点的路称为Hamilton 路，G 上包含 V(G) 所有点的圈称为Hamilton 圈。

　　 可能会发生这样的情况，即链中的边都是有向的。特别，人们习惯称边方向一致的链为有向链。

定义 11　有向链

　　 设 W 是 xy 链，其对应序列为

(2)xe1x1⋯eky. 
若每一 ei 都是起点为 xi−1 终点为 xi（x0=x,xk=y）的有向边，则称 W 为从 x 到 y 到有向链。反之若每一 ei 都是起点为 xi 终点为 xi−1（x0=x,xk=y）的有向边，则称 W 为从 y 到 x 到有向链。

　　 有了有向链的定义，自然而然就有有向迹，有向路，有向圈的定义。

3. 相关定理

定理 1　

　　 设 G 是图，x≠y∈V(G)，W 是 G 的 xy 链。则存在 G 的 xy 路，且其长度最长为 |V(G)|−1。

　　 证明：1.把 xy 链的序列中相同内点之间段（保留相同点的一个）去掉，则得的仍是 xy 链：

　　 设 W=xe1x1⋯eny，xi=xj∈W,j>i。那么去掉段 W(xi,xj) 并保留 xi,xj 的一个之后（比如保留 xj），得到形如

(3)xe1x1⋯eixjej+1⋯eny 
的序列，由于段 W(x,xi−1),W(xj,y) 没变，因此只需判断 ei 两边的点是否是 ei 的端点即可，由于 ei 的两边的点也没变，因此新得到的序列仍是 xy 链。

　　 2.由于链长有限，我们可以重复 1 操作把链变成没有相同内点的链，而仍得到端点相同的链。由于内点不同，边也就不同，而由条件链的端点不同，因而得到就是连接端点的路。而包含 |V(G)| 个点的路最长为 |V(G)|−1。

　　 证毕！

1. ^ 注意因为点边的记号很好区分，往往省略了序列中相邻两元间的逗号

[1] ^ 徐俊明.图论及应用. 中国科学技术大学出版社, 合肥.1998.

致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。

                     

友情链接： 超理论坛　|　©小时科技 保留一切权利