电路分析基础（第4版）课件 §2-1 图论的初步知识.ppt

北京邮电大学电子工程学院退出开始§2-1图论的初步知识内容提要图论的起源图论的基本概念X1.图论的起源图论属于数学的一个分支，它是一个年轻但却迅速成熟的学科，它主要研究事物之间的客观规律。哥尼斯堡桥问题X图论在电路中的应用称为网络图论（网络拓扑学）。应用图论讨论电路的结构及其联接性质，对电路进行分析。拓扑(topology)：几何或联接性质。古普鲁士哥尼斯堡城的Pregel有七座桥将四块陆地相连。连通图每点连接的边数为偶数才能有解。演示返回1.图论的起源X从任一陆地出发走遍七座桥（而且只走一次）再回到原地是否可行？1736年Euler（欧拉：圣彼得堡大学的数学教授）证明无解。2.图论的一些基本概念1.图2.有向图3.连通图8.割集9.基本回路4.子图5.路径6.回路7.树X10.基本割集2.图论的一些基本概念2.1图(Graph):电路（网络）的图由支路（线段）和节点（点）组成，用G表示。每一支路代表一个电路元件或一些电路元件的某种组合，每一支路都连接在图中的两个节点之间。X电路图拓扑图G在电路分析中，图中支路的方向即代表了对应电网络中该支路电压和支路电流的方向。2.图论的一些基本概念2.2有向图(directedgraph)：给图中的每一条支路都规定了方向的图。否则，称为无向图(undirectedgraph)X2.3连通图(connectedgraph)：图G中任意两节点之间至少存在一条通路的图。否则称为不连通图(unconnectedgraph)。连通图非连通图2.图论的一些基本概念X图G子图2.图论的一些基本概念2.4子图(subgraph)：如果图G1的每个节点和支路都是图G中的节点和支路，则称图G1是图G的一个子图。子图有很多。子图X2.图论的一些基本概念X2.5路径(path)：从图G的某一节点出发，沿着一些支路连续移动，从而到达另一指定的节点，则这样一系列的支路便构成了图G的一条路径。回路L（1,3,6），或回路L（a,d,c,a）2.6回路(loop)：如果路径的起点和终点重合，则就构成了一条回路。2.图论的一些基本概念2.7树(tree-T)：树是连通图G的一个连通子图；包含图G的所有的节点；不包含任何回路。T2T1树支：组成树的支路。连支：其余的支路。图GX树支集合连支集合割集2.8割集(cutset)：图G的割集是G的一些支路集合，把这些支路移去将使G分离为两个部分，而如果少移去其中一条支路，图仍将是连通的。即割集是使图分为两部分的最少支路集。2.图论的一些基本概念X2.9基本回路：只含有一条连支的回路。（单连支回路）以连支的方向为基本回路的绕行方向。注意2.图论的一些基本概念XL1(1,2,4)，L2(2,3,5)，L3(1,3,6)L1(1,2,4)，L2(2,3,5)，L3(4,5,6)基本回路数等于连支数2.10基本割集：只含有一条树支的割集。（单树支割集）2.图论的一些基本概念返回XC1(1,4,6)，C2(1,2,3)，C3(3,5,6)C1(1,4,6)，C2(2,4,5)，C3(3,5,6)以树支的方向为基本割集的方向。注意基本割集数等于树支数