Question

若G是一个汉密尔顿图,则G一定是( ) A. 平面图 B. 对偶图 C. 欧拉图 D. 连通图

Answer 1

D、连通图

若G是一个汉密尔顿图，则G一定是连通图。哈密顿通路与哈密顿图 通过图G的每个结点一次，且仅一次的通路，就是哈密顿通路。存在哈密顿回路的图就是哈密顿图。美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密顿图。闭合的哈密顿路径称作哈密顿圈，含有图中所有顶点的路径称作哈密顿路径。所以选D、连通图。

扩展资料：

哈密顿图的充分条件和必要条件：

1、定理1： 设无向图G是哈密顿图，V1是V的任意的非空子集， p(G-V1)≤|V1| 其中，p(G-V1)为从G中删除V1(删除V1中各顶点及关联的边)后所得到的图的连通分支。

2、定理2： 设G是n(n≥3)阶无向简单图，如果G中任何一对不相邻的顶点度数之和都大于等于n，则G是哈密顿图。

3、定理3： 在n(n≥2)阶有向图D=中，如果所有有向边均用无向边代替，所得无向图中含生成子图Kn，则有向图中存在哈密顿图。