《1－1 图论的初步知识 网络分析与综合 教学课件》由会员分享，可在线阅读，更多相关《1－1 图论的初步知识 网络分析与综合 教学课件（12页珍藏版）》请在金锄头文库上搜索。
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 有向图(directed graph)：给图中的每一条支路都规定了方向的图。否则，称为无向图( undirected graph)如果用n表示节点数，b表示支路数，则图中n=3，b=4。 图论的一些基本概念1.3 连通图(connected graph)：图G中
3、任意两节点之间至少存在一条通路的图。否则称为不连通图(unconnected graph)。 连通图不连通图图论的一些基本概念图G 子图G1图论的一些基本概念1.4 子图(subgraph)：图G中的一部分称为其子图。子图G21.5 路径(path)：从图G的某一节点出发，沿着一些支路连续移动 ，从而到达另一指定的节点或原节点，则这样一系列的支路便构成了图G的一条路径。图论的一些基本概念1.6 回路(loop)：起点和终点重合的路径便构成了一个回路。图G 图论的一些基本概念1.7 树(tree-T) ：树是连通图G的一个连通子图；包含图G的所有的节点；不包含任何回路。T2 T1 树支：组成树的支路 。连支：其余的支路。树支数 ：连支数 ：割集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,41.10 基本割集 (cutset) ：由一条树支和若干条连支组成的割集。图论的一些基本概念独立回路 独立割集 基本回路 基本割集
