作业帮 > 数学 > 作业

离散数学一道证明题证明:一个联通无向图G中的结点v是割点的充分条件是存在两个结点u和w,使得结点u和w的每一条路都通过v

来源:学生作业帮 编辑:百度作业网作业帮 分类:数学作业 时间:2024/07/17 18:42:46
离散数学一道证明题
证明:一个联通无向图G中的结点v是割点的充分条件是存在两个结点u和w,使得结点u和w的每一条路都通过v
离散数学一道证明题证明:一个联通无向图G中的结点v是割点的充分条件是存在两个结点u和w,使得结点u和w的每一条路都通过v
若结点v是连通图G=的一个割点,设删去v得到子图G',则G'至少包含2个连通分支.设其为G1=,G2=,任取u∈V1,w∈V2,因为G是连通的,故在G中必有一条连接u和w的路C,但u和w在G'中属于两个不同的连通分支,故u和w必不连通,因此C必须通过v,故u和w之间的任意一条路都通过v
反之,若连接图G中某两个结点的每一条路都通过v,删去v得到子图G',在G'中这两个结点必然不连通,故v是图G的割点.