无向完全图是哈密顿图吗?

发布网友发布时间：2022-05-11 02:58

共2个回答

热心网友时间：2024-03-01 08:59

应该是错的，通过图G中每节点一次的通道定为路，此路称为哈密顿路。通过图G中每结点一次的闭通道为回路，此回路称为哈密顿回路。具有哈密顿回路的图叫哈密顿图
定义1:
经过图中每个顶点一次且仅一次的通路称为哈密顿通路。存在哈密顿回路的图称为哈密顿图。
定理1:
设无向图G=是哈密顿图，V1是V的任意的非空子集，
则
p(G-V1)<=|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)阶有向完全图为哈密顿图。

热心网友时间：2024-03-01 08:59

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