2.树和最小支理树 如果用六个点V…V代表这六个城市, 在任意两个城市之间架设电话线,即在相应 的两个点之间连一条边。这样,六个城市的 个电话网就作成一个图。由于任意两个城 市之间均可以通话,这个图必须是连通图。 并且,这个图必须是元圈的。否则,从圈上 任意去掉一条边。剩下的图仍然是大个城市 的一个电话网。图8.8是一个不含圈的连通 图,代表了一个电话线网
32 2.树和最小支撑树 如果用六个点v1…v6代表这六个城市， 在任意两个城市之间架设电话线，即在相应 的两个点之间连一条边。这样，六个城市的 一个电话网就作成一个图。由于任意两个城 市之间均可以通话，这个图必须是连通图。 并且，这个图必须是无圈的。否则，从圈上 任意去掉一条边，剩下的图仍然是六个城市 的一个电话网。图8.8是一个不含圈的连通 图，代表了一个电话线网
2.树和小支树 5 图8.8
33 2.树和最小支撑树 图8.8 v6 v3 v4 v2 v5 v1
2.树和最小支理树 定义8.1一个无圈的连通图叫做树。 下面介绍树的一些重要性质 定理8.3设图G(V,E)是一个树PG) 今2,那么图G中至少有两个悬挂点。 定理8.4图G(V,B)是一个树的充要条 件是G不含圈。并且有且仅有P-1条边 件是禔是连通图,并且有且仅有1条说。 定理8.5图G(V,B)是一个树的充要条 定理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,E)是图G(V,D的 支撑子图,如果图(V,B)是一个树,那 么称是(的一个支撑树。 例如,图8.10b是图8.10a的一个支撑 树。 v6 图8.10V a V4 b
2.树和最小支撑树 二.支撑树 定义8.2 设图K=(V,E’)是图G=(V,E)的 一支撑子图,如果图K=(V,E’)是一个树,那 么称K是G的一个支撑树。 例如,图8.10b 是图8.10a 的一个支撑 树。 v6 v5 v2 v3 v4 v1 v6 v5 v2 v3 v4 v1 图8.10 a b