网络图论.pptx

电电 路路 原原 理理电 子 教 案（下册）第一章第一章 网络图论网络图论 本章主要介绍网络图论的基本知识本章主要介绍网络图论的基本知识本章重点：本章重点：有向图、树、树支、连支、基本割集、基本回路等概念。有向图、树、树支、连支、基本割集、基本回路等概念。关联矩阵、基本割集矩阵、基本回路矩阵。关联矩阵、基本割集矩阵、基本回路矩阵。1-1 网络的图网络的图 线形图线形图：将网络中的每一个元件将网络中的每一个元件(即支路即支路)用一条线段代替，称之为支用一条线段代替，称之为支路；将每一个元件的端点或若干个元件相联接的点路；将每一个元件的端点或若干个元件相联接的点(即节点即节点)用一个圆点表示，并称之为节点。如此得到的一个点、线用一个圆点表示，并称之为节点。如此得到的一个点、线的集合，称为网络的集合，称为网络N N 的图，或线形图，用符号的图，或线形图，用符号G G 代表。代表。网络的图只表明网络中各支路的联接情况，而不涉及网络的图只表明网络中各支路的联接情况，而不涉及元件的性质。元件的性质。有向图有向图：标明各支路参考方向的图称为有向图。标明各支路参考方向的图称为有向图。子图子图(subgraph)：如果图如果图Ga中的每一个节点和支路都是图中的每一个节点和支路都是图G中的节点和支中的节点和支路，即图路，即图Ga是图是图G的一部分，则的一部分，则Ga叫做叫做G的子图。的子图。补图（补图（complement subgraph）：）：如果图如果图G的子图的子图Ga和和Gb包含了包含了G的所有支路和节点，的所有支路和节点，而且而且Ga和和Gb又没有公共的支路，则又没有公共的支路，则Ga和和Gb互为补图。互为补图。路径路径(path)：由由m条不同的支路和条不同的支路和m+1个不同的节点依次联接成的一个不同的节点依次联接成的一条通路称为路径。条通路称为路径。回路回路(loop):如果路径的始端节点和终端节点重合，这样的路径称如果路径的始端节点和终端节点重合，这样的路径称为回路。为回路。连通图连通图(connected graph)和非和非连通图连通图(disconnected graph):在图在图G中，如果任意两个节点之间至少有一条路径存中，如果任意两个节点之间至少有一条路径存在，则此图称为连通图，否则就称为非连通图。在，则此图称为连通图，否则就称为非连通图。1-2 树和树余树和树余树支和连支树支和连支 树树(tree)：树是一个树是一个连通图的子图，该子图中包含了连通图连通图的子图，该子图中包含了连通图G G的全部节点，但不包含任何回路。的全部节点，但不包含任何回路。树余树余(cotree)：连通图中与树互补的子图叫做树余。连通图中与树互补的子图叫做树余。树支树支(tree branch)：连支连支(link)：树中的支路叫做树支。树中的支路叫做树支。树余中的支路叫做连支。树余中的支路叫做连支。基本回路基本回路(fundamental loop)：只包含一条连支的回路叫做基本回路。只包含一条连支的回路叫做基本回路。基本回路是唯一的。基本回路是唯一的。1-3 割割 集集 割集割集(cut set)：任一连通图任一连通图G中，符合下列两个条件的支路集叫做图中，符合下列两个条件的支路集叫做图G的割集。的割集。(1)该支路集中的所有支路被移去该支路集中的所有支路被移去(但所有节点予以但所有节点予以保留保留)后，原连通图留下的图形将是两个彼此分离而后，原连通图留下的图形将是两个彼此分离而又各自连通的子图；又各自连通的子图；(2)该支路集中，当保留任一支路，而将其余的所有该支路集中，当保留任一支路，而将其余的所有支路移去后，原连通图留下的图形仍然是连通的。支路移去后，原连通图留下的图形仍然是连通的。对于具有对于具有s个分离部分的非连通图，符合下列条件的个分离部分的非连通图，符合下列条件的支路集叫做割集支路集叫做割集。(1)该支路集中的所有支路被移去该支路集中的所有支路被移去(但所有节点予以保但所有节点予以保留留)后，原非连通图留下的图形将具有后，原非连通图留下的图形将具有s+1个分离部分；个分离部分；(2)该支路集中，当保留任一支路，而将其余的所有该支路集中，当保留任一支路，而将其余的所有支路移去后，原非连通图留下的图形仍然只具有支路移去后，原非连通图留下的图形仍然只具有s个个分离部分。分离部分。基本割集基本割集(fundamental cut set)：只包含一条树支的割集叫做基本割集只包含一条树支的割集叫做基本割集。由每一树支决定的由每一树支决定的基本割集是唯一基本割集是唯一的。的。1-4 图的基本回路数和基本割集数图的基本回路数和基本割集数 一个节点数为一个节点数为nt=n+1支路数为支路数为b的连通图的连通图G，无论如，无论如何选树，恒具有何选树，恒具有n个基本割集和个基本割集和b-n个基本回路。个基本回路。把把n+1个节点全部连通以构成一种树时，至少需要个节点全部连通以构成一种树时，至少需要n条支路。若支路数多于条支路。若支路数多于n，则必形成回路，而不成其，则必形成回路，而不成其为树。因为基本割集数等于树支数，为树。因为基本割集数等于树支数，所以，具有所以，具有nt=n+1+1个节点的图个节点的图G，恒具有，恒具有n个基本割集。个基本割集。连支数等于全部支路数连支数等于全部支路数b减去树支数减去树支数n，因基本回路的因基本回路的数目等于连支数，所以，具有数目等于连支数，所以，具有nt=n+1个节点、个节点、b条支条支路的图路的图G，恒具有，恒具有(b-n)个基本回路。个基本回路。对于具有对于具有nt个节点、个节点、b条支路、条支路、s个分离部分的非连通图，个分离部分的非连通图，在每一分离部分中选一树，则总树支数在每一分离部分中选一树，则总树支数(即基本割集数即基本割集数)为为nt-s，总连支数，总连支数(即基本回路数即基本回路数)为为b-(nt-s)=b-nt+s。平面图平面图(planar graph)：凡是能在一个平面上绘出，而又不致有两条支路在一凡是能在一个平面上绘出，而又不致有两条支路在一个非节点处交叉的图，称为平面图。个非节点处交叉的图，称为平面图。一个平面图的网孔数一个平面图的网孔数m等于图的基本回路数等于图的基本回路数l。为什么要研究图的基本割集数目和基本回路数目？为什么要研究图的基本割集数目和基本回路数目？1-5 关联矩阵关联矩阵 节点节点-支路关联矩阵支路关联矩阵(node-to-branch incidence matrix)若以节点若以节点为参考节点为参考节点 1-6 基本割集矩阵基本割集矩阵 基本割集矩阵基本割集矩阵(fundamental cutset matrix)F基本子阵（基本子阵（fundamental submatrix)1-7 基本回路矩阵基本回路矩阵 基本回路矩阵基本回路矩阵(fundamental loop matrix)1-8 矩阵矩阵Q与矩阵与矩阵B之间的关系之间的关系 1-9 对偶图对偶图 设有一个连通的平面图设有一个连通的平面图G，具有，具有n+1个节点、个节点、b条支条支路、路、l(=bn)个网孔。如果还有另一个连通的平面图个网孔。如果还有另一个连通的平面图满足下列条件，则称图满足下列条件，则称图G与图与图互为对偶图。(1)G的网孔（包括外网孔，总共是的网孔（包括外网孔，总共是l+1个）与个）与 的节点一一对应，的节点一一对应，的网孔（包括外网孔）也与的网孔（包括外网孔）也与G的节点一一对应；的节点一一对应；(2)G的支路与的支路与 的支路一一对应，而且的支路一一对应，而且G中任意两个网孔中任意两个网孔(包括包括外网孔外网孔)之间的公共支路对应于之间的公共支路对应于中两相应节点间的支路；中两相应节点间的支路；反之亦然。反之亦然。由此可知：由此可知：G的对偶图具有的对偶图具有b条支路，条支路，l+1个节点、个节点、n+1个网孔个网孔(包包括外网孔括外网孔)。对偶图的网孔与节点一一对应，它们与支路的关联关系也是彼对偶图的网孔与节点一一对应，它们与支路的关联关系也是彼此对应的。此对应的。如果图如果图G是一个有向图，也可作出它的对偶有向图是一个有向图，也可作出它的对偶有向图 先按前述方法作出先按前述方法作出G的对偶无向图的对偶无向图，然后把，然后把G的每一条支路看成的每一条支路看成一个矢量，将此矢量按顺时针方向旋转一个矢量，将此矢量按顺时针方向旋转90，即得，即得中各对中各对应支路的参考方向。应支路的参考方向。