| 查看: 444 | 回复: 1 | ||
[求助]
学图论的朋友帮个忙啊 已有1人参与
|
| Prove that every cubic graph with at most two bridges contains a 1-factor!请帮忙给出完整的证明过程。 |
回复此楼» 猜你喜欢
0854 考研调剂 招生了！AI 方向
已经有14人回复
-
328求调剂
已经有3人回复
-
一志愿重庆大学085700资源与环境，总分308求调剂
已经有5人回复
-
招08考数学
已经有14人回复
-
一志愿上海交大生物与医药专硕324分，求调剂
已经有4人回复
-
0854电子信息求调剂 324
已经有3人回复
-
303求调剂
已经有3人回复
-
336求调剂
已经有3人回复
-
306求调剂
已经有9人回复
-
工科0856求调剂
已经有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
