图论基础通风网络

《图论基础通风网络》由会员分享，可在线阅读，更多相关《图论基础通风网络（102页珍藏版）》请在装配图网上搜索。

1、课 程 设 置 目 的该 门 课 在 工 程 应 用 中 的 重 要 性1） 矿 井 设 计2） 矿 井 改 扩 建3） 通 风 系 统 调 整4） 矿 井 灾 害 防 治 （ 瓦 斯 、 火 ）1） 风 量 分 配 与 调 整2） 风 流 方 向 判 断3） 通 风 设 施 合 理 位 置 的 选 择 4） 灾 害 烟 气 蔓 延 与 避 灾 路 线 的 选 择 系 统 规 划 系 统 合 并 单 一 风 井 工 作 授 课 计 划0 绪 论1 图 论 基 础 1.1 图 的 基 本 概 念 1.2 图 的 矩 阵 表 示 1.3 生 成 树 选 择 2 矿 井 通 风 网 络 2.1 矿

2、井 通 风 网 络 图 2.2 矿 井 通 风 网 络 内 风 流 变 化 的 规 律 2.3 通 风 网 络 分 析 与 数 学 模 型 实 验 授 课 计 划3 通 风 机 运 转 特 性 及 分 析 3.1 扇 风 机 特 性 的 数 学 描 述 3.2 扇 风 机 工 况 点 求 解 与 分 析 3.3 用 计 算 机 进 行 扇 风 机 优 选 4 复 杂 通 风 网 络 自 然 分 风 电 算 4.1 复 杂 通 风 网 络 解 算 概 述 4.2 回 路 法 解 算 复 杂 风 网 4.3 节 点 法 与 割 集 法 解 算 复 杂 风 网 4.4 风 网 自 然 分 风 算 法

3、 评 述 4.5 复 杂 风 网 自 然 分 风 电 算 程 序 实 例 实 验 授 课 计 划5 通 风 网 络 中 风 流 调 节 的 计 算 方 法 5.1 概 述 5.2 独 立 回 路 法 5.3 道 路 法 6 矿 井 通 风 网 络 优 化 6.1 矿 井 通 风 网 络 优 化 概 述 6.2 通 风 网 络 调 节 优 化 6.3 通 风 中 风 量 分 配 的 优 化 6.4 矿 井 通 风 系 统 优 化 设 计 简 介 授 课 计 划7 网 络 理 论 在 矿 井 通 风 中 的 应 用 7.1 在 通 风 设 计 中 的 应 用 7.2 在 通 风 管 理 中 的 应

4、 用 8 矿 井 火 灾 的 通 风 网 络 解 析 8.1 矿 井 火 灾 时 期 风 流 状 态 的 变 化 规 律 8.2 矿 井 火 灾 时 的 通 风 模 拟 8.3 矿 井 火 灾 时 风 流 控 制 8.4 矿 井 通 风 模 拟 软 件 示 例 实 验 1 图 论 基 础 -图 的 概 念 图 的 定 义顶 点或 节点 边 或分 支图 的 偶 对 表 示 :图 G G(V,E)节 点 V V(v 1,v2, vm) 节 点 集 m=|V| 节 点 数 边 E E(e1,e2, em) 边 集 n=|E| 边 数 1） 图 的 定 义指 某 类 具 体 事 物 和 这 些 事 物

5、 间 联 系 的 抽 象 描 述 。 v1 v2v3v 4v5v6 e1 e2e3e4e5 e6 e7e8e9 1.1 图 的 基 本 概 念 G（ m， n） 1 图 论 基 础 -图 的 概 念 图 的 定 义图 的 拓 扑 关 系 : 顶 点 和 边 间 的 联 接 关 系 。 有 限 图 无 限 图 空 图 （ m,n)图 根 据 m,n的 值 来 确 定 名 称 有 向 图 无 向 图 混 合 图 有 序 ， 含 有 有 向 边无 序 既 有 有 向 边 ， 又 有 无 向 边 1 图 论 基 础 -图 的 概 念 图 的 定 义图 的 几 何 表 示 图 的 图 解e1 e2e3

6、e4e6e 5 e7v1v2 v3 v4v5 e6v1v2 v3v4e1e2 e3e4e5 v1 v2v3v4v5v6 e1 e2e3e4e5 e6 e7e8e9图 G1点 集 ： V（ G1 ） = V(v1,v2, v5) 图 G1边 集 ： E（ G1 ） = E(e1,e2, e7)图 G1为 无 序 图 ， 各 边 的 联 接 可 表 示 为 e1=， e7=图 G2为 有 序 图 ， 各 边 的 联 接 可 表 示 为 e1=( v2 , v1 )， e6=( v1 , v4 )圆 括 号 表 示 有 序 偶 对 ， 尖 括 号 表 示 无 序 偶 对 。G1=（ 5， 7） G2

7、=（ 4， 6） G3=（ 6， 9） 1 图 论 基 础 -图 的 概 念 图 的 定 义关 联 与 邻 接 :邻 接 点 与 邻 接 边点 、 边 关 联 关 联 与 邻 接 的 区别v1 v 2v3v4v5v6 e1 e2e3e4e5 e6 e7e8e9 v1与 e1关 联v5与 v6邻 接 e2与 e3邻 接 1 图 论 基 础 -图 的 概 念 图 的 定 义 v1 v2v3v 4v5v6 e1 e2e3e4e5 e6 e7e8e9平 行 边 （ 重 边 ）圈 多 重 图重 边 数 量 叫 重 数 =2始 末 点 重 合 的 分 支 。阶节 点 个 数 。 完 全 图每 一 对 不

8、同 节 点 间 均 有 一 条 边 相 连m阶 完 全 图 有 多 少 条 边 ？ =m(m-1)/22 mC e6v1v2 v3v4e1e2 e3e4e5 e10简 单 图 1 图 论 基 础 -图 的 概 念 图 的 同 构2） 图 的 同 构表 示 节 点 和 边 的 关 联 关 系 ， 对 其 它 无 限 制 。 GG应 用 ： 根 据 需 要 将 通 风 系 统 图 转 变 成 通 风 网 络 图 。（ 4,6） 图 网 络 图 的 美 化 调 整213 4 13 24 123 4 32 41 1 图 论 基 础 -图 的 概 念 子 图3） 子 图 )()( GVHV 真 子 图

9、: GH )()( GEHE )()( GVHV GH )()( GEHE 或 H中 至 少 有 一 个 边 的 重 数 小 于 G中 对 应 边 的 重 数且 ： H中 边 的 重 数 不 超 过 G中 对 应 边 的 重 数生 成 子 图 : ),( 1EVH ),( EVG EE 1H是 包 含 了 图 G所 有 节 点 的 真 子 图生 成 子 图 是 原 图 的 真 子 图 ！若若 且 或 1 图 论 基 础 -图 的 概 念 子 图课 堂 练 习根 据 右 图1） 找 出 3个 子 图 ；2） 找 出 4个 真 子 图 ；3） 试 找 出 2个 生 成 子 图 e1e5e7 e8

10、e4e6e3 e2 e9 1 235 46 1 图 论 基 础 -图 的 概 念 赋 权 图4） 赋 权 图一 个 图 G=（ V， E） 与 定 义 在 E或 V上 的 权 或 权 函 数 ， 称 为一 个 网 络 或 赋 权 图 ， 亦 称 有 权 图 。在 通 风 网 络 中 ， 常 用 通 风 参 数 作 权 的 指 标 ， 如 风 阻 、 风量 、 风 压 等 。 一 般 将 权 值 注 在 分 支 旁 边 。 1 图 论 基 础 -道 路 与 回 路 链 闭 合 链 和 开 链1） 链对 于 图 G 的 p个 边 e1, e2 , ep ,如 果 有 p+1个 顶 点 序 列 v1

11、, v2 , vp+1 ,且 边ei 与 vi -1、 vi 关 联 （ i=1,2p),则 这 些 边 构 成 的 序 列 称 为 链 。eivi -1 vi 1 图 论 基 础 -道 路 与 回 路 链 简 单 链 :链 : 53483726345 vevevevevev 闭 链 : 53483726351 vevevevevev 例 37224834534 vevevevevev V3 V1 V2V4V5 e1 e2e3e4 e5 e6 e7e8 简 单 链 :基 本 链 :没 有 重 复 边 的 链没 有 重 复 顶 点 的 链 1 图 论 基 础 -道 路 与 回 路 路2） 路路道

12、 路 /通 路 : 一 条 不 闭 合 的 基 本 链方 向 一 致 的 路道 路 的 权 : 两 节 点 间 每 条 道 路 内 各 边 的 权 之 和 最 长 路 与 最 短 路回 路 : 始 点 和 终 点 重 合 的 基 本 链 V3 V1 V2V4V5 e1 e2e3e4 e5 e6 e7e8 1 图 论 基 础 -道 路 与 回 路 路e1e5e7 e8 e4e6e3 e2 e9 1 235 46课 堂 练 习根 据 右 图1） 找 出 经 过 2号 点 的 2条 路 ；2） 找 出 3个 回 路 。 1 图 论 基 础 -道 路 与 回 路 图 的 连 通 性连 通 图 :非 连

13、 通 图 : 图 G中 任 意 两 节 点 间 至 少 存 在 一 条 路3） 图 的 连 通 性 多 个 连 通 图 组 成v 1 v2v3 e5 e1e6e 7e8e4 e3 e2v4v5 1 图 论 基 础 -道 路 与 回 路 图 的 连 通 性图 的 秩 :m个 节 点 ,k个 分 离 部 分 ， 则 秩 r=m-k连 通 图 ， k=1， 则 秩 为 不 包 含 起 点 的 所 有 节 点 数单 向 连 通 图 :强 连 通 图 : v i vjvi vj 任 意 两 个 节 点 间 3） 图 的 连 通 性 1 图 论 基 础 -道 路 与 回 路 欧 拉 公 式4） 欧 拉 公

14、 式 重 点平 面 图 : 把 图 G画 在 平 面 上 ， 各 边 为 简 单 曲 线 ，除 节 点 外 任 意 两 边 均 不 相 交 。 1 图 论 基 础 -道 路 与 回 路 欧 拉 公 式4） 欧 拉 公 式网 孔 f: 在 自 然 网 眼 中 ， 网 眼 内 部既 不 含 节 点 ， 也 不 含 边欧 拉 公 式 : 内 部 回 路 数 C:自 然 网 眼 : 边 围 成 的 区 域f+m-n=2 =1 ?C=n-m+1联 系区 别 V3 V1 V2V4V5 e1 e2e3e4 e5 e6 e7e8 1 图 论 基 础 -树 树 的 概 念不 含 回 路 的 连 通 图 。 悬

15、挂 点仅 有 一 条 分 支 与 其 相 关 联 的 节 点 割 边去 掉 后 能 使 图 分 成 两 部 分 的 边 割 点去 掉 与 其 关 联 的 边 后 能 使 图 分 成 两 部 分 的 点树 枝割点与悬挂点有什么关系1)树 T DCA Be1 FE e2 1 图 论 基 础 -树 生 成 树 和 余 树2)生 成 树 和 余 树T是 图 G的 一 个 生 成 子 图 ， 且 是 一 棵 树 。包 含 所 有 节点 ； 不 唯 一生 成 树 生 成 树 : 包 含 图 G全 部 节 点 的 树 。 3 1 2 45 6 e1 e2e3 e4e5 e6e7 e8 e91 图 论 基 础

16、 -树 生 成 树 和 余 树 1 图 论 基 础 -树 生 成 树 和 余 树余 树 去 掉 生 成 树 T后 ， 剩 下 的 边 构 成 的 子 图余 树 中 即 可 含 有 回 路 ， 也 可 不 连 通 余 树 弦 数 ： 余 树 中 含 的 边余 树 弦 ： n-m+1 与 欧 拉 公 式有 何 联 系 ？ 1 图 论 基 础 -树 生 成 树 和 余 树 连 通 且 无 回 路 ； 连 通 且 有 m-1条 边 ； 无 回 路 ， 加 一 条 边 恰 有 一 条 回 路 ； 每 一 对 节 点 间 有 唯 一 的 一 条 路 ； 连 通 ， 任 一 边 均 为 割 边 ； 包 含

17、图 的 全 部 节 点 。生成树的特点图 G (7,11) 生 成 树 T 1 图 论 基 础 -树 生 成 树 和 余 树特 别 提 醒任 何 联 通 图 的 边 数 等 于 其 余 树 弦 数 和 树 枝 数 之 和 图 的 生 成 树 连 通 但 不 含 回 路余 树 既 可 含 回 路 ， 也 可 不 连 通任 何 图 的 边 数 等 于 其 余 树 弦 数 和 树 枝 数 之 和 1 图 论 基 础 -树 生 成 树 和 余 树特 别 提 醒生 成 树 与 余 树 之 间 的 区 别 节 点 数 方 面回 路 方 面连 通 性 方 面 1 图 论 基 础 -树 基 本 回 路3） 基

18、 本 回 路 由 一 条 余 树 弦 和 T的 树 枝 构 成的 回 路 ， 称 为 图 G关 于 生 成树 T的 基 本 回 路 。1)基 本 回 路 数 ；2)基 本 回 路 组 ；3)回 路 组 非 唯 一 性 ；4)基 本 回 路 也 叫 独 立 回 路 ；5)回 路 的 方 向 性 一 个 图 的 生 成 树 不 唯 一 基 本 回 路 组 也 不 唯 一V3 V1 V2V4V5 e1 e2e3e4 e5 e6 e7e8 1 图 论 基 础 -树 基 本 回 路3） 基 本 回 路1)基 本 回 路 或 独 立 回 路 数 ；2)基 本 回 路 组 ； 3 1 245 6 e1 e2

19、e3 e4e5 e6 e7 e8 e9 1 图 论 基 础 -树 最 大 树 与 最 小 树4） 最 大 树 与 最 小 树生 成 树 的 权 ： 一 颗 生 成 树 上 所 有 树 枝 权 总 和 。最 大 树 Tmax 最 小 树 Tmin 1 图 论 基 础 -树 最 大 树 与 最 小 树图 的 最 小 树 是 （ ） 的 树 。 唯 一 的不 唯 一权 最 小图 的 最 大 树 是 （ ） 的 树 。思 考 以 上 都 不 是权 最 大 1 图 论 基 础 -割 集 割 集 的 定 义割 集 S是 连 通 图 G 的 边 的 集 合 ,把 S从 G 中 移 去 ,使 图 G 仅 成为

20、 两 部 分 ,但 如 少 移 去 S中 的 一 条 边 ,则 图 G 仍 是 连 通 的 。1） 割 集 定 义1 2 3 54 b fgd a c S4eS1S2 S3 1） 割 集 为 虚 线 相 交 的 边 的 集 合 ； 2） 边 的 最 小 集 合 ； 3） 若 分 成 两 个 以 上 部 分 ， 非 割 集割 集 ： S1=d,e,g; S2=a,c,e,g 1 图 论 基 础 -割 集 割 集 的 定 义割 点去 除 该 点 后 ， 图 分 为 两 个 部 分 。连 通 图 中 ， 除 了 割 点 （ 如 3） 外 ， 与 任 一 点 相 连 的边 的 集 合 均 构 成 一

21、个 割 集 。 1 42 35 6 7 1 2 354 b fgd a c S4eS1S2 S3 1 图 论 基 础 -割 集 割 集 的 方 向2） 割 集 方 向1） 有 向 割 集 ；2） 割 集 正 方 向 的 确 定 ；3） 正 向 边 与 负 向 边 。以 虚 线 面 为 界 ， 可 把 割 集 内 向 外 穿 出的 方 向 定 为 割 集 的 正 方 向 ， 也 可 把 割集 外 向 内 穿 入 的 方 向 定 为 正 方 向 。1 2 354 b fgd a c S4eS1S2 S3 1 图 论 基 础 -割 集 割 集 与 生 成 树 关 系3） 割 集 与 生 成 树 关

22、系生 成 树 ： 连 通 图 G的 全 部 节 点 的 最 小 边 集 合 ；割 集 ： 将 连 通 图 G的 节 点 分 为 不 相 连 的 二 个 节 点 子 集 的 最 少 边 集 合 。连 通 图 G的 一 个 割 集 S至 少 包 含 图 G的 生 成 树 的 一 条 树 枝 。 1 图 论 基 础 -割 集 基 本 割 集4） 基 本 割 集S1， s2， s3， s4是 关 于 T的 基 本 割 集 组 。 结 论 ： 基 本 割 集 组 是 线 性 无 关 的 。基 本 割 集 只 能 包 含 一 条 树 枝 基 本 割 集 数 =树 枝 数41 2 35d fga bces1

23、 s2s4s3 T=（ a,b,d,f）ad b f 1 图 论 基 础 -割 集 基 本 割 集 3 1 245 6 e1 e2e3 e4e5 e6e7 e8 e9 1 图 论 基 础 -割 集 基 本 割 集说 明 :基 本 割 集 只 能 包 含 一 条 树 枝 基 本 割 集 数 =树 枝 数 =m-1基 本 回 路 只 能 包 含 一 条 余 树 弦 基 本 回 路 数 =余 树 弦 数 =n-m+1重 点 1 图 论 基 础 -割 集 基 本 割 集连 通 平 面 图 G(m， n) 独 立 回 路 数 为 ( )秩 为 ( )余 树 弦 为 ( ) n-m+1m-1n-m+1重

24、点图 的 树 枝 数 与 独 立 回 路 相 等不 等无 关 系图 的 余 树 枝 与 独 立 回 路 数考 考 你 1 图 论 基 础 -割 集 基 本 割 集重 点独 立 回 路 分 支 的 正 负 号基 本 割 集 分 支 的 正 负 号 基 本 割 集 内 ， 以 树 枝 方 向为 准 ， 与 其 同 向 者 为 正 ，反 之 为 负 独 立 回 路 分 支 方 向 以 余 数弦 分 支 方 向 为 准 ， 与 其 同向 者 为 正 ， 反 之 为 负 。 1 图 论 基 础 -图 的 矩 阵 表 示 邻 接 矩 阵1） 邻 接 矩 阵 表 示 图 的 节 点 间 邻 接 关 系 的

25、矩 阵 nmijaA )( ；vvvv vv，vva jiji jijiij 不 邻 接 时与或当 且邻 接与若,0 ;,1构 造 方 阵其 中 ：1.2 图 的 矩 阵 表 示 1 图 论 基 础 -图 的 矩 阵 表 示 邻 接 矩 阵例 e1 e2 e4 e5e3v1 v3v2 v4（ 1） 每 一 行 的 1表 示 什 么 意 思 ？ （ 2） 每 一 列 的 1表 示 什 么 意 思 ？（ 3） 非 零 数 的 数 量 与 图 有 什 么 关 系 ？ 43214321 0110 0011 0001 0000 vvvvvvvvA 1 图 论 基 础 -图 的 矩 阵 表 示 邻 接 矩

26、 阵思 考（ 1） 如 何 构 造 无 向 图 的 邻 接 矩 阵 ？e1 e2 e4 e5e3v1 v3v2 v4 43214321 0110 1011 1101 0110 vvvvvvvvA 1 图 论 基 础 -图 的 矩 阵 表 示 邻 接 矩 阵思 考（ 2） 如 何 构 造 非 简 单 有 向 图 的 邻 接 矩 阵 ？e1 e2 e4 e5e3v1 v3v2 v4e6 43214321 0110 0021 0001 0000 vvvvvvvvA 1 图 论 基 础 -图 的 矩 阵 表 示 关 联 矩 阵2） 关 联 矩 阵表 示 图 的 节 点 和 边 的 关 联 关 系 的

27、矩 阵 。 nmijbB )(1,1,0,ij i j ib i j ii j 节 点 与 边 关 联 ,且 为 始 节 点 ；节 点 与 边 关 联 ,且 为 终 节 点 ；节 点 与 边 不 关 联 。构 造 方 阵其 中 ：（ 1） 完 全 关 联 矩 阵 1 图 论 基 础 -图 的 矩 阵 表 示 关 联 矩 阵 1110104 0111003 0001112 1000011 fedcbaBeb a d f21 34 ce 矩 阵 Be的 行 向 量 是 线 性 相 关 的 ，矩 阵 的 秩 R=3（ 4-1） . 1 图 论 基 础 -图 的 矩 阵 表 示 关 联 矩 阵（ 2）

28、 基 本 关 联 矩 阵在 m阶 连 通 图 G的 完 全 关 联 矩 阵 Be中 ,划 去 任 一 行 后 ,所 得 的 (m-1) n矩 阵 ,称 为 图 G的 基 本 关 联 矩 阵 ， 简 称 关 联 矩 阵 ， 记 作 B。 划 去 的 对 应点 称 为 参 考 点 。b ad f12 34 ce 4111010 3011100 2000111 fedcbaB基 本 关 联 矩 阵 线 性 独 立 。通 常 ，通风网络中划去的节点为大气节点。 1 图 论 基 础 -图 的 矩 阵 表 示 关 联 矩 阵思 考 e1 e2 e4 e5e3v1 v3v2 v4（ 1） 写 出 下 图 的

29、 关 联 矩 阵 。 1 图 论 基 础 -图 的 矩 阵 表 示 关 联 矩 阵思 考（ 2） 根 据 下 面 的 关 联 矩 阵 ， 绘 制 对 应 的 网 络 图 。1 2 3 4 5 6 71 1 1 0 0 0 0 02 1 0 1 0 1 0 03 0 0 1 1 0 1 0 4 0 1 0 1 0 0 15 0 0 0 0 1 1 1e e e e e e e evvB vvv 1 图 论 基 础 -图 的 矩 阵 表 示 回 路 矩 阵3） 回 路 矩 阵表 示 一 个 图 的 边 与 回 路 关 系 的 矩 阵 。（ 1） 完 全 回 路 矩 阵1, , 1, ,0,ij j

30、 i jCe j i jj i 边 在 回 路 内 且 边 与 回 路 方 向 一 致边 在 回 路 内 且 边 与 回 路 方 向 相 反边 不 在 回 路 内 imax=2n-m+1-1jmax=n互 异 回 路 ： 至 少 有 一 条 边 不 同 的 回 路包 含 图 的 所 有 互 异 回 路 的 矩 阵 。 1 图 论 基 础 -图 的 矩 阵 表 示 回 路 矩 阵6dc ba41 523回 路 个 数 ： 2 6-4+1-1=7 7654321011011 011100 101001 110111 101110 110010 000111 654321 CCCCCCCCe 1 图

31、 论 基 础 -图 的 矩 阵 表 示 回 路 矩 阵6dc ba41 523 7654321011011 011100 101001 110111 101110 110010 000111 654321 CCCCCCCC e )1,3,2(1 C )5,6,2(2 C )4,6,3,2(3 C 214 CCC 315 CCC 326 CCC 3217 CCCC 若 生 成 树 为 T=(2,3,6)， 余 树 弦 为 （ 1,4,5） 1 图 论 基 础 -图 的 矩 阵 表 示 回 路 矩 阵完 全 回 路 矩 阵 的 特 点 每 一 行 对 应 一 个 回 路 ； 每 行 非 零 元 素

32、 组 成 一 个 回 路 ； 行 数 ： 2n-m+1; 各 行 之 间 并 非 线 性 独 立 ； 秩 为 n-m+1（ 独 立 回 路 数 ） 。 7654321011011 011100 101001 110111 101110 110010 000111 654321 CCCCCCCCe 独 立 回 路 矩 阵 能 反 映 完 全回 路 性 质 ， 没 有 必 要 写 完全 回 路 矩 阵 ？ 1 图 论 基 础 -图 的 矩 阵 表 示 回 路 矩 阵互 异 回 路 与 独立 回 路 的 区 别 回 路 数 方 面线 性 相 关 方 面 独 立 回 路 数 为 n-m+1互 异 回

33、路 为 2n-m+1-1个独 立 回 路 是 线 性 独 立 的互 异 回 路 则 是 线 性 相 关 的 1 图 论 基 础 -图 的 矩 阵 表 示 回 路 矩 阵（ 2） 基 本 回 路 矩 阵基 本 回 路 矩 阵 一 般 是 在 某 个 生 成 树 的 基 础 上 提 出 的 。1, ,1, ,0,ij j i jC j i jj i 边 在 回 路 内 且 边 与 回 路 方 向 一 致边 在 回 路 内 且 边 与 回 路 方 向 相 反边 不 在 回 路 内 imax=n-m+1jmax=n 321101110 110010 000111 654321 CCCC 6dc ba4

34、1 523C1 C2C3 若 生 成 树 为 T=(2,3,6)， 余 树 弦 为 （ 1,4,5） 1 图 论 基 础 -图 的 矩 阵 表 示 回 路 矩 阵 111100 101010 011001 632451, fCIC1)基 本 回 路 矩 阵 的 秩 等 于 ： n-m+12)余 树 弦 在 前 、 树 枝 在 后 分 为 两 部 分 ：6dc ba41 523C1 C2C3 生 成 树 为 T=(2,3,6)， 余 树 弦 为 （ 1,4,5）基 本 回 路 矩 阵 的 性 质 1 图 论 基 础 -图 的 矩 阵 表 示 割 集 矩 阵4） 割 集 矩 阵（ 1） 完 全 割

35、 集 矩 阵 表 达 图 的 边 与 割 集 关 系 的 矩 阵包 含 图 G的 全 部 割 集 的 矩 阵1, S ;1, ; 0, .iij iijS j Sj S 若 边 在 割 集 内 ， 且 与 割 集 同 向若 边 在 割 集 内 ， 且 与 割 集 反 向边 不 在 割 集 内 1 图 论 基 础 -图 的 矩 阵 表 示 割 集 矩 阵 765432 1110101 010110 011011 001101 111000 101110 100011 SSSSSSSfedcbaS e 1 图 论 基 础 -图 的 矩 阵 表 示 割 集 矩 阵取 生 成 树 ),( ecaT 余

36、 树 弦 ),( fdb可 发 现 ),( ),( ),( 32 1 fedS fbcdS fbaS ),( ),( ),( ),( 3217 326 315 214 fecaSSSS ebcSSS edbaSSS cdaSSS 7654321110101 010110 011011 001101 111000 101110 100011 SSSSSSS fedcbaS e 1 图 论 基 础 -图 的 矩 阵 表 示 割 集 矩 阵（ 2） 基 本 割 集 矩 阵 ),(100110 010111 001101 ISecafdbS f同 一 个 图 ， 有 不 同 的 生 成 树 ， 故 基

37、 本 割 集 也 不 相 同 。列 ： 余 树 在 前 ， 树 枝 在 后 ；行 ： 按 树 枝 在 矩 阵 内 的 列 序 排 序 1 1 0 0 0 10 1 1 1 0 10 0 0 1 1 1a b c d e fS 1 图 论 基 础 -图 的 矩 阵 表 示 矩 阵 间 关 系5） 矩 阵 间 关 系 (自 学 )生 成 树 ),( 5431 eeeeT 余 树 弦 ),( 762 eee 1000110 0100101 0110010 1011000 5431762 eeeeeeeB 1211 BB 关 联 矩 阵V1V2 V3 V4 V5e1 e2e5 e3 e4e6 e7 1

38、 图 论 基 础 -图 的 矩 阵 表 示 矩 阵 间 关 系 3215431762 1110100 1010010 0111001 CCCeeeeeeeC 1211 CC 12CIC生 成 树 ),( 5431 eeeeT 余 树 弦 ),( 762 eee 回 路 矩 阵V1V2 V3 V4 V5e1 e2e5 e3 e4e6 e7 1 图 论 基 础 -图 的 矩 阵 表 示 矩 阵 间 关 系生 成 树 ),( 5431 eeeeT 余 树 弦 ),( 762 eee割 集 矩 阵 1000110 0100101 0010111 0001001 5431762 eeeeeeeS 121

39、1 SS 4321SSSS S11 IS V1V2 V3 V4 V5e1 e2e5 e3 e4e6 e7 1 图 论 基 础 -图 的 矩 阵 表 示 矩 阵 间 关 系V1V 2 V3 V4V5e1 e2e5 e3 e4e6 e7 关 联 矩 阵 B与 回 路 矩 阵 C的 关 系 00 TT CBBC 或 TT BBC )( 1121112 TTC BBIC )(, 11211 回 路 矩 阵 C与 割 集 矩 阵 S的 关 系 00 TT SCCS 或 TCS 1211 ),( 12 sT ICS 割 集 矩 阵 S与 割 集 矩 阵 的 关 系1111211 BBS ),( 11112

40、 sIBBS 1 图 论 基 础 -生 成 树 的 选 择1.3生 成 树 的 选 择知 识 点n 生 成 树 的 选 择n 独 立 回 路 的 选 择 既 是 本 章 重 点又 是 本 章 难 点 1 图 论 基 础 -生 成 树 的 选 择最 大 树最 小 树任 意 树生 成 树 的 类 型 根 据 权 值 大小 进 行 划 分 L1L3L2 L4 L5L6 1 图 论 基 础 -生 成 树 的 选 择破 圈 法加 边 法收 缩 法生 成 树 的 选 择 方 法常 用 253 1 图 论 基 础 -生 成 树 的 选 择 破 圈 法1） 破 圈 法6 21） 画 网 络 图 ,将 点 、

41、边 编 号 ， 标 出 风 向 ： m=4 ,n=62） 确 定 图 的 余 树 弦 数 （ 即 独 立 回 路 数 ） N: N=n-m+1=33） 将 分 支 按 权 （ 风 阻 ） 大 小 排 序 ： R1、 R6、 R4、 R2、 R5、 R34） 从 权 最 大 的 分 支 起 ， 依 次 从 图 中 除 去 ， 移 去 后 被 破 坏的 回 路 ， 即 可 能 是 独 立 回 路 。 若 被 破 坏 的 回 路 中 ， 有一 条 以 上 高 阻 分 支 ， 应 重 选 ；5） 重 复 4） ， 直 到 移 去 n-m+1条 余 树 弦 ， 剩 余 的 分 支 即 组成 最 小 风

42、阻 树 Tmin选 择 最 小 树为 什 么 可 能 是 独 立 回 路 ？4 1CDB A 1 图 论 基 础 -生 成 树 的 选 择 破 圈 法为 什 么 可 能 是 独 立 回 路 ？ D A B C3 6 4 25 1以 分 支 3为 例 ： 去 掉 分 支 3 )2,4,3(1 C )2,5,6,3(2 C )1,6,3(3 C3个 回 路 被 破 坏 ,哪 个 是 独 立 回 路 ？ 1 图 论 基 础 -生 成 树 的 选 择 破 圈 法注 意 ： 若 被 破 坏 的 回 路 中 ， 有 一 条 以 上 高 阻 分 支 ， 应 重 选 ！D A B C6 13 25R1、 R6

43、、 R4、 R2、 R5、 R3以 分 支 3为 例 ：如 果 ： 4)2,4,3(1 C )2,5,6,3(2 C )1,6,3(3 C 1 图 论 基 础 -生 成 树 的 选 择 破 圈 法破 圈 法 选 择 最 小 树 D A B C6 4 13 25高 阻 分 支 ： 3， 5， 2最 小 风 阻 树 : Tmin=(1， 6， 4)余 树 弦 ： ， ， 独 立 回 路 （ ， 1， 6） （ ， -4， -6） （ ， 1， 4， 6）D A B C3 6 4 25 1 1 图 论 基 础 -生 成 树 的 选 择 破 圈 法结 果 检 验 : 每 加 入 一 条 余 树 弦 ，

44、 便 构 成 一 个 独 立 回 路 。D A B C6 4 13 25 1 图 论 基 础 -生 成 树 的 选 择 破 圈 法思 考 V1V 2 V3 V4V5e1 e2e5 e3 e4e6 e7 用 破 圈 法 找 出 左 图 最 大 树 。各 分 支 风 阻 大 小 升 序 为 ： e6，e2， e3， e1， e7， e4， e5 1 图 论 基 础 -生 成 树 的 选 择 加 边 法2） 加 边 法 加 边 法 选 择 最 大 树 D AB C3 26 54 1R1、 R6、 R4、 R2、 R5、 R3 4） 重 复 3） ， 将 所 有 边 都 加 过 后 ， 取 走 n-m

45、+1条 余 树 弦 ， 剩 余 的（ m-1)条 边 ， 即 构 成 一 棵 生 成 树 。3） 加 边 ， 即 按 一 定 的 顺 序 将 边 加 到 图 中 原 位 置 。 每 加入 一 条 边 都 要 判 断 是 否 构 成 回 路 ， 构 成 回 路 ， 则 这 条 边就 是 余 树 弦 ， 将 它 取 走 ， 计 入 余 树 弦 集 合 ； 若 新 加 入 的分 支 未 构 成 回 路 ， 说 明 它 是 树 枝 ， 计 入 树 枝 集 合 ；2） 将 分 支 按 权 排 序 ；1） 将 图 去 边 留 点 ； 1 图 论 基 础 -生 成 树 的 选 择 -收 缩 法3） 收 缩

46、法 选 择 最 小 树步 骤 ：1） 绘 网 络 图 ， 将 节 点 、 分 支 编 号 ， 并 标 出 风 向 ；2） 计 算 生 成 树 枝 数 和 独 立 回 路 数 ， 并 将 边 按 权 大 小 排 序 ；3） 从 权 最 小 的 分 支 起 ， 由 始 点 向 终 点 收 缩 （ 始 点 与 最 小 权 分 支 被 收 缩 ） ， 将 此分 支 号 授 于 所 有 与 其 始 点 连 接 的 分 支 ， 如 某 分 支 号 重 复 出 现 ， 则 消 去 此 分 支号 ；4） 如 收 缩 边 始 末 点 合 一 ， 即 构 成 一 个 回 路 。 此 始 末 点 合 一 的 分 支

47、 ， 即 为 余 树 弦 ，将 其 计 入 余 树 弦 集 ；5） 如 未 形 成 回 路 ， 则 依 次 收 缩 权 较 小 的 分 支 ； 6） 重 复 5） ， 直 到 最 后 一 个 节 点 。 收 缩 过 程 中 始 末 点 合 一 的 分 支 即 为 余 树 弦 ， 去 掉 余 树 弦 后 剩 余 的 子 图 即 为 最 小生 成 树 。 收 缩 过 程 中 形 成 的 回 路 ， 即 为 相 应 的 独 立 回 路 。 1 图 论 基 础 -生 成 树 的 选 择 收 缩 法步 骤 ： 1） 从 权 最 小 的 边 1开 始 收 缩 ,边 1与 节 点 B被 A吸 收 ,与 点

48、B相 连的 分 支 5、 6均 被 授 于 分 支 号 1（ 如 图 b)。 例 ： 选 择 最 小 树 图 a余 树 弦 数 与 树 枝 数 皆 为 3， 分 支 按 风阻 赋 权 ， 按 风 阻 升 序 排 列 为 1,6,4,2,5,3。A(1)B 1 图 论 基 础 -生 成 树 的 选 择 收 缩 法步 骤 ： 2） 此 时 未 形 成 回 路 ， 依 次 收 缩 权 小 的 分 支 6， D点 、 边 6被 A点 吸 收 （ 如图 c)。 此 时 分 支 3、 6、 1形 成 一 个 回 路 ， 分 支 3始 末 点 重 合 ， 为 余 树 弦 ，将 此 记 于 余 树 弦 集 内

49、 。 A(1)B(6)DR1、 R6、 R4、 R2、 R5、 R3 1 图 论 基 础 -生 成 树 的 选 择 收 缩 法步 骤 ：3） 然 后 再 收 缩 分 支 4， 从 C向 A收 缩 ， 点 C、 边 4被 A点 吸 收 ， 分 支 2与 5的 始 末 点 均 重 合 ， 构 成 两 个 回 路 。 将 收 缩 边 4， (6)， (1)标 于 与 C相 连 的 分 支 2、 5上 ，形 成 两 个 回 路 是 (5， (4)， (6)， (1)， (1)和 (2， 4， (6)， (1)， 前 个 回 路 内 分支 号 1重 复 出 现 ， 消 去 分 支 号 1， 该 回 路

50、实 际 组 成 是 (5， -4， -6)(图 d)。A(1)B(6)D(4)CR1、 R6、 R4、 R2、 R5、 R3 1 图 论 基 础 -生 成 树 的 选 择 收 缩 法步 骤 ： 4） 收 缩 过 程 中 最 后 形 成 回 路 的 分 支 3、 5、 2是 余 树 弦 。 除 去 余 树 弦 后 ， 剩 余的 子 图 即 是 要 求 的 最 小 树 Tmin=(1,4,6)(图 e)。 相 应 的 独 立 回 路 为 (3,6,1)，(5,-4,-6)， (2,4,6,1)。 分 支 前 负 号 表 示 该 分 支 与 余 树 弦 分 支 风 向 相 反 。 1 图 论 基 础

51、 -独 立 回 路 选 择 矩 阵 运 算 法1） 矩 阵 运 算 法2） 试 探 回 朔 法3） 双 通 路 法独 立 回 路 的 选 择 1 图 论 基 础 -独 立 回 路 选 择 矩 阵 运 算 法1） 矩 阵 运 算 法 (自 学 ) 1211,BBB )(, 1211 TTC BBIC 余 树 弦 在 前 、 树 枝 在 后 的 顺 序 ， 建 立 基 本 关 联 矩 阵 ：利 用 关 联 矩 阵 与 回 路 矩 阵 的 关 系 ， 计 算 出 独 立 回 路 矩 阵 ： 1 图 论 基 础 -独 立 回 路 选 择 试 探 回 溯 法2） 试 探 回 朔 法前 提 ： 生 成 树

52、 和 余 树 弦 已 知 ！思 路 ： 往 生 成 树 中 逐 个 添 加 余 树 弦 ， 根 据 余 树 弦 的 终 点 找 出 与之 相 连 的 树 枝 ， 以 此 找 出 一 条 链 ， 当 链 的 末 端 是 余 树 弦 的 始点 时 ， 该 链 即 为 找 出 的 包 含 该 余 树 弦 回 路 。 1 图 论 基 础 -独 立 回 路 选 择 试 探 回 溯 法1） 取 一 条 余 树 边 作 为 链 ， 由 其 终 点 出 发 ， 在 树 枝 中 寻 找 回 路 的 其 他 分 支 ，当 某 树 枝 与 该 终 点 相 连 时 ， 将 链 终 点 前 移 ， 并 记 忆 该 分

53、支 ；2） 判 断 是 否 构 成 回 路 。 当 某 树 枝 一 端 点 联 接 链 的 终 点 ， 另 一 端 点 与 链 的始 点 重 合 时 ， 说 明 已 构 成 回 路 ， 转 入 4） ；3） 寻 找 回 路 组 成 的 进 程 中 ， 当 发 现 找 不 到 树 枝 与 链 的 终 点 相 连 时 ， 应 按原 路 逐 点 回 朔 ， 在 后 退 中 寻 找 新 通 路 ， 且 将 走 不 通 的 分 支 加 以 记 忆 ；4） 当 已 形 成 一 个 回 路 时 ， 记 录 回 路 的 组 成 ， 且 将 已 联 通 和 不 通 的 记 忆 标志 解 除 ； 回 路 组 成

54、中 ， 以 余 树 弦 方 向 为 正 ， 与 其 同 向 分 支 为 正 ， 逆 向 分 支 为 负 ；5） 重 复 上 过 程 ， 直 到 形 成 n-m+1个 回 路 。方 法 ： 1 图 论 基 础 -独 立 回 路 选 择 试 探 回 溯 法试 探 回 朔 法 例1） 生 成 树 ： T （ 1， 6， 4）2） 余 树 弦 ： T （ 2， 5， 3）3） 分 支 按 权 升 序 排 列 ： 1， 6， 4， 2， 5， 34） 独 立 回 路 数 ： 6 4 1 3 D A B C6 4 13 25 1 图 论 基 础 -独 立 回 路 选 择 试 探 回 溯 法试 探 回 朔

55、法1） 取 余 树 弦 3作 链 ， 从 其 终 点 D出 发 ， 沿 升 序 对 树 枝 逐 一 进 行 访 问 ， 检 查各 树 枝 是 否 与 D相 连 ， 第 一 遍 访 问 树 枝 时 ， 树 枝 6与 D相 连 ， 将 链 的 终 点 前 移 到 B， 从 B点 继 续 寻 找 相 连 的 树 枝 ， 分 支 1能 与 B相 连 ， 将 链 的终 点 前 移 到 A， 此 时 链 的 始 点 与 终 点 重 合 ， 形 成 第 一 个 回 路C1 （ 3， 6， 1） 。例 D A B C36 4 1R1、 R6、 R4、 R2、 R5、 R3 1 图 论 基 础 -独 立 回 路

56、 选 择 试 探 回 溯 法DA BC3 64 AE F0层 1层 2层 3层1 1 图 论 基 础 -独 立 回 路 选 择 试 探 回 溯 法D A B C6 4 5 12） 再 取 余 树 弦 5， 从 其 终 点 B始 ， 逐 一 寻 找 能 相 连 的 树 枝 ，对 树 枝 第 一 遍 访 问 时 ， 分 支 1能 连 上 ， 接 着 从 A点 继 续寻 找 与 之 相 连 的 树 枝 ， 从 图 中 可 以 看 出 ， 无 树 枝 与 A相连 ， 记 忆 分 支 1不 能 通 过 ， 将 链 的 终 点 回 朔 到 B点 ， 重新 寻 找 与 B点 相 连 的 树 枝 ， 跳 过

57、树 枝 1， 树 枝 6能 与 B相连 ， 将 链 的 终 点 前 移 到 D， 再 从 D点 寻 找 相 连 的 树 枝 ， 联 接 分 支 4形 成 第 二 条 回 路 C2 （ 5， 6， 4） 注 ： 分 支 前 负 号 表 示 其 方 向 与 余 树 弦 相 反 。试 探 回 朔 法例 1 图 论 基 础 -独 立 回 路 选 择 试 探 回 溯 法试 探 回 朔 法例 D A B C6 4 2 13） 最 后 取 余 树 弦 2， 从 其 终 点 C起 ， 寻 找 相连 的 树 枝 ， 联 分 支 4， 再 从 D点 寻 找 相 连 的树 枝 ， 联 接 分 支 6， 再 从 B点

58、 寻 找 相 连 的 树枝 ， 联 接 分 支 1， 形 成 第 三 个 回 路C 3 （ 2， 1， 6， 4） 1 图 论 基 础 -独 立 回 路 选 择 双 通 路 法双 通 路 法选 定 图 的 余 树 和 生 成 树 后 ,任 取 一 节 点 作 为 树 根 ， 从 每 一 余 树 弦 的始 、 末 点 向 树 根 方 向 寻 找 通 路 ， 当 两 通 路 在 某 一 节 点 处 相 交 时 ，即 形 成 一 个 回 路 ， 两 通 路 的 分 支 与 这 条 余 树 弦 即 为 回 路 的 组 成 。10 11 后 通 路前 通 路 1 ji X余 树 弦 邻 接 节 点 ：

59、指 与 某 节 点 i相 邻 且 靠 近 树 根 的 节 点 j；关 联 分 支 ： 是 与 （ i,j)节 点 对 应 的 树 枝 k， 且 规 定 当 k的 方 向 是 由 ji时 为 正 ， 由 ij时 为 负前 提 条 件 ： 生 成 树 和 余 树 弦 已 知 ！ 1 图 论 基 础 -独 立 回 路 选 择 双 通 路 法操 作 步 骤 ：1） 指 定 树 根 ， 并 计 算 各 节 点 与 树 根 间 的 分 支 数 ， 存 入 距 离 数 组 LEN；2） 形 成 生 成 树 的 邻 接 节 点 数 组 INC与 关 联 分 支 数 组 NUM： 生 成 树 的 中 某 树 枝

60、 k的 始 节 点 为 i,未 节 点 为 j， 若 LEN(i)LEN(j),则 ： INC(j)=i， NUM(j)=k； 否 则 INC(j)=j， NUM(i)=-k3） 形 成 回 路 4） 重 复 3） ， 直 到 选 出 n-m+1个 回 路 为 止 。10 11 后 通 路前 通 路 1 ji X余 树 弦 1 图 论 基 础 -独 立 回 路 选 择双 通 路 法 例 1 3425 6 123 4 568 7 91） n=9， m=62） 生 成 树 ： T （ 2， 4， 5， 6， 8） 3） 余 树 弦 ： T （ 1， 3， 7， 9）4） 独 立 回 路 数 ： 9

61、 6 1 41 3425 624 568 1 图 论 基 础 -独 立 回 路 选 择 双 通 路 法双 通 路 法 例 1 3425 624 5681)以 节 点 1作 树 根 ， 计 算 各 节 点 与 树 根 间 的距 离 得 LEN=(0,1,3,2,3,4) 1 图 论 基 础 -独 立 回 路 选 择 双 通 路 法 1 3425 624 5682)求 生 成 树 的 邻 接 节 点 数 组 INC和 关 联 分 支 数 组 NUM： INC=（ 0， 1， 4， 2， 4， 5） NUM=（ 0， 2， -5， 4， 6， 8）双 通 路 法 例 1 图 论 基 础 -独 立 回

62、 路 选 择 双 通 路 法双 通 路 法 例3)形 成 独 立 回 路 。 余 树 弦 1： j1=1， j2=3， LEN(1)=0，LEN(3)=3， 故 采 用 后 通 路 法 P 1(1)=-NUM(3)=5， j2=INC(3)=4; P1(2)=-NUM(4)=-4， j2=INC(4)=2; P1(2)=-NUM(2)=-2， j2=INC(2)=1; 则 前 后 通 路 在 1点 汇 合 ， 且 P1=（ 5， -4， -2） ， P1=0， 故 回 路 为 ： C1=（ 1， 5， -4， -2）LEN=(0,1,3,2,3,4) 1 3425 624 568 1 1 图

63、论 基 础 -独 立 回 路 选 择 双 通 路 法双 通 路 法 例 1 3425 624 568 173 9 4) 独 立 回 路 的 选 择 ： 余 树 弦 1： C1=（ 1， 5， -4， -2） 余 树 弦 3： C2=（ 3， -6， -4） 余 树 弦 7： C3=（ 7， -8， -6， -5） 余 树 弦 9： C4=（ 9， 2， 4， 6， 8） 1 图 论 基 础 -作 业1.图 论 中 图 描 述 的 本 质 内 容 是 什 么 ?它 有 几 种 表 示 方 法 ?2.试 述 图 中 邻 接 、 关 联 、 阶 、 度 的 含 义 。3.图 G的 子 图 、 真 子

64、 图 、 生 成 子 图 有 何 区 别 ？4.道 路 、 简 单 道 路 、 基 本 道 路 有 何 异 同 ？5.回 路 和 网 孔 有 何 异 同 ？作 业 1 图 论 基 础 -作 业6.何 谓 图 的 生 成 树 ？ 树 枝 与 图 的 顶 点 数 、 余 树 弦 数 、 独 立 回 路 数 有 何 关 系 ？7.试 述 连 通 图 的 割 点 、 割 边 、 割 集 的 异 同 点 。8.有 向 图 的 邻 接 矩 阵 、 道 路 矩 阵 如 何 构 造 ？ 它 们 分 别 给 出 了 图 的 那 些 信 息 ？9.假 定 图 1-8为 无 向 图 ， 试 写 出 其 邻 接 矩

65、阵 ， 并 指 出 有 向 图 与 无 向 图 邻 接 矩阵 有 何 区 别 。10.图 的 基 本 关 联 矩 阵 给 出 了 图 的 那 些 信 息 ？ 它 与 图 的 生 成 树 有 何 关 系 ？11.试 根 据 关 联 矩 阵 B画 图 。 011010 101001 000111 B 1 图 论 基 础 -作 业12.基 本 回 路 矩 阵 给 出 了 图 的 那 些 信 息 ？ 一 个 连 通 图 的 互 异 回 路 与 基 本 回路 各 有 多 少 ？13.基 本 割 集 矩 阵 给 出 了 图 的 那 些 信 息 ？ 它 与 图 的 生 成 树 有 何 关 系 ？14.将 B

66、、 C、 S矩 阵 均 按 余 树 弦 在 前 、 树 枝 在 后 的 相 同 顺 序 排 列 ， 并 分 成余 树 弦 子 阵 和 树 枝 子 阵 的 目 的 何 在 ？15.试 根 据 图 1-13选 一 棵 生 成 树 （ a,c,e)， 构 造 其 关 系 矩 阵 B， 并 由 B通 过运 算 求 得 矩 阵 C、 S。16.试 述 破 圈 法 、 加 边 法 、 收 缩 法 求 最 小 生 成 树 的 思 路 与 步 骤 ， 并 比 较 其优 缺 点 和 使 用 条 件 。17.试 用 加 边 法 、 破 圈 法 、 收 缩 法 找 出 通 风 网 络 图 1-19的 最 小 风 阻 树 、 余 树 弦 和 独 立 回 路 。 已 知 图 1-19的 分 支 风 阻 升 序 排 列 为 1， 13， 4， 12， 8，5， 6， 9， 3， 11， 2， 7， 10。 1 图 论 基 础 -作 业18.试 举 例 说 明 用 试 探 回 朔 法 和 双 通 路 法 由 最 小 风 阻 树 选 择 独 立 回 路的 步 骤 。 并 比 较 其 优 缺 点 。19.独 立 回 路