一 、 树 及 生 成 树 的 基 本 概 念 树 是 无 向 图 的 特 殊 情 况 , 即 对 于 一 个 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是 一 个 树 ,...