2.树和小支树 树及其性质 在各种各样的图中,有一类图是 十分简单又非常具有应用价值的图 这就是树。 例83:已知有六个城市,它们之 要架设电话线,要求任意两个城 市均可以互相通话,并且电话线的 总长度最短
30 2.树和最小支撑树 一 、树及其性质 在各种各样的图中，有一类图是 十分简单又非常具有应用价值的图， 这就是树。 例8.3：已知有六个城市，它们之 间要架设电话线，要求任意两个城 市均可以互相通话，并且电话线的 总长度最短
2.树和小支树 如果用六个点v 点代表这六 个城市,在任意两个城市之间架设电话 线,即在相应的两个点之向连一条边。 这样,六个城市的一个电话网就作成 个图。由于任意两个城市之间均可以通 话,这个图必须是连通图。并且,这个 图必须是无圈的。否则,从圈上任意去 掉一条边,剩下的图仍然是六个城市的 个电话网。图8-8是一个不含圈的连 通图,代表了一个电话线网
2.树和最小支撑树 如果用六个点v1， …，v6代表这六 个城市，在任意两个城市之间架设电话 线，即在相应的两个点之间连一条边。 这样，六个城市的一个电话网就作成一 个图。由于任意两个城市之间均可以通 话，这个图必须是连通图。并且，这个 图必须是无圈的。否则，从圈上任意去 掉一条边，剩下的图仍然是六个城市的 一个电话网。图8-8是一个不含圈的连 通图，代表了一个电话线网
2.树和小支树 图8-8
32 2.树和最小支撑树 图8-8 v6 v3 v4 v2 v5 v1
2.树和小支树 定义81无圈的连通图叫做树。 性质 定理83设图G=(,E是一个树 P(G≥2,那么图G中至少有两个悬 挂点。 定理84图G=(Ⅳ,E)是一个树 的充要条件是G不含圈,并且有且 仅有P-1条边
2.树和最小支撑树 定义8.1 无圈的连通图叫做树。 性质： 定理8.3 设图G=(V，E)是一个树 P(G) ≥2，那么图G中至少有两个悬 挂点。 定理8.4 图G=（V，E）是一个树 的充要条件是G不含圈，并且有且 仅有P-1条边
2.树和最小支撑树 定理8.5图G=(V,E)是一个树 的充要条件是G是连通图,并 且有且仅有P-1条边。 乌定理86图G是一个树的充分必要 条件是任意两个顶点之间有且 仅有一条链
34 2.树和最小支撑树 定理8.5 图G=（V，E）是一个树 的充要条件是G是连通图，并 且有且仅有P-1条边。 定理8.6 图G是一个树的充分必要 条件是任意两个顶点之间有且 仅有一条链