哈密顿图，欧拉图与哈密顿图的区别

本文目录一览

1，欧拉图与哈密顿图的区别
2，离散数学哈密顿图问题问题如图
3，正五边形是不是哈密尔顿图
4，什么时候无向完全图是哈密顿图
5，有不含hamilton圈的hamilton图么
6，哈密尔顿图证明题

1，欧拉图与哈密顿图的区别

欧拉图要遍历所有的边，点是可以重复经过的，而哈密顿图每个顶点只能通过一次

欧拉回路：结点可以重复。哈密尔顿回路：每个点仅能经过一次，不能重复。

欧拉图与哈密顿图的区别

2，离散数学哈密顿图问题问题如图

第一个等号是握手定理说的是度数之和等比边数的两倍。后面放大时一是d(u)+d(v)<m而是除u，v外剩余m-2点每个点度数分成两部分一部分是和u，v连的变，这些度数<d(u)+d(v)<m另外一部分是他们互相之间的边，每个均不大于m-3 所以是<m+m+(m-2)(m-3)

离散数学哈密顿图问题问题如图

3，正五边形是不是哈密尔顿图

1，哈密尔顿图有严格的理论。哈密尔顿通路（回路）与哈密顿图（Hamilton图）通过图G的每个结点一次，且仅一次的通路（回路），就是哈密顿通路（回路）. 存在哈密尔顿回路的图就是哈密顿图·通求画成正五边形。但对形状要求没那么严格，结点不能疏漏。2，而正五边形图形严格，边长和内角都相等。供参考

也许是的。

正五边形是不是哈密尔顿图

4，什么时候无向完全图是哈密顿图

假设图有n个顶点，记为A1,A2,...,An，那么取路径A1,A2,...,An,A1即可。

应该是错的，通过图g中每节点一次的通道定为路，此路称为哈密顿路。通过图g中每结点一次的闭通道为回路，此回路称为哈密顿回路。具有哈密顿回路的图叫哈密顿图定义1：经过图中每个顶点一次且仅一次的通路称为哈密顿通路。存在哈密顿回路的图称为哈密顿图。定理1：设无向图g=是哈密顿图，v1是v的任意的非空子集，则 p(g-v1)其中，p(g-v1)为从g中删除v1(删除v1中各顶点及关联的边)后所得到的图的连通分支。定理2：设g是n(n>=3)阶无向简单图，如果g中任何一对不相邻的顶点度数之和都大于等于n,则g是哈密顿图。推论：设g是n(n>=3)阶无向简单图，如果g中任何一对不相邻的顶点的度数之和都大于等于n，则g是哈密顿图。定理3：在n(n>=2)阶有向图d=中，如果所有有向边均用无向边代替，所得无向图中含生成子图kn，则有向图中存在哈密顿图。推论： n(n>=3)阶有向完全图为哈密顿图。

5，有不含hamilton圈的hamilton图么

哈密顿图定义如下：哈密顿通路（回路）与哈密顿图（Hamilton图）通过图G的每个结点一次，且仅一次的通路（回路），就是哈密顿通路（回路）. 存在哈密顿回路的图就是哈密顿图.所以不含hamilton圈的图不可能是hamilton图

关于这种图怎么看的问题，主要就是要知道题目所给条件隐含的内容，以及需要关联所学知识再做答。就以这道题为例吧~ 分析所给条件： a为北极圈——该地位于北半球 b为晨昏线——mp、pn是晨线昏线中的某一条 q点和p点分别是a和b的中点——所以该点所在直线为正午12点或凌晨0点 m、n为晨昏线与北极圈的交点，且m、n两点的经度差为120°——（经度差这样的条件要特别注意，因为这样的题会涉及到计算时间等等）明确条件后就可以开始回答问题了。 1.如果pm为晨线，则此时n点为 a.4点 b 8点 c 20点 d 16点选d。若pm为晨线，则pn为昏线，按太阳自西向东转，q点和p点所经过的直线为正午12点。m到p、p到n的经度差相等，为60°（=120°/2）。每隔15°时间相差一小时，所以相差60°就是相差4小时，求昏线，即n点时间为16点（=12点+4小时）.题目还可以问昏线上的时间、落日时间，这都是一样的,或给昏线时间问晨线、问日出时间等等。 2.如果pn为晨线，则q点的日出时间为 a.4点 b 8点 c 20点 d 16点我想你的问题有没有打错了？若pn为晨线，那么应该问q点的日落时间啊... 如果本题是这样的话，选c。与上一题相同，pn为晨线那么pm为昏线，两地相差240°，算法与上一题相同，得出答案为c。 3.如果一架飞机沿最短航线自m地飞行到n地，则其飞行方向是a 由东向西b 由西向东c 先向东北，后向东南d 先向西北，后向西南选c。两地间最短距离为他们的劣弧，北半球弯向北极，南半球弯向南极。其实这种题最重要的是掌握方法，只要有思路，多练练就可以了~ 一家之言，仅做参考，不过还是希望能够帮助你~~

6，哈密尔顿图证明题

根据题意可得g为一个有回路的简单图，然后假设有点不再回路上，去掉与这个点相连的边，与G-e是一棵生成树是一颗生成树矛盾，所以所有点必在这个回路上，所以必为哈密尔顿图

证明 1）首先证明g是连通的。若g有两个或更多互不连通的分图，设一个分图有n1个结点，任取一个结点v1，设另一个分图有n2个结点，任取一个结点v2，因为d(v1)≤n1－1，d(v2)≤n2－1，故d(v1)+ d(v2) ≤n1+ n2－2＜n－1，这表明与题设矛盾，故g必连通。其次证明g中存在哈密尔顿路。通过下面的方法可以在g中找到一条哈密尔顿路。为此令p为g中任意一条包含p个结点(p＜n)的路，设其结点序列为v1，v2，…，vp。反复应用下面方法来扩充这一路径，直到p包含n个结点。由于p<n，故必有路径p外结点v与p上结点相邻接, 否则，图g就不连通。 i）如果v与v1或vp邻接，那么可立即扩充p为长度为p的路。 ii）如果v不与v1或vp邻接，则v1，vp均只与原路径p上的结点相邻，则首先证明：g中有一条包含v1，v2，…，vp，长度为p的环。如果v1与vp相邻，那么，则回路已找到。否则，如果v1与vi1 ,vi2 , …,vir相邻，1＜i1＜i2＜…＜ir＜p,考虑vp：若vp不与vi1-1 ,vi2-1 , …, vir-1中任何一个相邻，那么deg(vp)≤p-r-l，因而deg(v1)+deg(vp)≤r+p-r-l=p-1＜n-1，与题设矛盾。因此vp与vi1-1 ,vi2-1 , …, vir-1之一，例如vik-1(i1≤ik≤ir)相邻，于是,我们便可得到包含v1，v2，…，vp 的环：v1，v2，…，vik ,vp , vp-1 , …，vik,v1。如图10.32(a)所示。由于如果v不与v1或vp邻接，则v必与p上其它某个结点邻接，如与vi邻接，那么我们可以得到一条包含p+1个结点的路：v, vi ,vi-1,…, v1,vik ,vik+1,…, vp ,vik-1 ,…, vi+1，如图10.32(b)所示。由于p<n，则总可以按上述方法重复扩充路p，直至最终p=n，即路p包含n个结点，即g的哈密尔顿路。 2) 用反证法。设g是有n个结点、并满足题设的结点度数条件的非哈密尔顿图。通过向g中加边，总能得到一哈密顿尔图。设g′为对g加边得到的一个图，g′是非哈密尔顿图，且再向g′中加入任一边时即成哈密尔顿图。显然，g′仍满足结点度数条件，且g′中有一条包含g中每一个结点的路v1v2…vn。因为g′是非哈密尔顿图，所以v1与vn不相邻，故有d(v1)+d(vn)≥n。然而必存在结点vi与v1相邻，且vi-1与vn相邻，如图10.33所示。否则，若不存在这样的vi，即vi与vi1，vi2，…，vik相邻(2≤i1＜i2＜…＜ik≤n-1)，d(v1)=k，而vn与vi1-1，vi2-1，…，vik-1，均不相邻，则d(vn)≤n-k-1，于是d(v1)+d(vn)≤k+(n-k-1)＜n，与题设条件矛盾。因此，我们可以得到g′中的一条哈密尔顿环v1，v2，…，vi-1，vn，vn-1，…，vi+1，vi，v1，这与g′是非哈密尔顿图矛盾，从而原假设不正确，即满足题设给出的度数条件的图是哈密尔顿图。