树 无向树及其应用 生成树 根树及其应用 东南大学计算机科学与工程学院 同的出学 图论
无向树及其应用 生成树 根树及其应用
树 定义161连通无回路的无向图称为无向树,简称为树。每个连通 分支都是树的无向图称为森林。平凡图称为平凡树。在 无向树中,悬挂顶点称为树叶,度数大于或等于2的顶 点称为分支点。 存在子图与圈同构则不是树 东南大学计算机科学与工程学院 同的出学 图论
定义 16.1 连通无回路的无向图称为无向树，简称为树。每个连通 分支都是树的无向图称为森林。平凡图称为平凡树。在 无向树中，悬挂顶点称为树叶，度数大于或等于2的顶 点称为分支点
树的等价命题 定理16.1设 G是树 下面各命题 G无回路,但增加 G中任意两个顶 边后得到且仅 点之间存在唯 得一个圈 的路径 G连通且任何边 都是桥 G无回路且 m=n-1 G连通且m-1 东南大学计算机科学与工程学院 同的出学 图论
定理 16.1 设G=<V , E>是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