什么是哈密顿环

来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/26 15:44:33
什么是哈密顿环什么是哈密顿环什么是哈密顿环经过图(有向图或无向图)中所有顶点一次且仅一次的通路称为哈密顿通路.经过图中所有顶点一次且仅一次的回路称为哈密顿回路.换一种说法,对于一个给定的网络,确定起点

什么是哈密顿环
什么是哈密顿环

什么是哈密顿环
经过图(有向图或无向图)中所有顶点一次且仅一次的通路称为哈密顿通路.经过图中所有顶点一次且仅一次的回路称为哈密顿回路.
换一种说法,对于一个给定的网络,确定起点和终点后,如果存在一条路径,且满足每个顶点只被访问一次的情况下能穿过这个网络,我们就说这个网络存在哈密顿路径

正1859年,英国数学家哈密顿(R·Hamitlon,1805~1865)提出了一个著名的周游世界的游戏:以一个正十二面体的二十个顶点代表二十个城市,要求从一个城市出发,沿着棱恰好经过每个城市各一次,最后回到起点。上述游戏的解有好多种,满足要求的每一条路径都称之为哈密顿环...

全部展开

正1859年,英国数学家哈密顿(R·Hamitlon,1805~1865)提出了一个著名的周游世界的游戏:以一个正十二面体的二十个顶点代表二十个城市,要求从一个城市出发,沿着棱恰好经过每个城市各一次,最后回到起点。上述游戏的解有好多种,满足要求的每一条路径都称之为哈密顿环

收起