
上QQ阅读APP看本书,新人免费读10天
设备和账号都新为新人
051 哈密尔敦循环
在完全有向的图里每2个顶点之间都有连线,且每条线段都有1个箭头。
对于完全有向的图有个著名的定理,即完全有向图各线段的箭头不论怎么加,总有1条路线——从某个顶点出发,沿着箭头方向通过每个顶点,且每个顶点只经过1次。这样的路线被称为哈密尔敦路线。而如果这条路线能够正好回到起点,那么这条路线就被称为哈密尔敦循环。
根据完全有向定理,哈密尔敦路线在任意完全有向图上都是一定存在的,而哈密尔敦循环则不一定。
下面是1个有7个顶点的完全有向图。你能够在它里面找到1个哈密尔顿循环吗?也就是说,从起点开始,到达其他每个顶点分别1次,然后再回到起点?
