| 查看: 518 | 回复: 2 | ||
[求助]
请教一个图论问题！
|
|
图G是一个2-连通图，即不存在割点。 证明：对于任意u∈V(G)，存在u的某个邻点v，使得G－u－v连通。 |
回复此楼» 猜你喜欢
估计是周四
已经有3人回复
-
基金啊基金
已经有3人回复
-
科研孤儿太难了
已经有15人回复
-
让我中一个面上吧！
已经有10人回复
-
言之凿凿，明天官网会通知放榜？
已经有17人回复
-
时间戳又变了
已经有17人回复
-
今天系统多次维护，明天很可能放榜！
已经有11人回复
-
时间戳变了，能看出什么问题？
已经有23人回复
-
只有每年这种时候来逛逛小木虫
已经有22人回复
-
放榜前的不淡定
已经有12人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 请教一个电子能量的问题
已经有6人回复
- 请教一个老问题：结构优化时的对称性问题
已经有17人回复
- 请教一个养细胞的问题！急！
已经有9人回复
- 求助，如何将一个图划分为几个大小相等的集群并集群间的互联度最小
已经有5人回复
- 呼唤图论高手！关于图论中子图间连通度的问题。
已经有4人回复
- 请教一个问题，自旋多重度为什么是2S+1? 它的意义又是什么？
已经有10人回复
- 请教一个小问题，capping agent 要怎么翻译呢？
已经有15人回复
- 请教一个关于相似度检查的问题
已经有6人回复
- 再请教一个shell命令批处理问题
已经有8人回复
- SCI大修录用经历
已经有7人回复
- 弱问：运筹学和图论有什么联系？
已经有6人回复
- APL 奇怪， 没有Editorial Office，直接Under Consideration - Editor
已经有10人回复
- 请教一个CCDC的小问题
已经有8人回复
- 请教一个关于测序峰图的问题
已经有5人回复
- 请教一个烯丙基溴反应的问题
已经有9人回复
- 请教一个while loop程序的问题
已经有5人回复
- 请教一个问题：用商用盗版软件仿真的结果发表论文会不会有麻烦？
已经有6人回复
- 【请教】请教一个六方晶系的问题
已经有12人回复
- 【请教】请教一个关于图片精度的问题
已经有6人回复
- 【求助】请教一个m062x的问题
已经有7人回复
- 【求助】关于图像分割的一个问题
已经有9人回复
- 【求助】请教 科研学术论文的写作
已经有15人回复
hank612
至尊木虫 (著名写手)
- 数学EPI: 14
- 应助: 225 (大学生)
- 金币: 14270.6
- 散金: 1055
- 红花: 95
- 帖子: 1526
- 在线: 1375.8小时
- 虫号: 2530333
- 注册: 2013-07-03
- 性别: GG
- 专业: 理论和计算化学
【答案】应助回帖
★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★
感谢参与，应助指数 +1
feixiaolin: 金币+2, Hank612很活跃，常应助一些疑难问题。颁数学EPI一枚。 2013-11-28 09:24:48
dameng: 金币+20, ★★★★★最佳答案, 果然是高手！ 2013-11-28 11:46:35
感谢参与，应助指数 +1
feixiaolin: 金币+2, Hank612很活跃，常应助一些疑难问题。颁数学EPI一枚。 2013-11-28 09:24:48
dameng: 金币+20, ★★★★★最佳答案, 果然是高手！ 2013-11-28 11:46:35
|
根据Menger定理, a graph is k-connected if and only if it contains k independent paths between any two vertices. 现在假设在图 G-{v}中, 删除任意一个邻居(u~v), 都将使得G-{u}-{v}不连通. 这意味着,存在x,y 在G-{v}, 使得所有连接x到y的道路Path, 一定经过u. 那么, x,y在G中一定有一条道路通过v, 并且跟上述经过u的道路没有在内部相交.换句话说, 存在z,w 均为v的邻居, 使得: x--z--v--w--y, 并且 z,w,u 均不相同. 下一步, 忘记所有不是v邻居的顶点, 只考虑v邻居们形成的三元组(z,u,w), 使它们满足: 从z到w在G-{v}中必须要经过u. 我们还可以额外要求, 从z到u不经过v的任何邻居, 从u到w也不经过 v的任何邻居. 我们可以证明, 一定有另外邻居 a, 使得 (a, z, u). 要不然, 所有邻居都可以不通过z到达u, 那么对顶点z, 它们可以通过u中转,就没有三元组(a,z,b)以z为必经之地了, 这和我们的假设不符. 那么, 由于v邻居只有有限个, 所以一定有个顶点p, 使得, p - a1 -a2 -a3-...- an-p, 其中, p, a1,..,an各不相同, (p, a1, a2), (a1, a2, a3) 等等都是三元组. 可是, 这就是矛盾所在, 因为p可以反过来经过an -a(n-1)-..-a3到达a2, 并且这条道路上仅有的v的邻居就是an ,a(n-1),..,a3, 但是不用经过a1. |
2楼2013-11-28 06:13:23
hank612
至尊木虫 (著名写手)
- 数学EPI: 14
- 应助: 225 (大学生)
- 金币: 14270.6
- 散金: 1055
- 红花: 95
- 帖子: 1526
- 在线: 1375.8小时
- 虫号: 2530333
- 注册: 2013-07-03
- 性别: GG
- 专业: 理论和计算化学
3楼2013-11-28 14:08:21
40