最近学习中,在这两个概念上出现了混淆,导致了一些误解,在此厘清。
最大路径
在一个简单图G中,u、v之间的距离 d ( u , v ) = min { u 到 v 的最短路的长度 } d(u,v) = \min \{ u到v的最短路的长度 \} d(u,v)=min{u到v的最短路的长度},直径 d ( G ) = max { d ( u , v ) ∣ u , v ∈ G } d(G) = \max \{ d(u,v)| u,v \in G \} d(G)=max{d(u,v)∣u,v∈G}, 如果G是一个连通图,那么直径就是其中的最长路的距离,或者称之为最大路径。
极大路径
对任意一条路,如果起点和终点的相邻点都在这条路上,则称这条路为极大路径。
举例
如图,v0 v1 v2 是一条极大路径,但不是最大路径。v0 v1 v3 v4 v5是最大路径,自然,也是极大路径。
扩大路径法
扩大路径法只能得到极大路径,而不能得到最大路径。