东南大学：《离散数学》课程教学资源（PPT课件讲稿）图论（树）

树 无向树及其应用 生成树 根树及其应用 东南大学计算机科学与工程学院 同的出学 图论

无向树及其应用 生成树 根树及其应用

树 定义161连通无回路的无向图称为无向树,简称为树。每个连通 分支都是树的无向图称为森林。平凡图称为平凡树。在 无向树中,悬挂顶点称为树叶,度数大于或等于2的顶 点称为分支点。 存在子图与圈同构则不是树 东南大学计算机科学与工程学院 同的出学 图论

定义 16.1 连通无回路的无向图称为无向树，简称为树。每个连通 分支都是树的无向图称为森林。平凡图称为平凡树。在 无向树中，悬挂顶点称为树叶，度数大于或等于2的顶 点称为分支点

树的等价命题 定理16.1设 G是树 下面各命题 G无回路,但增加 G中任意两个顶 边后得到且仅 点之间存在唯 得一个圈 的路径 G连通且任何边 都是桥 G无回路且 m=n-1 G连通且m-1 东南大学计算机科学与工程学院 同的出学 图论

定理 16.1 设G=是n阶m条边的无向图，则下面各命题 等价： G是树； G中任意两个顶点之间存在唯一的路径； G无回路且m=n-1； G连通且m=n-1； G连通且任何边都是桥； G无回路,但增加一边后得到且仅得一个圈；

树的等价命题 G是树 G中任意两个顶 碳何边率 点之间存在唯 由G的连通性可知,任意两个顶点之间存在路径; 的路径若路径不唯一,则存在回路。与G中无回路矛盾。 回路但非厕 边后很到国仅 G无回且 G围m= 东南大学计算机科学与工程学院 同的出学 图论

由G的连通性可知，任意两个顶点之间存在路径； 若路径不唯一，则存在回路。与G中无回路矛盾

树的等价命题 若G中存在回路,根据回路的长度分两种情况: 若G中的某个顶点v关联环,到自身存在长为0和1的两条 路径; G中任意两个顶 若G存在长度大于等于2的圈,则圈上任意两个顶点之间 点之间存在唯 存在两条不同的通路; 的路径 以上皆与任意顶点之间存在唯一路径矛盾,因此G中无 回路。 n=1时,平凡图中不存在环,边数为0,结论成立。 设n=k时结论成立,即边数m=k1。 G无回路且 当n=k+1时,删除G中任意一条边。由于G任意顶点间存 在唯一路径,因此G将生成两个连通分支G1、G2。由于 两个连通分支的顶点数n1、n2均小于等于k,因此边数 m1、m2分别为n1-1、n2-1,且有n1+n2=n=k+1。 因此G中边的数量为1+m1+m2=n-1=k 东南大学计算机科学与工程学院 同的出学 图论

若G中存在回路，根据回路的长度分两种情况： 若G中的某个顶点v关联环，到自身存在长为0和1的两条 路径； 若G存在长度大于等于2的圈，则圈上任意两个顶点之间 存在两条不同的通路； 以上皆与任意顶点之间存在唯一路径矛盾，因此G中无 回路。 n=1时，平凡图中不存在环，边数为0，结论成立。 设n=k时结论成立，即边数m=k-1。 当n=k+1时，删除G中任意一条边。由于G任意顶点间存 在唯一路径，因此G将生成两个连通分支G1、G2。由于 两个连通分支的顶点数n1、n2均小于等于k，因此边数 m1、m2分别为n1 -1、n2 -1，且有n1 + n2 =n=k+1。 因此G中边的数量为1+m1+m2 =n-1=k

树的等价命题 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；