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