| 查看: 1131 | 回复: 4 | |||
| 当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖 | |||
[求助]
离散数学的题 谢谢啦 已有1人参与
|
|||
|
一，在一颗有2个2度结点，4个3度结点，其余为树叶的无向图中，应该有几片树叶？ 二，画出两个不同构的满足条件一的结点度数的无向图T1,T2. 发自小木虫Android客户端 |
回复此楼» 猜你喜欢
面上合作单位盖章
已经有5人回复
-
有多少人是今天查系统知道结果的？
已经有17人回复
-
为什么资助数各大高校都创新高，自己申请怎么就这么难
已经有8人回复
-
导师吐槽：我怎么摊上了这么个极品研究生！
已经有7人回复
-
申请删除本帖
已经有7人回复
-
基金不中，共勉
已经有10人回复
-
国自然面上复盘~欢迎讨论
已经有11人回复
-
基金未中，这种答复是模板吗？
已经有6人回复
-
看板上这么多中的，有点像50人群里49个人都是骗子的那种感觉……
已经有6人回复
-
怎么看青基中了没有啊
已经有5人回复
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
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
