图论的初步知识PPT学习教案

1、会计学1图论的初步知识图论的初步知识图论属于数学的一个分支，它是一个年轻但却迅速成图论属于数学的一个分支，它是一个年轻但却迅速成熟的学科，它主要是研究事物之间的客观规律。熟的学科，它主要是研究事物之间的客观规律。哥尼斯堡桥问题哥尼斯堡桥问题X第1页/共13页从任一陆地出发走遍七座桥（而且只走一次）再回到从任一陆地出发走遍七座桥（而且只走一次）再回到 原地是否可行？原地是否可行？17361736年年EulerEuler（欧拉：圣彼得堡大学的数学教授）证明（欧拉：圣彼得堡大学的数学教授）证明 无解。无解。ACBDabcdegf古普鲁士古普鲁士哥尼斯堡哥尼斯堡城的城的PregelPregel有七座桥

2、将四块陆地相有七座桥将四块陆地相 连。连。连通图每点连接的边数为偶数才能有解。连通图每点连接的边数为偶数才能有解。演示演示返回返回X第2页/共13页1.1.图图 2.2.有向图有向图 3.3.连通图连通图9.9.割集割集 8.8.网孔网孔4.4.平面图平面图 5.5.子图子图 6.6.树树7.7.基本回路基本回路X第3页/共13页应用图论讨论电路的结构及其联接性质，对电路进行应用图论讨论电路的结构及其联接性质，对电路进行分析，称为分析，称为网络图论（网络拓扑学）。网络图论（网络拓扑学）。2.1 拓扑拓扑(topology)：几何或联接性质几何或联接性质。2.2 图图(Graph):电路（网络）

3、的图由支路（线段）和节电路（网络）的图由支路（线段）和节点（点）组成，用点（点）组成，用G表示。每一支路代表一个电路元件表示。每一支路代表一个电路元件或一些电路元件的某种组合，每一支路都连接在图中或一些电路元件的某种组合，每一支路都连接在图中的两个节点之间。的两个节点之间。 i u 标准支标准支路组合路组合X第4页/共13页 1234 电路图电路图 拓扑图拓扑图G 1234 在电路分析中，图中边上的箭头即表示该边所代表在电路分析中，图中边上的箭头即表示该边所代表的支路电压、电流方向。的支路电压、电流方向。 2.3 有向图有向图(directed graph)：给图中的每一条支给图中的每一条支

4、路都路都规定了方向的图。否则，称为规定了方向的图。否则，称为无向图无向图( undirected graph)令令b表示表示边数，边数，n表示节点数，则图中表示节点数，则图中b4， n3 3 。X第5页/共13页2.5 连通图连通图(connected graph)：图图G中任意两节点之间中任意两节点之间至 少 存 在 一 条 路 径 的 图 。 否 则 称 为至 少 存 在 一 条 路 径 的 图 。 否 则 称 为 不 连 通 图不 连 通 图(unconnected graph)。 连通图连通图不连通图不连通图2.4 路径路径(path)：从图从图G的某一节点出发，沿着一些支的某一节点出

5、发，沿着一些支路连续移动，从而到达另一指定的节点或原节点，则路连续移动，从而到达另一指定的节点或原节点，则这样一系列的支路便构成了图这样一系列的支路便构成了图G的一条路径。的一条路径。X第6页/共13页2.6 平面图平面图( (planar graph) )：一个图一个图G画在平面上时，画在平面上时，其各条支路除所联接的节点外不再交叉的图。否则称其各条支路除所联接的节点外不再交叉的图。否则称为非平面图。为非平面图。平面图平面图非平面图非平面图X第7页/共13页 12345 图图G 1245子图子图1G2.7 子图子图( (subgraph) )：图图G中的一部分称为其子图。中的一部分称为其子图

6、。子图有很多。子图有很多。子子图图2G 1345X第8页/共13页 123 1451 nnt树支数1 nbnblt数连支2.8 树树(tree-T) ：树是连通图树是连通图G的一个的一个连通连通子图；包含子图；包含图图G的所有的节点；不包含任何回路。的所有的节点；不包含任何回路。T2 T1 树支：树支：组成树的支路。组成树的支路。连支：连支：其余的支路。其余的支路。 12345 图图G X第9页/共13页树支电压，连支电流树支电压，连支电流 123456 2 5 6 ， 5 6 3 ， 5 2 4 ， 2.9 基本回路：基本回路：只含有一条连支的回路。只含有一条连支的回路。 123456 6

7、5 2 ，树支集合树支集合 4 3 1 ， 连支集合连支集合以连支的方向为基本回路的绕行方向。以连支的方向为基本回路的绕行方向。注注意意X第10页/共13页2.10 网孔网孔(mesh)：内部不包含支路的回路叫网孔。内部不包含支路的回路叫网孔。2. 图论的一些基本概念图论的一些基本概念图中网孔为：图中网孔为：1,2,3 2,4,5 3,5,6 2 5 6 ， 5 6 3 ， 5 2 4 ，基本回路为：基本回路为： 123456 123456X第11页/共13页 4 5 3 ，割集割集2.11 割集割集 (cutset) ：图图G的割集是的割集是G的一些支路集合，的一些支路集合，把这些支路移去将使把这些支路移去将使G分离为两个部分，而如果少移分离为两个部分，而