| 查看: 431 | 回复: 1 | |||
[求助]
学图论的朋友帮个忙啊 已有1人参与
|
| Prove that every cubic graph with at most two bridges contains a 1-factor!请帮忙给出完整的证明过程。 |
回复此楼» 猜你喜欢
假如你的研究生提出不合理要求
已经有6人回复
-
对氯苯硼酸纯化
已经有3人回复
-
求助:我三月中下旬出站，青基依托单位怎么办？
已经有12人回复
-
不自信的我
已经有12人回复
-
所感
已经有4人回复
-
论文终于录用啦！满足毕业条件了
已经有28人回复
-
要不要辞职读博？
已经有7人回复
-
北核录用
已经有3人回复
-
实验室接单子
已经有3人回复
-
磺酰氟产物，毕不了业了！
已经有8人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 一个关于己烷熔沸点比较的问题，请知道的朋友帮个忙
已经有4人回复
【答案】应助回帖
★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ...
感谢参与，应助指数 +1
小瓶盖8023(feixiaolin代发): 金币+30, 及时奖励应助 2014-01-24 08:23:28
小瓶盖8023(feixiaolin代发): 金币+30 2014-01-24 08:23:36
小瓶盖8023(feixiaolin代发): 金币+30 2014-01-24 08:23:45
小瓶盖8023: 金币+10, ★★★很有帮助, 谢谢你哦 2014-01-28 19:31:22
感谢参与，应助指数 +1
小瓶盖8023(feixiaolin代发): 金币+30, 及时奖励应助 2014-01-24 08:23:28
小瓶盖8023(feixiaolin代发): 金币+30 2014-01-24 08:23:36
小瓶盖8023(feixiaolin代发): 金币+30 2014-01-24 08:23:45
小瓶盖8023: 金币+10, ★★★很有帮助, 谢谢你哦 2014-01-28 19:31:22
|
令S表示V（G）的任意一个子集，O（G-S）表示G-S的奇连通分量的个数 显然G-S的奇连通分量与S之间的连接只能是：至多有两个奇连通分量与S的连接为1（否则，就会出现三条以上的割边），并且其他奇连通分量与S的连接大于等于3（考虑到3-regular的问题，连接数只能都是奇数）。 如果用k表示所有奇连通分量到S的连接数，则由上可知k≥3O(G-S)-4；又因k≤3|S|（当S中所有点互相都无连接时），则O(G-S)≤|S|+4/3。注意，O(G-S)与|S|的奇偶性相同（3-regular，前面已经说过了），那么只能O(G-S)≤|S|。由Tutte定理可知G存在1-factor |
2楼2014-01-21 02:51:23