2.树和最小支撑树 如果用六个点V1V代表这六个城市, 在任意两个城市之间架设电话线,即在相 应的两个点之间连一条边。这样,六个城 市的一个电话网就作成一个图。意义任洋 眼两个城市之间均可以通话,这个图必须 是连通图。并且,这个囹必须是无圈的。 否则。从圈上任意去掉一条边。剩下的图 仍然是六个城市的一个电话网。图8.8是 个不含圈的连通图。代表了一个电话线 网
33 2.树和最小支撑树 如果用六个点v1…v6代表这六个城市， 在任意两个城市之间架设电话线，即在相 应的两个点之间连一条边。这样，六个城 市的一个电话网就作成一个图。意义任洋 眼两个城市之间均可以通话，这个图必须 是连通图。并且，这个图必须是无圈的。 否则，从圈上任意去掉一条边，剩下的图 仍然是六个城市的一个电话网。图8.8是 一个不含圈的连通图，代表了一个电话线 网
2.树和最小支撑树 定义8.1一个无圈的连通图叫做树 下面介绍树的一些重要性质 定理8.3设图G(V,E)是一个树P(G 2,那么图G中至少有两个悬挂点。 定理8.4图G(V,E)是一个树的充要条 件是G不含圈,并且有且仅有P-1条边。 定理8.5图G(V,B)是一个树的充要条 件是禔是连通图,并且有且仅有B1条边 定理8.6图G是一个树的充分必要条件是 任意两个顶点之间有且仅有一条链
34 2.树和最小支撑树 定义8.1 一个无圈的连通图叫做树。 下面介绍树的一些重要性质： 定理8.3 设图G=（V，E）是一个树P(G) ≥2，那么图G中至少有两个悬挂点。 定理8.4 图G=（V，E）是一个树的充要条 件是G不含圈，并且有且仅有P-1条边。 定理8.5 图G=（V，E）是一个树的充要条 件是G是连通图，并且有且仅有P-1条边。 定理8.6 图G是一个树的充分必要条件是 任意两个顶点之间有且仅有一条链
2.树和最小支撑树 从以上定理,不难得出以下 结论 (1)从一个树中任意去掉一 条边,那么剩下的图不是连通图, 亦即,在点集合相同的囹中,树 是含边数最少的连通图。 (2)在树中不相邻的两个点 之间加上一条边。那么恰好得到 一个圈
35 2.树和最小支撑树 从以上定理，不难得出以下 结论： （1）从一个树中任意去掉一 条边，那么剩下的图不是连通图， 亦即，在点集合相同的图中，树 是含边数最少的连通图。 （2）在树中不相邻的两个点 之间加上一条边，那么恰好得到 一个圈
2.树和最小文撑树 支撑树 定义8.2设图K(V,F)是图G(V,B的 支撑子图,如果图/(V,B是一个树,那 么称尼是(的一个支撑树。 例如,图8.10b是图8.10a的一个支撑 树, V5 V V6 图8,10 v2 b
2.树和最小支撑树 二.支撑树 定义8.2 设图K=(V,E I )是图G=(V,E)的 一支撑子图,如果图K=(V,E I)是一个树,那 么称K是G的一个支撑树。 例如,图8.10b 是图8.10a 的一个支撑 树。 v6 v5 v2 v3 v4 v1 v6 v5 v2 v3 v4 v1 图8.10 a b
2.树和最小支撑树 显然,如果图(VB是图 G=(V,B的一个支撑树,那么的边数 是(O-1,中不属于支撑树K的边 数是q(G)-p(G)+1。 定理8.7一个图G有支撑树的充 要条件是足是连通图
37 2.树和最小支撑树 显然,如果图K=(V,E I )是图 G=(V,E)的一个支撑树,那么K的边数 是p(G)-1，G中不属于支撑树K的边 数是q(G)-p(G)+1。 定理8.7 一个图G有支撑树的充 要条件是G是连通图