树的等价命题 由于G连通且任何边都是桥,因此对于任何两个顶 点若删除顶点间路径上的一条边都会使两顶点属 于不同连通分支,因此不存在回路。 G无回路,但增加一 边后得到且仅得 由于G连通,因此在任意一对顶点之间添加新边都 个圖 会形成圈。 设会形成一个以上的圈,则删除新边之后,新边 关联的两个顶点之间存在两条不同的通路,这和 G连通且任何边 都是桥 两个顶点存在唯一路径矛盾。 G无回络 东南大学计算机科学与工程学院 同的出学 图论由于G连通且任何边都是桥，因此对于任何两个顶 点若删除顶点间路径上的一条边都会使两顶点属 于不同连通分支，因此不存在回路。 由于G连通，因此在任意一对顶点之间添加新边都 会形成圈。 设会形成一个以上的圈，则删除新边之后，新边 关联的两个顶点之间存在两条不同的通路，这和 两个顶点存在唯一路径矛盾