无向完全图是哈密顿图.（）判断对错

关节轴承2022-10-04 11:39:541条回答

已提交，审核后显示！提交回复

共1条回复

surehouse 共回答了21个问题 | 采纳率81%: 应该是错的,通过图G中每节点一次的通道定为路,此路称为哈密顿路.通过图G中每结点一次的闭通道为回路,此回路称为哈密顿回路.具有哈密顿回路的图叫哈密顿图
定义1：经过图中每个顶点一次且仅一次的通路称为哈密顿通路.存在哈密顿回路的图称为哈密顿图.
定理1：设无向图G=是哈密顿图,V1是V的任意的非空子集,
则
p(G-V1)=3)阶无向简单图,如果G中任何一对不相邻的顶点度数之和都大于等于n,则G是哈密顿图.
推论：设G是n(n>=3)阶无向简单图,如果G中任何一对不相邻的顶点的度数之和都大于等于n,则G是哈密顿图.
定理3：在n(n>=2)阶有向图D=中,如果所有有向边均用无向边代替,所得无向图中含生成子图Kn,则有向图中存在哈密顿图.
推论：n(n>=3)阶有向完全图为哈密顿图.; 1年前

相关推荐

证明,一个具有N个顶点的无向完全图的边数为N(N-1)/2 芯雨3791年前1: 梓榆25 共回答了13个问题 | 采纳率84.6%

数学归纳法：
1个顶点为0 2个顶点为1 满足1=2*1/2
3个顶点以上时假如n=k-1 k>=3时结论成立
也就是k-1个顶点有 (k-1)*(k-2)/2=k^2/2-3k/2+1个边
加入第k个顶点时与前k-1个顶点产生k-1条边
则边数一共为k^2/2-3k/2+1+k-1=k^2/2-k/2=k*(k-1)/2
即当n=k时也满足条件
因此一个具有N个顶点的无向完全图的边数为n*(n-1)/2

1年前查看全部

离散数学A无向完全图都是欧拉图 B有n个结点n-1条边的无向图都是树 C无向完全图都是平面图 D树的每条边都是割边那个 离散数学 A无向完全图都是欧拉图 B有n个结点n-1条边的无向图都是树 C无向完全图都是平面图 D树的每条边都是割边那个对 wangman1111年前1: shendan69 共回答了19个问题 | 采纳率94.7%

D
某条边要不是割边就形成圈了

1年前查看全部

离散数学急问八阶无向完全图的边数是? nackel1年前1: minano 共回答了20个问题 | 采纳率95%

8(8-1)/2=28
八阶无向完全图的边数是28.

1年前查看全部

无向完全图K4是（）．A.欧拉图 B.汉密尔顿图 C.非平面图 D.树 eldtop1年前1: jiangguicai 共回答了14个问题 | 采纳率100%

C明显错（自己可以画一下）
D也是错的,它不是树（树有一个结点的度数是1,而K4结点度数全是3）；
A也是错的（存在欧拉回路当且仅当每个结点度数是偶数）；
B是对的（存在一个汉密尔顿回路当且仅当每一对结点度数大于n,这里n=4,而每一对结点之和是6）
所以选B

1年前查看全部

无向完全图K4的非同构的连通的生成子图共有（）个.自学跪谢 芳草_20061年前0: 共回答了个问题 | 采纳率

查看全部

无向完全图是哈密顿图吗? 无时不在1年前1: 好奇lijiay 共回答了20个问题 | 采纳率90%

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

1年前查看全部

大家在问