| 查看: 456 | 回复: 1 | ||
[求助]
学图论的朋友帮个忙啊 已有1人参与
|
| Prove that every cubic graph with at most two bridges contains a 1-factor!请帮忙给出完整的证明过程。 |
回复此楼» 猜你喜欢
评审感受-评审感受-评审感受
已经有14人回复
-
求助大佬sci投稿哪个好中
已经有3人回复
-
这年头没有找到涵评专家，还有中面上的可能吗
已经有6人回复
-
2026博士申请求助
已经有10人回复
-
西南大学考核制博士
已经有6人回复
-
窗边初夏的小雨
已经有10人回复
-
护理论文 晋升
已经有4人回复
-
求碳排放博导；方向是LCA、生命周期可持续发展以及碳排放
已经有8人回复
-
26年申博自荐-计算机视觉
已经有5人回复
-
导师各种操作恶心咋办
已经有12人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 一个关于己烷熔沸点比较的问题，请知道的朋友帮个忙
已经有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