| 查看: 921 | 回复: 4 | ||
| 当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖 | ||
[求助]
离散数学的题 谢谢啦 已有1人参与
|
||
|
一，在一颗有2个2度结点，4个3度结点，其余为树叶的无向图中，应该有几片树叶？ 二，画出两个不同构的满足条件一的结点度数的无向图T1,T2. 发自小木虫Android客户端 |
回复此楼» 猜你喜欢
投稿Elsevier的杂志（返修），总是在选择OA和subscription界面被踢皮球
已经有8人回复
-
自荐读博
已经有7人回复
-
自然科学基金委宣布启动申请书“瘦身提质”行动
已经有4人回复
-
求个博导看看
已经有18人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 证明求解
已经有3人回复
3楼2015-11-23 07:54:25
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
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