24小时热门版块排行榜

>论坛更新日志 (4178)
>虫友互识 (506)
>导师招生 (398)
>找工作 (285)
>职场人生 (242)
>论文投稿 (234)
>文献求助 (215)
>考博 (141)
>考研 (103)
>休闲灌水 (90)
>博后之家 (84)
>学术会议 (61)
>医学 (61)
>硕博家园 (60)
>招聘信息布告栏 (55)
>有机交流 (29)

返回列表

star0828

铁虫 (初入文坛)

应助: 0 (幼儿园)
金币: 20.5
帖子: 9
在线: 1小时
虫号: 866849
注册: 2009-10-09
性别: MM
专业: 电路与系统\电子系统设计自

[交流] 【求助】Euler图已有1人参与

一个阶为5的图添加任一条边变成Euler图是什么图啊？

回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:

Project Euler 48 欧拉工程 48 题已经有30人回复
第一性原理如何描述化学反应动力学？已经有21人回复
Euler 工程第廿七题：系数的积已经有15人回复
Euler 工程第十八题：三角阵上最大的和已经有12人回复
Euler 工程第十五题：从左上角到右下角有多少条路？已经有5人回复
【求助】模拟烧杯中固液流动的热传导已经有6人回复
【分享】无穷的世界【已搜无重复】已经有3人回复
【求助】关于欧拉－拉格朗日方程（Euler-Lagrange equation）【已解决】已经有11人回复

1楼 2009-12-29 20:53:15

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

formleaf

木虫 (正式写手)

应助: 0 (幼儿园)
贵宾: 1.097
金币: 3383.1
散金: 2780
红花: 3
帖子: 991
在线: 69.6小时
虫号: 698652
注册: 2009-02-09
性别: GG
专业: 组合数学

★ ★
小木虫(金币+0.5):给个红包，谢谢回帖交流
haixing2008(金币+1,VIP+0):多谢交流！ 12-31 09:24

5个顶点的完全图减去任意一条边得到的图满足楼主的要求（前提是只考虑简单图，即没有重复边也没有自环）

赞一下(11人)

回复此楼

2楼2009-12-30 08:54:40

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

formleaf

木虫 (正式写手)

应助: 0 (幼儿园)
贵宾: 1.097
金币: 3383.1
散金: 2780
红花: 3
帖子: 991
在线: 69.6小时
虫号: 698652
注册: 2009-02-09
性别: GG
专业: 组合数学

★ ★
haixing2008(金币+2,VIP+0):多谢热心解答！ 12-31 09:24

如果是一般图，允许有重复边和自环，那么此题无解。因为加一条边成为Euler图，就是说原图有3个顶点是偶数度的，2个顶点是奇数度的，如果任意连边，假设连接两个偶度点，则会有四个顶点奇数度的，不可能是Euler图。
Euler图的条件：任意顶点的度是偶数的。

赞一下(10人)

回复此楼

3楼2009-12-30 08:59:03

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

formleaf

木虫 (正式写手)

应助: 0 (幼儿园)
贵宾: 1.097
金币: 3383.1
散金: 2780
红花: 3
帖子: 991
在线: 69.6小时
虫号: 698652
注册: 2009-02-09
性别: GG
专业: 组合数学

★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖交流
haixing2008(金币+2,VIP+0):再次鼓励！加油！ 12-31 09:24

这里我考虑阶是指顶点的个数
如果放宽条件，不要求有Euler回路，只要求有Euler路即可，则
存在Euler路的充要条件：最多有两个顶点度为奇数。
那么我们考虑5个顶点的连通图，则要求它必须至多只有两个奇数度点，这样无论如何添加边，它始终保证最多有两个奇数度点。这样的图中最简单的是P5，即5个顶点组成的一条路径，其他满足条件的图都是在P5上任意添加边得到的，这里可以添加重复边或自环

赞一下(11人)

回复此楼

4楼2009-12-30 09:07:14

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖