| 查看: 446 | 回复: 1 | |||
[求助]
学图论的朋友帮个忙啊 已有1人参与
|
| Prove that every cubic graph with at most two bridges contains a 1-factor!请帮忙给出完整的证明过程。 |
回复此楼» 猜你喜欢
291求调剂
已经有4人回复
-
生物学一志愿985，分数349求调剂
已经有8人回复
-
328求调剂，英语六级551，有科研经历
已经有12人回复
-
070300化学求调剂
已经有6人回复
-
考研化学308分求调剂
已经有7人回复
-
一志愿上海交大生物与医药专硕324分，求调剂
已经有5人回复
-
工科0856求调剂
已经有5人回复
-
一志愿中国石油大学（华东） 本科齐鲁工业大学
已经有4人回复
-
279分求调剂 一志愿211
已经有16人回复
-
求调剂一志愿武汉理工大学材料工程（085601）
已经有5人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 一个关于己烷熔沸点比较的问题，请知道的朋友帮个忙
已经有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
