图论的初步知识.pptx

内容提要内容提要图论的起源图论的起源图论的基本概念图论的基本概念X1.1.图论的起源图论的起源图论属于数学的一个分支，它是一个年轻但却迅速成图论属于数学的一个分支，它是一个年轻但却迅速成熟的学科，它主要是研究事物之间的客观规律。熟的学科，它主要是研究事物之间的客观规律。哥尼斯堡桥问题哥尼斯堡桥问题X从任一陆地出发走遍七座桥（而且只走一次）再回到从任一陆地出发走遍七座桥（而且只走一次）再回到 原地是否可行？原地是否可行？17361736年年EulerEuler（欧拉：圣彼得堡大学的数学教授）证明（欧拉：圣彼得堡大学的数学教授）证明 无解。无解。古普鲁士古普鲁士哥尼斯堡哥尼斯堡城的城的PregelPregel有七座桥将四块陆地相有七座桥将四块陆地相 连。连。连通图每点连接的边数为偶数才能有解。连通图每点连接的边数为偶数才能有解。演示演示返回返回1.1.图论的起源图论的起源X2.2.图论的一些基本概念图论的一些基本概念1.1.图图 2.2.有向图有向图 3.3.连通图连通图9.9.割集割集 8.8.网孔网孔4.4.平面图平面图 5.5.子图子图 6.6.树树7.7.基本回路基本回路X2.2.图论的一些基本概念图论的一些基本概念应用图论讨论电路的结构及其联接性质，对电路进行应用图论讨论电路的结构及其联接性质，对电路进行分析，称为分析，称为网络图论（网络拓扑学）。网络图论（网络拓扑学）。2.1 拓扑拓扑(topology)：几何或联接性质几何或联接性质。2.2 图图(Graph):电路（网络）的图由支路（线段）和节电路（网络）的图由支路（线段）和节点（点）组成，用点（点）组成，用G表示。每一支路代表一个电路元件表示。每一支路代表一个电路元件或一些电路元件的某种组合，每一支路都连接在图中的或一些电路元件的某种组合，每一支路都连接在图中的两个节点之间。两个节点之间。标准支标准支路组合路组合X电路图电路图 拓扑图拓扑图G 在在电电路路分分析析中中，图图中中边边上上的的箭箭头头即即表表示示该该边边所所代代表表的的支路电压、电流方向。支路电压、电流方向。2.2.图论的一些基本概念图论的一些基本概念2.3 有向图有向图(directed graph)：给图中的每一条支给图中的每一条支 路都路都规定了方向的图。否则，称为规定了方向的图。否则，称为无向图无向图(undirected graph)令令b表示表示边数，边数，n表示节点数，则图中表示节点数，则图中b4，n3 3。X2.5 连连通通图图(connected graph)：图图G中中任任意意两两节节点点之之间间至至 少少 存存 在在 一一 条条 路路 径径 的的 图图。否否 则则 称称 为为 不不 连连 通通 图图(unconnected graph)。连通图连通图不连通图不连通图2.2.图论的一些基本概念图论的一些基本概念2.4 路路径径(path)：从从图图G的的某某一一节节点点出出发发，沿沿着着一一些些支支路路连连续续移移动动，从从而而到到达达另另一一指指定定的的节节点点或或原原节节点点，则则这样一系列的支路便构成了图这样一系列的支路便构成了图G的一条路径。的一条路径。X2.6 平平面面图图(planar graph)：一一个个图图G画画在在平平面面上上时时，其其各各条条支支路路除除所所联联接接的的节节点点外外不不再再交交叉叉的的图图。否否则则称称为非平面图。为非平面图。平面图平面图非平面图非平面图2.2.图论的一些基本概念图论的一些基本概念X 图图G 子图子图2.2.图论的一些基本概念图论的一些基本概念2.7 子图子图(subgraph)：图图G中的一部分称为其子图。中的一部分称为其子图。子图有很多。子图有很多。子图子图X2.2.图论的一些基本概念图论的一些基本概念2.8 树树(tree-T)：树是连通图树是连通图G的一个的一个连通连通子图；包含子图；包含图图G的所有的节点；不包含任何回路。的所有的节点；不包含任何回路。T2 T1 树支：树支：组成树的支路。组成树的支路。连支：连支：其余的支路。其余的支路。图图G X树支电压，连支电流树支电压，连支电流 2.9 基本回路：基本回路：只含有一条连支的回路。只含有一条连支的回路。树支集合树支集合 连支集合连支集合以连支的方向为基本回路的绕行方向。以连支的方向为基本回路的绕行方向。注意注意2.2.图论的一些基本概念图论的一些基本概念X2.10 网孔网孔(mesh)：内部不包含支路的回路叫网孔。内部不包含支路的回路叫网孔。2.图论的一些基本概念图论的一些基本概念图中网孔为：图中网孔为：1,2,3 2,4,5 3,5,6基本回路为：基本回路为：X 割集割集2.11 割集割集(cutset)：图图G的割集是的割集是G的一些支路集合，的一些支路集合，把这些支路移去将使把这些支路移去将使G分离为两个部分，而如果少移去分离为两个部分，而如果少移去其中一条支路，图仍将是连通的。即割集是使图分为其中一条支路，图仍将是连通的。即割集是使图分为两部分的最少边集。两部分的最少边集。2.图论的一些基本概念图论的一些基本概念返回返回X