§3-4网络图论基础 、拓扑图 拓朴图是由结点与线段组成的图形,简称为图。 R3 1、有向图(定向图):标有电流参考方向的图 称为有向图,否则为无向图。 闪四 西南交通大学
西南交通大学 §3-4 网络图论基础 R3 R2 R1 R4 + - R5 us i s 一、拓扑图 1、有向图（定向图）：标有电流参考方向的图 称为有向图，否则为无向图。 拓朴图是由结点与线段组成的图形，简称为图
2、子图:如果图G的每个结点和每条支路都是 图G的,则称图G是图G的子图。 ① 1②2 8① ⑧① ④↓ ④ ① 23\ ④ ④ 西南交通大学
西南交通大学 2 、子图：如果图G1的每个结点和每条支路都是 图G的，则称图G1是图G的子图。 (b) 1 2 4 ① ② ③ ④ 3 4 5 (c) ① ② ③ ④ 2 4 5 (f) ② ③ ④ 4 3 (e) ① ② ③ ④ 2 3 (d) ① ② ③ ④ (a) 5 1 2 3 4 ① ② ③ ④
3、路径:从图G的某个结点沿不同支路及结点到达 另一结点,那么所经过的支路序列称为路径。 4、连通图与非连通图:图G中的任意两个结点之间 至少存在一条路径时,则称图G为连通图,否则为非 连通图。 5、孤立结点:没有任何支路与之连接的结点。 在图论中,说移去一条支路,并不意味着把它所连 接的结点同时移去;但是说移去一个结点,则意味 着与该结点相连的支路也移去了 树 1、树:设图G是一个连通图,图T是图G的一个子 图,当图T同时满足下列三个条件时,则称图T是图 G的一棵树。 闪四 西南交通大学
西南交通大学 3、路径：从图G的某个结点沿不同支路及结点到达 另一结点，那么所经过的支路序列称为路径。 4 、连通图与非连通图：图G中的任意两个结点之间 至少存在一条路径时，则称图G为连通图，否则为非 连通图。 5 、孤立结点：没有任何支路与之连接的结点。 二、树 1、树：设图G是一个连通图，图T是图G的一个子 图，当图T同时满足下列三个条件时，则称图T是图 G的一棵树。 在图论中，说移去一条支路，并不意味着把它所连 接的结点同时移去；但是说移去一个结点，则意味 着与该结点相连的支路也移去了
(1)是一个连通的子图。 (2)包含图G的全部结点。 (3)不包含回路。 树:连接全部结点所需的最少支路的集合。 树支:组成树的支路称为树支。 3、连支:除去树支后所剩支路即为连支。 、回路与基本回路 1、回路:一个闭合的路径。 2、基本回路:仅由一条连支与多条树支构成的回 路。基本回路的方向与连支的方向一致。 闪四 西南交通大学
西南交通大学 （1） 是一个连通的子图。 （2） 包含图G的全部结点。 （3） 不包含回路。 树：连接全部结点所需的最少支路的集合。 2、树支：组成树的支路称为树支。 3、连支：除去树支后所剩支路即为连支。 三、回路与基本回路 1、回路：一个闭合的路径。 2、基本回路：仅由一条连支与多条树支构成的回 路。基本回路的方向与连支的方向一致
llll 闪四 西南交通大学
西南交通大学 1 2 3 4 6 5 7 8
闪四 西南交通大学
西南交通大学 1 2 3 4 6 5 7 8 1 2 3 4 6 5 7 8
、割集与基本割集 割集:是支路的集合,它必须满足两个条件: (1)移去该集合中的所有支路,则图被分为两部分。 (2)当少移去该集合中的任何一条支路,则图仍是连 通的。 注:移支路时,与其相连的结点并不移去。 {1,5,2}{1,5,3,6} 2 闪四 西南交通大学
西南交通大学 四、割集与基本割集 1、割集：是支路的集合，它必须满足两个条件： 注：移支路时，与其相连的结点并不移去。 1 2 4 3 6 5 1 2 4 3 6 5 1 2 4 3 6 5 （1）移去该集合中的所有支路，则图被分为两部分。 （2）当少移去该集合中的任何一条支路，则图仍是连 通的。 {1，5，2} {1，5，3，6}
0, 6}{1,5,4,6}{1,2,3,4,5} 不是图G的集合 2、作高斯面确定割集: 在图G上作一个高斯面(闭合面),使其包围 G的某些结点,而每条支路只能被闭合面切割一次 ,去掉与闭合面相切割的支路,图G将被分为两部 分,那么这组支路即为图G的一个割集。 闪四 西南交通大学
西南交通大学 1 2 4 3 6 5 1 2 4 3 6 5 1 2 4 3 6 5 {2，5，4，6} {1，5，4，6} {1，2，3，4，5} 不是图G的集合 2、作高斯面确定割集： 在图G上作一个高斯面（闭合面），使其包围 G的某些结点，而每条支路只能被闭合面切割一次 ，去掉与闭合面相切割的支路，图G将被分为两部 分，那么这组支路即为图G的一个割集
C 割集C1 C1,C2,C3为基本割集 3、基本割集: C为非基本割集 先选一棵树,如选支路1、5、3为树枝。 基本割集又称单树支割集,即割集中只含一条树 支,其余均为连支。 西南交通大学 带
西南交通大学 1 2 3 4 6 5 C1 C2 C3 割集C1、C2、C3 3、基本割集： 6 1 2 4 3 5 C4 C1 C2 C3 先选一棵树，如选支路1、5、3为树枝 。 基本割集又称单树支割集，即割集中只含一条树 支，其余均为连支。 C1，C2，C3为基本割集 C4为非基本割集
基本割集数:设有n个结点、b条支路 树支数=n-1 基本割集数=n-1 闪四 西南交通大学
西南交通大学 1 2 4 3 6 5 C3 C2 C1 1 2 4 3 6 5 C1 C2 C3 基本割集数： 设有n个结点、b条支路 树支数＝n-1 基本割集数＝ n-1