051 哈密尔敦循环

在完全有向的图里每2个顶点之间都有连线,且每条线段都有1个箭头。

对于完全有向的图有个著名的定理,即完全有向图各线段的箭头不论怎么加,总有1条路线——从某个顶点出发,沿着箭头方向通过每个顶点,且每个顶点只经过1次。这样的路线被称为哈密尔敦路线。而如果这条路线能够正好回到起点,那么这条路线就被称为哈密尔敦循环。

根据完全有向定理,哈密尔敦路线在任意完全有向图上都是一定存在的,而哈密尔敦循环则不一定。

下面是1个有7个顶点的完全有向图。你能够在它里面找到1个哈密尔顿循环吗?也就是说,从起点开始,到达其他每个顶点分别1次,然后再回到起点?

figure_0091_0217