| 查看: 445 | 回复: 1 | |||
[求助]
学图论的朋友帮个忙啊 已有1人参与
|
| Prove that every cubic graph with at most two bridges contains a 1-factor!请帮忙给出完整的证明过程。 |
回复此楼» 猜你喜欢
291 求调剂
已经有5人回复
-
298-一志愿中国农业大学-求调剂
已经有11人回复
-
一志愿南京理工大学085701资源与环境302分求调剂
已经有7人回复
-
316求调剂
已经有7人回复
-
材料与化工考研调剂
已经有4人回复
-
一志愿重庆大学085700资源与环境，总分308求调剂
已经有7人回复
-
一志愿211 初试270分 求调剂
已经有4人回复
-
08工学调剂
已经有11人回复
-
350求调剂
已经有6人回复
-
求调剂一志愿武汉理工大学材料工程（085601）
已经有4人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 一个关于己烷熔沸点比较的问题，请知道的朋友帮个忙
已经有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
