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

1、电电 网网 络络 理理 论论主讲人：李畸勇广西大学电气工程学院考核方式考核方式1.1.平时（平时（40%40%）+ +期末笔试（期末笔试（60%60%）2.2.平时（平时（40%40%）+ +期末小论文（期末小论文（60%60%）考核方式二选一考核方式二选一图论基础图论基础 自然界和人类社会中的大量事物自然界和人类社会中的大量事物及事物之间的关系，常可以用图形来及事物之间的关系，常可以用图形来描述。例如：物质结构，电气网络，描述。例如：物质结构，电气网络，城市规划，交通运输，信息传递，工城市规划，交通运输，信息传递，工作调配，事物关系等等都可以用点和作调配，事物关系等等都可以用点和线连起来的图

2、模拟。线连起来的图模拟。 对于大型复杂网络，传统的分对于大型复杂网络，传统的分析方法已不能适应，取而代之的是以析方法已不能适应，取而代之的是以网络图论为基础的现代网络分析方法，网络图论为基础的现代网络分析方法，它是现代网络理论的一个重要方面。它是现代网络理论的一个重要方面。图论是数学领域中拓扑学的一个分支，图论是数学领域中拓扑学的一个分支，图论通过点和线组成的图形，构成模图论通过点和线组成的图形，构成模拟物理系统的数学模型，并根据图的拟物理系统的数学模型，并根据图的性质进行分析，提供研究各种系统的性质进行分析，提供研究各种系统的分析方法。分析方法。 在电网络分析中，网络图论提供了在电网络分析中

3、，网络图论提供了选取网络独立完备变量的理论依据，并选取网络独立完备变量的理论依据，并通过引入网络矩阵方程使列写网络方程通过引入网络矩阵方程使列写网络方程系统化。网络方程用矩阵形式表示，不系统化。网络方程用矩阵形式表示，不仅清晰直观，而且易于用计算机建立和仅清晰直观，而且易于用计算机建立和求解方程。在计算机辅助网络分析和综求解方程。在计算机辅助网络分析和综合、以及电力网络分析等方面都将用到合、以及电力网络分析等方面都将用到网络图论的理论。网络图论的理论。 图论发展史图论发展史 图论是组合数学的一个分支，也图论是组合数学的一个分支，也是近几十年来最活跃的数学分支之一是近几十年来最活跃的数学分支之一

4、. .到目前为止，它已有二百六十多年的到目前为止，它已有二百六十多年的发展历史发展历史。 图论是拓扑学的一个分支，拓扑图论是拓扑学的一个分支，拓扑学（学（Topology）最初由德国数学家）最初由德国数学家Listing提出。提出。K Knigsbergnigsberg七桥的故事七桥的故事 K Knigsbergnigsberg七桥位于前苏联的七桥位于前苏联的加里宁格勒，历史上曾是德国东普鲁加里宁格勒，历史上曾是德国东普鲁士省的省会，霹雷格尔横穿城堡，河士省的省会，霹雷格尔横穿城堡，河中有两个小岛中有两个小岛B B与与C C，并有七座桥连接，并有七座桥连接岛与河岸及岛与岛（见图）。是否存岛与河

5、岸及岛与岛（见图）。是否存在一种走发，从四块陆地中的任意一在一种走发，从四块陆地中的任意一块开始，通过每一座桥恰好一次再回块开始，通过每一座桥恰好一次再回到起点。到起点。能否从某个地点出发经过每个桥一能否从某个地点出发经过每个桥一次且仅一次然后返回出发点？次且仅一次然后返回出发点？ABCD这就是著名的这就是著名的K Knigsbergnigsberg七桥问题，七桥问题，即一笔画问题；也是图论的起源。即一笔画问题；也是图论的起源。欧拉判定规则欧拉判定规则 （a）连接奇数个桥的陆地只有一个或）连接奇数个桥的陆地只有一个或超过两个以上时，不能实现一笔画。超过两个以上时，不能实现一笔画。 （b）连接奇

6、数个桥的陆地仅有两个时，）连接奇数个桥的陆地仅有两个时，则从两者中任一陆地出发，可以实现一则从两者中任一陆地出发，可以实现一笔画而停在另一陆地。笔画而停在另一陆地。 （c）每块陆地都连接偶数个桥时，则）每块陆地都连接偶数个桥时，则从任一陆地出发，都可以实现一笔画而从任一陆地出发，都可以实现一笔画而回到出发点。回到出发点。环球旅行与环球旅行与Hamilton问题问题 1859年年 Hamilton 提出这样一个提出这样一个问题：一个正十二面体有问题：一个正十二面体有20个顶点，个顶点，它们代表世界上它们代表世界上20个重要城市。正十个重要城市。正十二面体的每个面均为五边形，若两个二面体的每个面均

7、为五边形，若两个顶点之间有边相连，则表示相应的城顶点之间有边相连，则表示相应的城市之间有航线相通。市之间有航线相通。 Hamilton 提出提出 “能否从某城市出发经过每个城市一能否从某城市出发经过每个城市一次且仅一次然后返回出发点？次且仅一次然后返回出发点？” 正十二面体的顶点与棱的关系可以正十二面体的顶点与棱的关系可以用平面上的图表示，把正十二面体的顶用平面上的图表示，把正十二面体的顶点与棱分别对应图的顶点与边，就得到点与棱分别对应图的顶点与边，就得到正十二面体图。正十二面体图。 七桥问题与环球旅行的区别？七桥问题与环球旅行的区别？ 前者要求找一条路，必须经过图前者要求找一条路，必须经过图

8、中每条边且只能经过一次，而定点次中每条边且只能经过一次，而定点次数不限制；后者要求找一条回路经过数不限制；后者要求找一条回路经过图中的每个顶点，且只经过一次，而图中的每个顶点，且只经过一次，而经过边的次数不受限制。经过边的次数不受限制。四色四色问题问题 18401840年数学家茂比乌斯（年数学家茂比乌斯（M Mbiusbius）提出一个猜）提出一个猜想：想：任何平面地图，总可以把它的一个国家用任何平面地图，总可以把它的一个国家用四种颜色的一种着染，使相邻国家着不同色四种颜色的一种着染，使相邻国家着不同色。这就是著名的这就是著名的四色猜想四色猜想。如：。如：中国邮路问题中国邮路问题 196219

9、62年中国数学家管梅谷提出：年中国数学家管梅谷提出：一个邮递员从邮局出发递送邮件，要一个邮递员从邮局出发递送邮件，要求对他所负责的辖区的每条街至少走求对他所负责的辖区的每条街至少走一次，问如何选取路程最短一次，问如何选取路程最短 的路线？的路线？这个问题称为中国邮路问题。这个问题称为中国邮路问题。 该问题可用专门的算法来求解。该问题可用专门的算法来求解。（最优化问题）（最优化问题）平面图与非平面图问题平面图与非平面图问题 相传国王有相传国王有5个儿子，他在遗嘱中个儿子，他在遗嘱中写着把国土分成写着把国土分成5块给儿子，规定各块块给儿子，规定各块之间都要有交界线，但之间都要有交界线，但5个儿子提

10、出在个儿子提出在自己分到的领土上都要修一个王宫，并自己分到的领土上都要修一个王宫，并且各个王宫之间都要有路直接相通而不且各个王宫之间都要有路直接相通而不能交叉，这问题能否解决？能交叉，这问题能否解决？ 涉及到平面图及非平面图的概念。涉及到平面图及非平面图的概念。 要求每对顶点之间要求每对顶点之间都有一条边连接，都有一条边连接，而且边与边在不是而且边与边在不是顶点的地方不能相顶点的地方不能相交，称交，称5个顶点的个顶点的完备图，完备图，K5表示。表示。 图论的应用范围很广，它不但能应图论的应用范围很广，它不但能应用于自然科学，也能应用于社会科学。用于自然科学，也能应用于社会科学。它非但广泛应用于

11、电信网络、电力网络、它非但广泛应用于电信网络、电力网络、运输能力开关理论、编码理论、控制论、运输能力开关理论、编码理论、控制论、反馈理论、随机过程、可靠性理论、化反馈理论、随机过程、可靠性理论、化学化合物的辨认、计算机的程序设计、学化合物的辨认、计算机的程序设计、故障诊断、人工智能、印刷电路板的设故障诊断、人工智能、印刷电路板的设计、图案识别、地图着色、情报检索，计、图案识别、地图着色、情报检索，也应用于语言学、社会结构、经济学、也应用于语言学、社会结构、经济学、运筹学、遗传学等。运筹学、遗传学等。 只考虑电网络中各元件之间的连接关系时，只考虑电网络中各元件之间的连接关系时，可将网络中的每一个

12、元件用一条线段表示，称可将网络中的每一个元件用一条线段表示，称为为边边，元件的端点用，元件的端点用顶点顶点表示，这样便构成了表示，这样便构成了电网络图，以下简称电网络图，以下简称网络图网络图或或图图。图的组成元。图的组成元素称为素称为图元图元，边和顶点是最基本的图元。，边和顶点是最基本的图元。 一个实际系统抽象为图后，物理对象以边一个实际系统抽象为图后，物理对象以边的形式出现，因此边是实体图元；顶点的作用的形式出现，因此边是实体图元；顶点的作用是将边连接成图，所以顶点是连接图元。是将边连接成图，所以顶点是连接图元。 每一条线段称作图的边（每一条线段称作图的边（Edge），每一），每一个节点称作

13、图的顶点（个节点称作图的顶点（Vertex）。）。 图的基本概念图的基本概念一图的定义一图的定义 定义定义1 一个图一个图 G 定义为一个有序对定义为一个有序对(V, E)，记为，记为G = (V, E)，其中，其中 （1）V是一个非空集合，称为顶点集或点是一个非空集合，称为顶点集或点集，其元素称为顶点或点；集，其元素称为顶点或点； （2）E是由是由V中的点组成的无序点对构成的中的点组成的无序点对构成的集合，称为边集，其元素称为边，且同一点集合，称为边集，其元素称为边，且同一点对在对在 E 中可出现多次。中可出现多次。符号说明符号说明: 图图G 的顶点集也记为的顶点集也记为V(G), 边集也记

14、边集也记为为E(G)。图。图G 的顶点数（或阶数）和边数可分的顶点数（或阶数）和边数可分别用符号别用符号 n(G) (或或 |V(G)| ) 和和 m(G)表示。表示。例例1 设设 V =v1, v2, v3, v4，E =v1v2 , v1v2, v2v3 ，则则 G = (V, E) 是一个是一个4阶图。阶图。 若用小圆点代表点，若用小圆点代表点，连线代表边，则可将一连线代表边，则可将一个图用个图用“图形图形”来表示来表示, 如如例例1 中的图可表为中的图可表为v1v2v3v4注注: 也可记边也可记边 uv 为为e ，即，即 e = uv。v1v2v3v4e1e2e3e4e5 例例2 设设

15、V = v1,v2,v3,v4，E = e1,e2,e3,e4,e5，其中，其中 e1= v1v2， e2 = v2v3， e3 = v2v3， e4 = v3v4， e5 = v4v4 则则 G = (V, E) 是一个图。是一个图。相关概念相关概念: （1） 若边若边e = uv , 此时称此时称 u 和和v 是是 e 的端点的端点; 并称并称 u 和和 v 相邻，相邻，u (或或v)与与 e 相关联。若两条相关联。若两条边有一个共同的端点，则称这两条边相邻。边有一个共同的端点，则称这两条边相邻。（2）特殊点、边）特殊点、边 孤立点：不与任何边相关联的点；孤立点：不与任何边相关联的点； 环

16、：两端点重合的边；环：两端点重合的边； 重边：连接两个相同顶点的边的条数，叫重边：连接两个相同顶点的边的条数，叫做边的重数。重数大于做边的重数。重数大于1的边称为重边。的边称为重边。(4) 既没有环也没有重边的图称为既没有环也没有重边的图称为简单图简单图。其他所有的图都称为其他所有的图都称为复合图。复合图。简单图简单图非非简单简单图图例例3 3 平凡图平凡图 (3) 点集与边集均为有限集合的图称为点集与边集均为有限集合的图称为有限有限图图，本书只讨论有限图。只有一个顶点而无边，本书只讨论有限图。只有一个顶点而无边的图称为的图称为平凡图平凡图。边集为空的图称为。边集为空的图称为空图空图。边构成的

17、连续通路叫路径（边构成的连续通路叫路径（path）。仅有一条边的路径叫自环（仅有一条边的路径叫自环（self loop）。若两条边的两个顶点分别相同，那么这两若两条边的两个顶点分别相同，那么这两条边称为并联边条边称为并联边。没有并联边和自环的图叫简单图没有并联边和自环的图叫简单图。边与其两端之顶点相互关联。一个边关联边与其两端之顶点相互关联。一个边关联的两个顶点相互邻接，具有共同顶点的边的两个顶点相互邻接，具有共同顶点的边也相互邻接，前者是顶点邻接，后者是边也相互邻接，前者是顶点邻接，后者是边邻接邻接。 定义定义2 2 关联集合：顶点关联的全部边构成顶关联集合：顶点关联的全部边构成顶点的关联集

18、合。点的关联集合。 定义定义3 连通图和非连通图：任意两个顶点连通图和非连通图：任意两个顶点间都存在路径的图间都存在路径的图G为连通图，否则为非为连通图，否则为非连通图。连通图。电网络存在图不连通而物理连通的情况电网络存在图不连通而物理连通的情况 定义定义4 子图和补图：设子图和补图：设G 和和H为两个图，若为两个图，若V(H) V(G) , E(H) E(G) ,且且H中边的重数中边的重数不超过不超过G中对应边的重数，则称中对应边的重数，则称H 是是G 的的子子图图. 记为记为H G 。有时又称。有时又称G是是H的母图。的母图。 当当H G ，但，但H G时，则记为时，则记为H G ，且称且

19、称H为为G的的真子图真子图。G的的生成子图生成子图是指满是指满足足V(H) = V(G)的子图的子图H。 上图中，上图中，H1与与H2均为均为G 的子图，其中的子图，其中H2 是是G 的生成子图，而的生成子图，而H1 则不是。则不是。v1v2v3v4v5v1v3v4v2G H1 v1v3v4v2v5 H2导出子图导出子图 设设V是是V的一个非空子集。以的一个非空子集。以V为顶为顶点集，以两端点均在点集，以两端点均在V中的边的全体为边集所中的边的全体为边集所组成的子图，称为组成的子图，称为G的由的由V导出的子图，记为导出的子图，记为GV；简称为；简称为G的导出子图，的导出子图， 导出子图导出子图

20、GVV记为记为 G -V ；它是；它是G中删除中删除V中的顶点以及与这些顶点相关联的边所得中的顶点以及与这些顶点相关联的边所得到的子图。若到的子图。若 V=v, 则把则把G-v简记为简记为Gv。边导出子图边导出子图 假设假设E是是E的非空子集。以的非空子集。以E为为边集，以边集，以E中边的端点全体为顶点集所组成中边的端点全体为顶点集所组成的子图称为的子图称为G的由的由E导出的子图，记为导出的子图，记为GE ；简称为；简称为G的边导出子图，边集为的边导出子图，边集为 E E 的的G 的导出子图简记为的导出子图简记为 G-E 。若。若E =e ，则用，则用Ge来代替来代替 G-e。相对补图相对补图

21、/complementary graph ：（，：（，）是图，）是图，（，）是的子图，）是的子图，”，” VV或是或是”中边中边所关联的所有顶点集合，则所关联的所有顶点集合，则”（”，”）称为）称为关于的相对补图。关于的相对补图。补图：补图： 关于完全图的子图的补图称为此子图的关于完全图的子图的补图称为此子图的绝对补图，若子图记为，则补图记为绝对补图，若子图记为，则补图记为 。边不重的。是与G则称G,E若E是不相交的;与G则称G,V)是两个图，若VE,(V)和GE,(V设G21212121222111CG 定义定义5 顶点的度：一个顶点关联边的数量是顶点的度：一个顶点关联边的数量是该顶点的度。

22、该顶点的度。 所有顶点之间都有边连接的图叫完备图，所有顶点之间都有边连接的图叫完备图，v个个顶点的完备图，每个顶点的度都等于顶点的完备图，每个顶点的度都等于v-1。 定义定义6 割点、可分图和不可分图：如果移割点、可分图和不可分图：如果移去某个顶点后去某个顶点后G不再连通，那么这个顶点叫不再连通，那么这个顶点叫连通图连通图G的割点。存在割点的连通图是可分的割点。存在割点的连通图是可分图，不存在割点的连通图是不可分图。图，不存在割点的连通图是不可分图。割集割集在连通图在连通图G中，满足下列条件的边的最小集合中，满足下列条件的边的最小集合称为图称为图G的割集：若移去该边集中所有的边，的割集：若移去

23、该边集中所有的边，将使图分离为两个且仅有两个彼此分离而又各将使图分离为两个且仅有两个彼此分离而又各自连通的子图；若保留该边集中的任一条边不自连通的子图；若保留该边集中的任一条边不被移去，图被移去，图G仍然是连通的。仍然是连通的。 割集可以这样来确定：如图所示，在图割集可以这样来确定：如图所示，在图上画一条不经过顶点且不与同一边重复上画一条不经过顶点且不与同一边重复相交的封闭曲线，如图中虚线所示，则相交的封闭曲线，如图中虚线所示，则与此曲线相交的边组成一割集。与此曲线相交的边组成一割集。 图中边图中边1、2、5、6组成一割集，可用组成一割集，可用C(1，2，5，6)表示。移去该割集后，边表示。移

24、去该割集后，边3、4为两个分为两个分离的连通子图。有向连通图的割集可以定义离的连通子图。有向连通图的割集可以定义方向，其方向为由一个子图指向另一个子图。方向，其方向为由一个子图指向另一个子图。若取割集若取割集C(2，3，5)，则分离的一个子图中，则分离的一个子图中仅有一顶点。在图论中允许有孤立的顶点存仅有一顶点。在图论中允许有孤立的顶点存在，但不能存在没有顶点的边。在，但不能存在没有顶点的边。 定义定义7 有向图和无向图：赋予了方向的边有向图和无向图：赋予了方向的边叫有向边，有向边构成有向图，不存在有叫有向边，有向边构成有向图，不存在有向边的图是无向图。向边的图是无向图。 定义定义8 回路：当

25、一条通路的始端顶点与终回路：当一条通路的始端顶点与终端顶点重合，即通路闭合，则这种闭合通路端顶点重合，即通路闭合，则这种闭合通路称为回路。任何回路的顶点数等于边数，当称为回路。任何回路的顶点数等于边数，当回路的顶点数和边数都为回路的顶点数和边数都为1时称为自回路或时称为自回路或自环。自环。 在图在图2.2中，边中，边1、2、3构成回路，回路可构成回路，回路可表示为表示为L (1，2，3)。边。边1、2、5、6构成另构成另一回路，还可找出多个其他的回路。回路一回路，还可找出多个其他的回路。回路中结点数与边数相同。中结点数与边数相同。 定义定义9 树和补树：没有回路且包含全部顶树和补树：没有回路且

26、包含全部顶点的连通子图叫连通图点的连通子图叫连通图G的树的树T；树；树T的补的补图叫补树。图叫补树。(1)包含全部节点；包含全部节点；(2)不包含回路；不包含回路；(3)连通连通 1 12 23 34 45 56 6单连支回路单连支回路树树补树补树树支树支 1 1，2 2，3 3连支连支 4 4，5 5，6 6定义定义10 同构（或同形）同构（或同形）设有两个图设有两个图G1 = (V1, E1)和和G2 = (V2, E2)，若，若在其顶点集合之间存在双射，即存在一一在其顶点集合之间存在双射，即存在一一对应的关系，使得边之间有如下的关系：对应的关系，使得边之间有如下的关系：设设12uu12v

27、v111,u vV222,u vV，对应为：，对应为：1 11u vE2 22u vE1 1u v2 2u v当且仅当当且仅当， ；且；且的重数与的重数与的重数相同，则称两图同构，记为的重数相同，则称两图同构，记为G1 G2。例如例如 说明：说明：(1) 两个同构的图均有相同的结构，没有两个同构的图均有相同的结构，没有本质上的差异本质上的差异, 差异只是顶点和边的名称不同。差异只是顶点和边的名称不同。（2）图同构的几个必要条件：图同构的几个必要条件： 顶点数相同；顶点数相同； 边数相同；边数相同； 度数度数相等的顶点个数相同。相等的顶点个数相同。定义定义 设设 v为为 G 的顶点，的顶点，G

28、中与中与 v 为端点的边为端点的边的条数（环计算两次）称为点的条数（环计算两次）称为点 v 的度数，简的度数，简称为点称为点v的的度度，记为，记为 dG (v)，简记为，简记为 d(v)。图中图中 d (v1) = 5 d (v2) = 4 d (v3) = 3 d (v4) = 0 d (v5) = 2v1v2v3v4v5例例 注：注：该图中各点的该图中各点的度数之和等于度数之和等于14，恰好是边数恰好是边数7的的两两倍倍(3) 易证，图的同构关系是一个等价关系。该易证，图的同构关系是一个等价关系。该关系将所有的图的集合，划分为一些等价类关系将所有的图的集合，划分为一些等价类，即相互同构的图作成同一个等价类。，即相互同构的图作成同一个等价类。图的运算图的运算设设G1，G2是是G 的子图的子图, 有下列术语与概念有下列术语与概念 G1和和G2不相交不相交: 指它们无公共顶点指它们无公共顶点.G1和和G2边不重边不重 : 指它们无公共边指它们无公共边.并图并图G1G2 ：是