| 查看: 1108 | 回复: 4 | ||
[求助]
离散数学的题 谢谢啦 已有1人参与
|
|
一，在一颗有2个2度结点，4个3度结点，其余为树叶的无向图中，应该有几片树叶？ 二，画出两个不同构的满足条件一的结点度数的无向图T1,T2. 发自小木虫Android客户端 |
回复此楼» 猜你喜欢
能否退出参与的面上项目解除限项
已经有14人回复
-
2026国自然函评费到账
已经有18人回复
-
建议基金发布提前给出明确的时间点
已经有15人回复
-
范进中举一文的中心思想
已经有7人回复
-
朋友圈看到的
已经有9人回复
-
让我中一个面上吧！
已经有16人回复
-
放榜前的不淡定
已经有17人回复
-
科研孤儿太难了
已经有19人回复
-
明天应该可查了！？
已经有4人回复
-
什么时候开奖？
已经有11人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 证明求解
已经有3人回复
Edstrayer
版主 (著名写手)
方寸斗室小天地正气迷漫大世界
- 数学EPI: 7
- 应助: 157 (高中生)
- 贵宾: 0.927
- 金币: 9349.6
- 散金: 4503
- 红花: 77
- 沙发: 2
- 帖子: 2745
- 在线: 1465.6小时
- 虫号: 3086598
- 注册: 2014-03-25
- 管辖: 数学
2楼2015-11-23 03:04:57
3楼2015-11-23 07:54:25
hank612
至尊木虫 (著名写手)
- 数学EPI: 14
- 应助: 225 (大学生)
- 金币: 14270.6
- 散金: 1055
- 红花: 95
- 帖子: 1526
- 在线: 1375.8小时
- 虫号: 2530333
- 注册: 2013-07-03
- 性别: GG
- 专业: 理论和计算化学
|
Edstrater 大神的答案无疑是正确的，我来八卦一下题目背后的意图。 第一问其实是来自Erdős–Gallai theorem， 它给出一个递减正整数序列能够作为某个简单图(simple graph) 的degree sequence 的充分必要条件，连接 https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem 所以，可能有的树叶(leaf) 个数可以为 0,2,4,6。 具体可以看附件的图片 (当然，图画的很难看，楼主多多包涵，谢谢啦） 第二问，可以参考附件中的Havel-Hakimi-Berge 定理：给定degree sequence, 所有可能的图必须是2-switch等价的。 满足题目中条件的图那是相当的多，楼主慢慢画吧。 问题的困难点在于，没有什么好的办法或理论判定两个图是否同构。  temp1.png  temp2.png |
4楼2015-11-23 10:52:35
hank612
至尊木虫 (著名写手)
- 数学EPI: 14
- 应助: 225 (大学生)
- 金币: 14270.6
- 散金: 1055
- 红花: 95
- 帖子: 1526
- 在线: 1375.8小时
- 虫号: 2530333
- 注册: 2013-07-03
- 性别: GG
- 专业: 理论和计算化学
|
@Edstrayer 刚发完帖子，发现居然把 Edstrayer 准版主大神 的名字拼错了，非常非常对不起啊，敬请谅解。 另外，关于2-switch, 可以参考文章 http://homepages.math.uic.edu/~mubayi/papers/newdraft.pdf http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%202.PDF |
5楼2015-11-23 11:00:06
