网络分析与综合 教学课件 作者 俎云霄 吕玉琴第一章1－1 图论的初步知识.ppt

《网络分析与综合 教学课件 作者 俎云霄 吕玉琴第一章1－1 图论的初步知识.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§1-1图论的初步知识北京邮电大学电子工程学院俎云霄图论属于数学的一个分支，它是一个年轻但却迅速成熟的学科，它主要是研究事物之间的客观规律。1.图2.有向图3.连通图4.子图9.基本回路10.基本割集5.路径6.回路7.树8.割集图论的起源——哥尼斯堡桥问题从任一陆地出发走遍七座桥（而且只走一次）再回到原地是否可行？1736年Euler（欧拉：圣彼得堡大学的数学教授）证明无解。古普鲁士有条Pregel河穿越哥尼斯堡城，河上有七座桥将四块陆地相连。连通图每点连接的边数为偶数才能有解。图论的一些基本概念应用图论讨论电路的结构及其联接性质，对电路进行分析，称为网络图论（网络拓扑

2、学）。拓扑(topology)：几何或联接性质。1.1图(Graph):电路（网络）的图由支路（线段）和节点(点)组成，用G表示。每一支路代表一个电路元件或一些电路元件的某种组合，每一支路都连接在图中的两个节点之间。标准支路组合电路图拓扑图G在电路分析中，图中边上的箭头即表示该边所代表的支路电压、电流方向。1.2有向图(directedgraph)：给图中的每一条支路都规定了方向的图。否则，称为无向图(undirectedgraph)如果用n表示节点数，b表示支路数，则图中n=3，b=4。图论的一些基本概念1.3连通图(connectedgraph)：图G中任意两节点之间

3、至少存在一条通路的图。否则称为不连通图(unconnectedgraph)。连通图不连通图图论的一些基本概念图G子图G1图论的一些基本概念1.4子图(subgraph)：图G中的一部分称为其子图。子图G21.5路径(path)：从图G的某一节点出发，沿着一些支路连续移动，从而到达另一指定的节点或原节点，则这样一系列的支路便构成了图G的一条路径。图论的一些基本概念1.6回路(loop)：起点和终点重合的路径便构成了一个回路。图G图论的一些基本概念1.7树(tree-T)：树是连通图G的一个连通子图；包含图G的所有的节点；不包含任何回路。T2T1树支：组成树的支路。连支：其余

4、的支路。树支数：连支数：割集C(1,3,5,4)1.8割集(cutset)：图G的割集是G的一些支路集合，把这些支路移去将使G分离为两个部分，而如果少移去其中一条支路，图仍将是两通的。即割集是使图分为两部分的最少边集。图论的一些基本概念1.9基本回路：由一条连支和若干条树支组成的回路。以连支的方向为基本回路的绕行方向。注意图论的一些基本概念l1(1,6,5,2)l2(3,6,5)l3(4,2,5)割集{1,3,5,4}1.10基本割集(cutset)：由一条树支和若干条连支组成的割集。图论的一些基本概念独立回路独立割集基本回路基本割集