扩大路径法

设 $G=<V,E>$ 为 $n$ 阶无向图, $E\ne \varnothing$, 设 ${\Gamma }_l$ 为 $G$ 中的一条 路径, 若路径的起点或终点与路径外的顶点相邻, 将顶点扩大到路径中. 设最后得到的路径为 ${\Gamma }_{l+k}$, 称为极大路径.

极大路径不一定是图中最长的路径.