电力网络理论讲课图论基础.ppt

电网络理论;考核方式;图论根底;对于大型复杂网络，传统的分析方法已不能适应，取而代之的是以网络图论为根底的现代网络分析方法，它是现代网络理论的一个重要方面。图论是数学领域中拓扑学的一个分支，图论通过点和线组成的图形，构成模拟物理系统的数学模型，并根据图的性质进行分析，提供研究各种系统的分析方法。;在电网络分析中，网络图论提供了选取网络独立完备变量的理论依据，并通过引入网络矩阵方程使列写网络方程系统化。网络方程用矩阵形式表示，不仅清晰直观，而且易于用计算机建立和求解方程。在计算机辅助网络分析和综合、以及电力网络分析等方面都将用到网络图论的理论。;图论开展史;K?nigsberg七桥的故事;能否从某个地点出发经过每个桥一次且仅一次然后返回出发点？;欧拉判定规那么;环球旅行与Hamilton问题;正十二面体的顶点与棱的关系可以用平面上的图表示，把正十二面体的顶点与棱分别对应图的顶点与边，就得到正十二面体图。;七桥问题与环球旅行的区别？;四色问题;中国邮路问题;平面图与非平面图问题;要求每对顶点之间都有一条边连接，而且边与边在不是顶点的地方不能相交，称5个顶点的完备图，K5表示。;图论的应用范围很广，它不但能应用于自然科学，也能应用于社会科学。它非但广泛应用于电信网络、电力网络、运输能力开关理论、编码理论、控制论、反响理论、随机过程、可靠性理论、化学化合物的识别、计算机的程序设计、故障诊断、人工智能、印刷电路板的设计、图案识别、地图着色、情报检索，也应用于语言学、社会结构、经济学、运筹学、遗传学等。;只考虑电网络中各元件之间的连接关系时，可将网络中的每一个元件用一条线段表示，称为边，元件的端点用顶点表示，这样便构成了电网络图，以下简称网络图或图。图的组成元素称为图元，边和顶点是最根本的图元。;每一条线段称作图的边〔Edge〕，每一个节点称作图的顶点〔Vertex〕。;图的根本概念;符号说明:图G的顶点集也记为V(G),边集也记为E(G)。图G的顶点数〔或阶数〕和边数可分别用符号n(G)(或|V(G)|)和m(G)表示。;注:也可记边uv为e，即e=uv。;相关概念:

〔1〕假设边e=uv,此时称u和v是e的端点;并称u和v相邻，u(或v)与e相关联。假设两条边有一个共同的端点，那么称这两条边相邻。;(4)既没有环也没有重边的图称为简单图。其他所有的图都称为复合图。;边构成的连续通路叫路径〔path〕。;定义2关联集合：顶点关联的全部边构成顶点的关联集合。;定义3连通图和非连通图：任意两个顶点间都存在路径的图G为连通图，否那么为非连通图。;电网络存在图不连通而物理连通的情况;定义4子图和补图：设G和H为两个图，假设V(H)?V(G),E(H)?E(G),且H中边的重数不超过G中对应边的重数，那么称H是G的子图.记为H?G。有时又称G是H的母图。;上图中，H1与H2均为G的子图，其中H2是G的生成子图，而H1那么不是。;导出子图G[V\V’]记为G-V’；它是G中删除V’中的顶点以及与这些顶点相关联的边所得到的子图。假设V’={v},那么把G-{v}简记为G–v。;相对补图/complementarygraph：Ｇ＝〔Ｖ，Ｅ〕是图，Ｇ’＝〔Ｖ’，Ε’〕是Ｇ的子图，Ｅ”＝Ｅ－Ｅ’，Ｖ”＝V－V’或是Ｅ”中边所关联的所有顶点集合，那么Ｇ”＝〔Ｖ”，Ｅ”〕称为Ｇ’关于Ｇ的相对补图。

补图：关于完全图的子图的补图称为此子图的绝对补图，假设子图记为Ｇ，那么补图记为。;定义5顶点的度：一个顶点关联边的数量是该顶点的度。;定义6割点、可分图和不可分图：如果移去某个顶点后G不再连通，那么这个顶点叫连通图G的割点。存在割点的连通图是可分图，不存在割点的连通图是不可分图。;割集可以这样来确定：如下图，在图上画一条不经过顶点且不与同一边重复相交的封闭曲线，如图中虚线所示，那么与此曲线相交的边组成一割集。;图中边1、2、5、6组成一割集，可用C(1，2，5，6)表示。移去该割集后，边3、4为两个别离的连通子图。有向连通图的割集可以定义方向，其方向为由一个子图指向另一个子图。假设取割集C(2，3，5)，那么别离的一个子图中仅有一顶点。在图论中允许有孤立的顶点存在，但不能存在没有顶点的边。;定义7有向图和无向图：赋予了方向的边叫有向边，有向边构成有向图，不存在有向边的图是无向图