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