树的等价命题 G是树 种中两个顶证明其连通。 点之间有在唯一若不连通,假设有s个连通分支。每个连通无回路,为 的路径 树。则有m=n-<n-1 矛盾! 边后很到国仅 G无回路且 G连通且m=n-1 东南大学计算机科学与工程学院 同的出学 图论
证明其连通。 若不连通，假设有s个连通分支。每个连通无回路，为 树。则有m=n-s<n-1。 矛盾！
树的等价命题 G申两个顶 G无回路但加 点之间有在唯一 动后得到国仅得 个 对于任意G的边e,Ge的边的数目为n2,Ge不连G连通且任何边 通。所以e为桥。 都是桥 G无回路且 G连通且m=n-1 东南大学计算机科学与工程学院 同的出学 图论
对于任意G的边e，G-e的边的数目为n-2，G-e不连 通。所以e为桥
树的等价命题 由于G连通且任何边都是桥,因此对于任何两个顶 点若删除顶点间路径上的一条边都会使两顶点属 于不同连通分支,因此不存在回路。 G无回路,但增加一 边后得到且仅得 由于G连通,因此在任意一对顶点之间添加新边都 个圖 会形成圈。 设会形成一个以上的圈,则删除新边之后,新边 关联的两个顶点之间存在两条不同的通路,这和 G连通且任何边 都是桥 两个顶点存在唯一路径矛盾。 G无回络 东南大学计算机科学与工程学院 同的出学 图论
由于G连通且任何边都是桥，因此对于任何两个顶 点若删除顶点间路径上的一条边都会使两顶点属 于不同连通分支，因此不存在回路。 由于G连通，因此在任意一对顶点之间添加新边都 会形成圈。 设会形成一个以上的圈，则删除新边之后，新边 关联的两个顶点之间存在两条不同的通路，这和 两个顶点存在唯一路径矛盾
树的等价命题 G是树 G申两个顶 G无回路,但增加一 点之间有在唯一 边后得到且仅得 个圆 证明G连通。 对于任意两个顶点,添加一条边,可产生一个包 郁是 含e的圈C。ce为G中两个顶点的通路。 G回日 连通m= 东南大学计算机科学与工程学院 同的出学 图论
证明G连通。 对于任意两个顶点，添加一条边，可产生一个包 含e的圈C。C-e为G中两个顶点的通路
最少树叶数 定理162设T是n阶非平凡的无向树,则至少存在两片树叶 1、顶点数确定则边数确定 2、叶子顶点度为1; 根据定理16,1,n阶非平凡无向树的边数为n-1,度数为2n-2。 若叶子顶点为k个,则分支点数量为nk个,且其度数均大于等于2。 因此T的度数至少为2(n-k)+k=2n-k。 若k小于2,则T的度数将大于2n2,与定理161的结论矛盾 东南大学计算机科学与工程学院 同的出学 图论
定理 16.2 设T是n阶非平凡的无向树,则T至少存在两片树叶。 根据定理16.1，n阶非平凡无向树的边数为n-1，度数为2n-2。 若叶子顶点为k个，则分支点数量为n-k个，且其度数均大于等于2。 因此T的度数至少为2(n-k)+k=2n-k。 若k小于2，则T的度数将大于2n-2，与定理16.1的结论矛盾。 1、顶点数确定则边数确定； 2、叶子顶点度为1；