一 、 树 及 生 成 树 的 基 本 概 念 树 是 无 向 图 的 特 殊 情 况 ， 即 对 于 一 个 N个 节 点 的 无 向 图 ， 其 中 只 有 N-1条 边 ， 且 图 中 任意 两 点 间 有 且 仅 有 一 条 路 径 ， 即 图 中 不 存 在 环 ， 这 样 的 图 称 为 树 ， 一 般 记 为 T。 树 定 义 有 以下 几 种 表 述 ： (1)、 T连 通 、 无 圈 、 有 n个 结 点 ， 连 通 有 n－ 1条 边 ； (2)、 T无 回 路 ， 但 不 相 邻 的 两 个结 点 间 联 以 一 边 ， 恰 得 一 个 圈 ； (3)、 T连 通 ， 但 去 掉 任 意 一 边 ， T就 不 连 通 了 （ 即 在 点 集 合相 同 的 图 中 ， 树 是 含 边 数 最 少 的 连 通 图 ）； (4)、 T的 任 意 两 个 结 点 之 间 恰 有 一 条 初 等 链 。 例 如 ： 已 知 有 六 个 城 市 ， 它 们 之 间 要 架 设 电 话 线 ， 要 求 任意 两 个 城 市 均 可 以 互 相 通 话 ， 并 且 电 话 线 的 总 长 度 最 短 。 若 用六 个 点 v1… v6代 表 这 六 个 城 市 ， 在 任 意 两 个 城 市 之 间 架 设 电 话线 ， 即 在 相 应 的 两 个 点 之 间 连 一 条 边 。 这 样 ， 六 个 城 市 的 一 个电 话 网 就 作 成 一 个 图 。 任 意 两 个 城 市 之 间 均 可 以 通 话 ， 这 个 图必 须 是 连 通 图 ， 且 这 个 图 必 须 是 无 圈 的 。 否 则 ， 从 圈 上 任 意 去掉 一 条 边 ， 剩 下 的 图 仍然是 六 个 城 市 的 一 个 电 话 网 。 图 5-6是一 个 不 含 圈 的 连 通 图 ， 代 表 了 一 个 电 话 线 网 。 生 成 树 （ 支撑树 ） 定 义 ：如 果图 G’是 一 棵包含 G的 所有 顶点 的 树 ，则 称 G’是 G的 一 个 支撑树 或生 成 树 。例 如 ,图 5-7b是 图 5-7a的 一 个 支撑树 。 定 理： 一 个 图 G有 生 成 树 的 条 件是 G是 连 通 图 。 证明:必 要 性显然； 充分性:设 图 G是 连 通 的 ， 若 G不 含 圈 ， 则 按照定 义 ， G是 一 个 树 ，...
