|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- 求教大牛们关于块的问题 (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=63770) |
|
-- 作者：Chojin -- 发布时间：6/16/2008 12:40:00 PM -- 求教大牛们关于块的问题 离散教程上有个证明说，一个图是2-边连通的当且仅当任意两点共简单回路。 这个证明用到了块的概念，并且看它的证明似乎有这么个暗含的结论： 两个块之间只有一个公共点（如果它们有公共点的话），并且该公共点是图的割点。 请问大牛这个结论对吗？怎么证明呢？ 谢谢！ |
|
-- 作者：fgffggfg -- 发布时间：6/16/2008 3:02:00 PM -- 不正确。比如1个K4，去掉边（v1,v3）所得的图中有2个块：1个顶点集为v1,v2,v4，另1个为v2,v3,v4，这2个块有2个公共点v2,v4。搞错了，照团的定义去想了呵呵，sorry。 是正确的，用反证法，假设块1和块2交点数大于1，则块1并块2仍为无割点的连通图，与块的定义矛盾（即块1非无割点的最大连通子图）。 证2块的交点是图的割点：反证法：若交点v不是割点，则{块1}-{v}与{块2}-{v}仍连通， 则{块1}-{v}中至少存在1点v1且{块2}-{v}中至少存在1点v2，且v1到v2存在路径p。则在原图中块1并块2并路径p仍为无割点的连通图，与块的定义矛盾。
[此贴子已经被作者于2008-6-16 19:25:02编辑过]
|
|
-- 作者：Chojin -- 发布时间：6/16/2008 5:31:00 PM -- 删除(v1,v3)后剩下的只有一个块吧？ |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
15.625ms |