技术中心
 
 

网络图论的基本概念

   日期:2009-07-27     来源:互联网    
网络图论的基本概念

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

图2-1-1

图2-1-2

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

图2-1-3

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

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

(1)子图本身是连通的;

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

(3)不包含任意回路。

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

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

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

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

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

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

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

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

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

 
  
  
  
  
 
更多>同类技术
 
全年征稿 / 资讯合作
 
推荐图文
推荐技术
可能喜欢