网络图论的基本概念

-回复 -浏览
楼主 2021-11-28 21:54:47
举报 只看此人 收藏本贴 楼主
漏电保护器

       对于一个电路图,如果用点表示其节点,用线段表示其支路,得到一个由点和线段组成的图,这个图被称为对应电路图的拓扑图,通常用符号G表示。例如:图1a)所示电路,其对应的拓扑图如图1 (b) 所示。

1

2

       拓扑图是线段和点组成的集合,它反映了对应的电路图中的支路数、节点数以及各支路与节点之间相互连接的信息。

3

       在拓扑图中,如果任意两点之间至少有一条连通的途径,那么这样的图称为连通图,例如图1b)所示的图,否则称为非连通图,例如图2b)所示的图。如果图G1中所有的线段与点均是图G中的全部或部分线段与点,且线段与点的连接关系与图G中的一致,那么图G1称为图G的子图。例如图b)(c)(d)(e)均是图3a)的子图。

       下面介绍网络图论中非常重要的一个概念——树。树是连通图G的一个特殊子图,必须同时满足以下三个条件:

1)子图本身是连通的;

2)包括连通图G所有节点;

3)不包含任意回路。

组成树的支路称为树支,不包含在树上的支路称为连支(或链支)。如果用表示树支的数目,则:(式1

连支的数目等于支路数b减去树支的数目,即:(式2    

       如果将一个电路铺在一个平面上,除节点之外再没有其他交点,这样的电路被称为平面电路,否则,称为非平面电路。

       在平面电路中,内部没有任何支路的回路称为网孔。它是一种特殊的回路。

       一个有b条支路、n个节点的连通平面图的网孔数m为:(式3

       接下来介绍割集的概念。割集是连通图G的一个子图,它满足以下两个条件:

       1)移去该子图的全部支路,连通图G将被分为两个独立部分;

       2)当少移去该子图中任一条支路时,则图仍然保持连通。    

       一个具有n个节点的连通图,有(n-1)条树,有(n-1)个单树支割集。

我要推荐
转发到