什么是汉密尔顿回路问题？（哈密尔顿）_百度知道
什么是汉密尔顿回路问题？（哈密尔顿）
关于数学的哈~有详细的解释最好了~
哈密尔顿的相关知识
您可能关注的推广
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁一类特殊三正则图汉密尔顿回路存在性的证明--《数学学习与研究》2012年11期
一类特殊三正则图汉密尔顿回路存在性的证明
【摘要】：现已知一个内部包含若干条线段的圆,每一条线段和它有两个交点,每一条线段都与其他的若干条线段或全部线段相交.这显然是一种特殊的三正则图.这个圆本身就是经过且仅经过一次所有交点的一个回路,也就是这个图形的一个汉密尔顿回路,本文将证明这样一个定理,凡是符合上述条件的图形都至少还有一个不同于上述圆的汉密尔顿回路.
【作者单位】：
【关键词】：
【分类号】：G634.6【正文快照】：
证明过程如下:首先任选择一条线段,比如线段AB.因为至少与其他线段中的一条相交,因此圆被这条线段分成的两部分都至少拥有两个或两个以上的圆弧.现假设所有的圆弧和线段都是白色的,然后将被选择的线段染成黑色(实线代表黑色,虚线代表白色),再从所分成的两部分中分别选择这样
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【相似文献】
中国期刊全文数据库
张欣星;;[J];数学通讯;2011年06期
雷淑芳;;[J];考试周刊;2011年56期
陈新芳;;[J];教育教学论坛;2011年29期
崔宝荣;;[J];读与写(教育教学刊);2011年07期
王梅;;[J];考试(高考数学版);2011年Z5期
姚永正;;[J];中学教学参考;2011年20期
袁方程;黄俊峰;;[J];中学数学研究;2011年08期
徐军;陈幼凯;;[J];数学大世界(教师适用);2011年06期
刘康玺;;[J];中学教学参考;2011年20期
张国志;;[J];辅导员;2011年17期
中国重要报纸全文数据库
广元市元坝中学
胡德志;[N];学知报;2010年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
地址：北京清华大学 84-48信箱 知识超市公司
出版物经营许可证 新出发京批字第直0595号
同方知网数字出版技术股份有限公司
订购热线：400-819-82499
在线咨询：
传真：010-
京公网安备74号汉密尔顿图怎么证明_百度知道
汉密尔顿图怎么证明
我有更好的答案
首先证明G中有割点,则G不是汉密尔顿图,反证法,如果图G是汉密尔顿图,则必存在汉密尔顿圈(回路),即所有结点均在一个回路中,此时删除任意一个结点图G必连通,于是它的任何点均不是割点,矛盾,即有割点的图不是汉密尔顿图.另一方面,如果它有桥,则连结桥的两个结点必有一个是结点是割点,除非它是仅有一条边的图,显然这种情况它没有汉密尔顿回路,因此不是汉密尔顿图,如果不是这种情况,它必有割点,由上可知它也不是汉密尔顿图.
其他类似问题
汉密尔顿的相关知识
您可能关注的推广回答者：
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁Hamilton 汉密尔顿回路的C语言实现代码，是国外的人写的，和 强大 Algorithm 数学计算 182万源代码下载-
&文件名称: Hamilton
& & & & &&]
&&所属分类:
&&开发工具: Visual C++
&&文件大小: 97 KB
&&上传时间:
&&下载次数: 125
&&提 供 者:
&详细说明：汉密尔顿回路的C语言实现代码，是国外的人写的，和好很强大-code for Hamilton circuit C language implementation
文件列表(点击判断是否您需要的文件，如果是垃圾请在下面评价投诉):
&&Hamilton\tester.h&&........\backtrack.c&&........\graphdata.c&&........\graphgen.c&&........\hamcycle.c&&........\heuristic.c&&........\main.c&&........\options.c&&........\stats.c&&........\tester.c&&........\Makefile&&........\backtrack.h&&........\graphdata.h&&........\graphgen.h&&........\hamcycle.h&&........\heuristic.h&&........\main.h&&........\options.h&&........\stats.h&&........\README.txt&&........\sampleopt.opt&&........\sampletest.test&&........\conditions.txt&&........\manual.txt&&........\Method.txt&&Hamilton
&相关搜索:
&输入关键字，在本站182万海量源码库中尽情搜索：
&[] - 利用回溯法求解Hamilton回路的算法
&[] - 国外黑客Casper写的基于PHP的远程控制程序，思路新颖，功能强大，代码完整。
&[] - 经典的汉密尔顿回路算法，以Matlab代码编写。
&[] - 在无向完全图中寻找边不重复的汉密尔顿回路在无向完全图中寻找边不重复的汉密尔顿回路在无向完全图中寻找边不重复的汉密尔顿回路在无向完全图中寻找边不重复的汉密尔顿回路
&[] - 包括图论中经典的Dijkstra 汉密尔顿算法的图论程序包，非常的实用
&[] - 简单写了个一个哈密顿回路，里面添加了分支限界。这是一个全遍历的，用邻接矩阵存储的。正常情况跑17个节点
&[] - 求最短哈密顿回路C＋＋代码　运用哈密顿思想　求回路
&[] - 给定一个n个结点的连通图，用回溯法求出图中含有的所有哈密尔顿环。包含实验报告。
&[] - 求马步图Hamilton圈的最优算法的论文，希望对大家有用
&[] - 给出一个完全图，给出最小哈密顿回路。顶点个数不要超过20.程序自动生成了一个完全图。也可修改输入，自己输入完全图。& & & & & & & &转：/post.2072698.html
&&：设一个无向图中有 N 个节点，若所有节点的度数都大于等于 N/2，则汉密尔顿回路一定存在。注意，“N/2” 中的除法不是整除，而是实数除法。如果 N 是偶数，当然没有歧义；如果 N 是奇数，则该条件中的 “N/2” 等价于 “?N/2?”。
证明起来不难。首先可以证明图一定是连通的。设 d(v) 表示节点 v 的度数。对于任意两个节点 u、 v，若它们不相邻，则可能和它们相邻的节点共有 N - 2 个，而 d(u) + d(v) ≥ N/2 + N/2 ≥ N，那么根据，肯定存在一个节点与 u 和 v 都相邻。即证，任何两个节点之间都是连通的。
接下来，证明汉密尔顿回路存在的过程其实就是构造这条回路的过程，分成以下几个步骤：
1. 任意找两个相邻的节点 S 和 T，在它们基础上扩展出一条尽量长的没有重复节点的路径。也就是说，如果 S 与节点 v 相邻，而且 v 不在路径 S → T 上，则可以把该路径变成 v → S → T，然后 v 成为新的 S。从 S 和 T 分别向两头扩展，直到无法扩为止，即所有与 S 或 T 相邻的节点都在路径 S → T 上。
2. 若 S 与 T 相邻，则路径 S → T 形成了一个回路。
3. 若 S 与 T 不相邻，可以构造出一个回路。设路径 S → T 上有 k + 2 个节点，依次为 S、 v1、 v2…… vk 和 T。可以证明存在节点 vi， i ∈ [1, k)，满足 vi 与 T 相邻，且 vi+1 与 S 相邻。证明方法也是根据鸽巢原理，既然与 S 和 T 相邻的点都在该路径上，它们分布的范围只有
v1 ∼ vk 这 k 个点， k ≤ N - 2，而 d(S) + d(T) ≥ N，那么可以想像，肯定存在一个与 S 相邻的点 vi 和一个与 T 相邻的点 vj， 满足 j & i。那么上面的命题也就显然成立了。
找到了满足条件的节点 vi 以后，就可以把原路径变成 S → vi+1 → T → vi → S，即形成了一个回路。
4. 现在我们有了一个没有重复节点的回路。如果它的长度为 N，则汉密尔顿回路就找到了。
如果回路的长度小于 N，由于整个图是连通的，所以在该回路上，一定存在一点与回路以外的点相邻。那么从该点处把回路断开，就变回了一条路径。再按照 的方法尽量扩展路径，则一定有新的节点被加进来。接着回到。
在整个构造过程中，如果说每次到步骤 4 算是一轮的话，那么由于每一轮当中，至少有一个节点被加入到路径 S → T 中来，所以总的轮数肯定不超过 N 轮。实际上，不难看出该算法的复杂度就是 O(N2)，因为总共扩展了 N 步路径，每步扩展最多枚举所有的节点。
Source Code
Problem: 2438
Memory: 848K
Time: 141MS
Language: C++
Result: Accepted
Source Code
#include &iostream&
#include &cstring&
#include &cstdio&
#include &cmath&
const int N = 410;
int mp[N][N];
int ans[N];
int vis[N];
void init()
for(int i=1;i&=n;i++)
for(int j=1;j&=n;j++)
if(i==j)mp[i][j]=0;
mp[i][j]=1;
memset(vis,0,sizeof(vis));
memset(ans,0,sizeof(ans));
void Reverse(int s,int e)
while(s&e)
swap(ans[s],ans[e]);
void kuozhan()
int flag=0;
for(int i=1;i&=n;i++)
if(!vis[i]&&mp[end][i])
ans[cnt++]=i;
void hamiltun()
for(int i=1;i&=n;i++)
if(mp[1][i]){
vis[start]=1;
vis[end]=1;
kuozhan();
Reverse(0,cnt-1);
swap(start,end);
kuozhan();
int mid=0;
if(!mp[start][end])
for(int i=1;i&cnt-2;i++)
if(mp[ans[i]][end]&&mp[ans[i+1]][start])
Reverse(mid,cnt-1);
end=ans[cnt-1];
if(cnt==n)
for(int i=1;i&=n;i++)
if(!vis[i])
for(j=1;j&cnt-1;j++)
if(mp[ans[j]][i])
if(mp[ans[mid]][i]){
end=i;mid=j;
start=ans[mid-1];
Reverse(0,mid-1);
Reverse(mid,cnt-1);
ans[cnt++]=
vis[end]=1;
int main()
while(scanf(&%d%d&,&n,&m)!=EOF)
if(!n&&!m)
for(int i=1;i&=m;i++)
scanf(&%d%d&,&u,&v);
mp[u][v]=mp[v][u]=0;
hamiltun();
cout&&ans[0];
for(int i=1;i&i++)
printf(& %d&,ans[i]);
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：142877次
积分：3580
积分：3580
排名：第3145名
原创：220篇
转载：57篇
评论：33条
(5)(1)(13)(19)(5)(1)(15)(1)(3)(6)(10)(15)(4)(15)(24)(46)(42)(21)(2)(8)(12)(4)(2)(3)}