1、图论信息学院计算机应用技术系信息学院计算机应用技术系讲课教师：胡静讲课教师：胡静办公地点：信息楼办公地点：信息楼805联络方式：联络方式：13064013020电子邮箱：电子邮箱：ise_ 1/271图论起源和发展图论起源和发展l图论是数学一个分支。它以图为研究对象。图论中图是由若干给定点及连接两点线所组成图形，这种图形通惯用来描述一些事物之间某种特定关系，用点代表事物，用连接两点线表示对应两个事物间含有这种关系。l图论最早起源于一些数学游戏难题研究，如1736年Euler所处理Knigsberg七桥问题，以及民间广为流传一些游戏难题，如迷宫问题，匿门博弈问题，棋盘上马行走路线问题等。这些古老
2、数学难题，当初吸引了很多学者注意，在这些问题研究基础上又继续提出了著名四色猜测，汉密尔顿（周游世界）数学难题。2/272图论起源和发展图论起源和发展l1847年，克希霍夫（Kirchhoff）用图论分析电网络，这是图论最早应用于工程科学。以后伴随科学发展，图论在处理运筹学、网络理论、信息论、控制论、博弈论以及计算机科学等各个领域问题时，显示出越来越大效果。l图论在各种物理学科，化学学科，工程领域，社会科学和经济问题广泛应用，使它受到数学界和工程界广泛支持。3/273离散数学第离散数学第2222讲讲l本讲基本知识点：本讲基本知识点：l1 1、图论中基本概念、图论中基本概念l2 2、通路与回路定义
3、、通路与回路定义l3 3、图连通性、图连通性l4 4、图矩阵表示、图矩阵表示4/274第十四章第十四章 图基本概念基本概念14.114.1图定定义14.114.1 一个无向无向图是一个有序二元组，记作G，其中(1)V称为顶点集顶点集，其元素称为顶点顶点或结点结点。(2)E称为边集边集，它是无序积V&V多重子集，其元素称为无无向边向边，简称为边边。设设A，B为任意两个集合，称为任意两个集合，称a,b|aAbB为为A与与B无序积，记作无序积，记作A&B.元素能够重复出现集合称为元素能够重复出现集合称为多重多重集合集合，某个元素重复出现次数称，某个元素重复出现次数称为该元素为该元素重复度重复度。比如
4、在集合。比如在集合a,b,b,a,a中，中，a,b重复度重复度分别为分别为3,2.5/275第十四章第十四章 图基本概念基本概念定定义14.214.2 一个有向有向图是一个有序二元组，记作D，其中(1)V,称为顶点集顶点集，其元素称为顶点顶点或结点结点。(2)E称为边集边集，它是笛卡儿积VV多重子集，其元素称为有向边有向边，简称为边边。用图形表示无用图形表示无(有有)向图时，惯用小圆圈或实心点表示顶点，向图时，惯用小圆圈或实心点表示顶点，用顶点之间连线表示无向边，用有方向边表示有向边。用顶点之间连线表示无向边，用有方向边表示有向边。6/276第十四章第十四章 图基本概念基本概念 v v1 1。
5、v v2 2 v v3 3。(1)v v4 4。v v5 5 a a。b (2)d。c 例例14.114.1画出以下画出以下图形。形。(1)G=,(1)G=,其中其中V=V=v v1 1,v v2 2,v v3 3,v v4 4,v v5 5,E=(,E=(v v1 1,v v1 1),),(v v1 1,v v2 2),(),(v v2 2,v v3 3),),(v v2 2,v v3 3),(),(v v1 1,v v5 5),),(v v2 2,v v5 5),(),(v v4 4,v v5 5)。(2)D=,(2)D=,其中其中V=a,b,c,d,E=a,V=a,b,c,d,E=,b。
6、7/277第十四章第十四章 图基本概念基本概念与与图相关概念和要求相关概念和要求(1)(1)普通用普通用G G泛指图。泛指图。V(G)V(G)、E(G)E(G)分别表示分别表示G G顶点集、边集，顶点集、边集，|V(G)|V(G)|、|E(G)|E(G)|分别表示分别表示G G顶点数、边数。顶点数、边数。若若|V(G)|=n,|V(G)|=n,则称则称G G为为n n阶图阶图。(2)(2)若若|V(G)|V(G)|、|E(G)|E(G)|均为有限数，则称均为有限数，则称G G为为有限图有限图。这。这是本书讨论重点。是本书讨论重点。(3)(3)在图在图G G中，若中，若E(G)=E(G)=,则称
7、则称G G为为零图零图.此时若此时若|V(G)|=n|V(G)|=n，则称，则称G G为为n n阶零图阶零图，记作，记作N Nn n。特殊称。特殊称N N1 1为为平凡图平凡图。8/278第十四章第十四章 图基本概念基本概念定定义14.314.3 在无向图中，关联一对顶点无向边假如多于在无向图中，关联一对顶点无向边假如多于1 1条，则称这条，则称这些边为些边为平行边平行边，平行边条数称为，平行边条数称为重数重数。在有向图中，关联一对顶点有向边假如多于在有向图中，关联一对顶点有向边假如多于1 1条，而且这条，而且这些边始点与终点相同些边始点与终点相同(即方向相同即方向相同)，则称这些边为，则称这
8、些边为平行边平行边。含平行边图称为含平行边图称为多重图多重图，既不含平行边也不含环图称为，既不含平行边也不含环图称为简单图简单图。如：如：。a a。b be e。d d。c c。9/279第十四章第十四章 图基本概念基本概念定义定义14.414.4 设设G=G=为一无向图，为一无向图，结点结点v(vV)v(vV)关联边数之和称关联边数之和称作该结点作该结点度数度数，简称为，简称为度度，记作，记作d dG G(v),(v),简记作简记作d(v).d(v).设设D=D=为一有向图，结点为一有向图，结点v(vV)v(vV)关联边中关联边中，以以v v为边为边始点边数之和称作始点边数之和称作v v出度
9、出度，记作，记作d dD D+(v)(v)，简记作，简记作d d+(v)(v)；以；以v v为边终点边数之和称作为边终点边数之和称作v v入度入度，记作，记作d dD D-(v)(v)，简记作，简记作d d-(v).(v).称称d d+(v)+d(v)+dD D-(v)(v)为为v v度数度数，记作，记作d(v).d(v).在无向图G中，令(G)=maxd(v)|vV(G)(G)=maxd(v)|vV(G)(G)=mind(v)|vV(G)(G)=mind(v)|vV(G)称，分别为G最大度和最小度。10/2710第十四章第十四章 图基本概念基本概念定理定理14.114.1握手定理握手定理 设
10、设G=G=为任意无向图，为任意无向图，V=V=v v1 1,v v2 2,v vn n,|E|=m,|E|=m,则则证实：G中每条边（包含环）均提供2个端点，故在计算各顶点度数和时，每条边均提供2度，m条边共提供2m度。=2m=2m即个顶点度数之和等于边数即个顶点度数之和等于边数2 2倍。倍。11/2711定理定理14.214.2握手定理握手定理 设设D=D=为任意有向图，为任意有向图，V=V=v v1 1,v v2 2,v vn n,|E|=m,|E|=m,则则=2m=2m，且，且=m=m证实：D中每条边（包含环）均关联两个顶点，故在计算各顶点度数和时，每条边均提供2度，即1个出度和1个入度
11、，m条边则提供m个出度，m个入度，共2m度。第十四章第十四章 图基本概念基本概念12/2712第十四章第十四章 图基本概念基本概念推推论 任何图中，奇度顶点个数一定是偶数。任何图中，奇度顶点个数一定是偶数。证实：设G=为任一图，令V1=v|vVd(v)为奇数V2=v|vVd(v)为偶数则V1V2=V,V1V2=,由握手定理知2m=2m=故故+必为偶数，又必为偶数，又V V1 1为奇度顶点集，故为奇度顶点集，故|V V1 1|必为偶数必为偶数.13/2713经典例典例题：例例1:1:已知无向图已知无向图G G中有中有1010条边，条边，2 2个个2 2度顶点度顶点,2,2个个3 3度顶点度顶点,
12、1,1 个个4 4度顶点度顶点,其余顶点度数都是其余顶点度数都是1,1,问问G G中有多少个顶点中有多少个顶点?例例2:2:已知无向图已知无向图G G中有中有1010条边，条边，3 3度与度与4 4度顶点各度顶点各2 2个个,其余其余顶点度数均小于顶点度数均小于3,3,问问G G中最少有多少个顶点中最少有多少个顶点?第十四章第十四章 图基本概念基本概念解解 ：假设顶点个数为：假设顶点个数为n n个，则由握手定理可知个，则由握手定理可知 2*2+2*3+1*4+2*2+2*3+1*4+（n-1-2-2n-1-2-2）*1=10*2*1=10*2故故 n=11 n=1114/2714定义定义14.
13、5完全图完全图1.设设G为一个含有为一个含有n个结点无向简单图，假如个结点无向简单图，假如G中任一个结点都与其余中任一个结点都与其余n-1个结点相邻接，则称个结点相邻接，则称G为为无向完全图无向完全图，简称，简称G为为完全图完全图，记为，记为Kn。2.设设G为一个含有为一个含有n个结点有向简单图，若对个结点有向简单图，若对于任意于任意u,v V(u v)，现有有向边，现有有向边，又有有向，又有有向边边，则称，则称G为为有向完全图有向完全图，在不发生误解情况，在不发生误解情况下，也记为下，也记为Kn。无向完全图无向完全图K Kn n边数边数为为=n(n-1)n(n-1)，有向完全，有向完全图图K
14、 Kn n边数边数为为=n(n-1)=n(n-1)。第十四章第十四章 图基本概念基本概念15/2715第十四章第十四章 图基本概念基本概念14.214.2通路与回路通路与回路 定定义14.1114.11图图G G中中结点和点和边相相继交交织出出现序列序列T=vT=v0 0e e1 1v v1 1e e2 2v v2 2eek kv vk k，若，若T T中中边e ei i两端点是两端点是v vi-1i-1和和v vi i（G G是有向是有向图时要求要求v vi-1i-1与与v vi i分分别是是e ei i始点和始点和终点），点），则称称T T为结点点v v0 0到到结点点v vk k通路通路
15、。v v0 0和和v vk k分分别称称为此通路始点和此通路始点和终点，点，统称称为通路通路端点端点。通路中通路中边数目数目k k称称为此此通路通路长度度。当当v v0 0v vR R时，此通路称，此通路称为回路回路。16/2716若通路中全部若通路中全部边e e1 1，e e2 2，e ek k互不相同，互不相同，则称此通称此通路路为简单通路通路或一条或一条迹迹；若回路中全部；若回路中全部边e e1 1，e e2 2，e ek k互不相同，互不相同，则称此回路称此回路为简单回路回路或一条或一条闭迹迹；若通路中全部若通路中全部结点点v v0 0，v v1 1，v vk k互不相同，互不相同，则
16、称此称此通路通路为基本通路基本通路或者或者初初级通路通路、路径路径；若回路中除；若回路中除v v0 0v vk k外全部外全部结点点v v0 0，v v1 1，v vk-1k-1互不相同（从而全部互不相同（从而全部边互不相同），互不相同），则称此回路称此回路为基本回路基本回路或者或者初初级回路回路、圈圈。基本通路基本通路(或基本回路或基本回路)一定是一定是简单通路通路(或或简单回路回路)，但反之，但反之则不一定。不一定。第十四章第十四章 图基本概念基本概念17/2717第十四章第十四章 图基本概念基本概念14.314.3图连通性通性 定定义14.1214.12 设无向图G=,u,vV,若u,v
17、之间存在通路，则称u,v是连通，记作uv.uV,要求vv.由定义不难看出，无向图中顶点之间连通关系 =|u,v V且u与v之间有通路显然是自反，对称，传递，因而是V上等价关系定定义14.1314.13 若无向图G是平凡图或G中任何两个顶点都是连通，则称G为连通图，不然称G为非连通图或分离图。18/2718定定义14.1414.14 若无向图G=，V关于顶点之间连通关系商集V/=V1 1,V2 2,Vk k,Vi i为等价类，称导出子图GVi i(I=1,2,k)为G连通分支，连通分支数k常记为p(G).例:以下图连通分支数分别为:第十四章第十四章 图基本概念图基本概念v3。v1e4v2v4v5
18、e1e3e5e6e7v3。v1v2v4v5e1e3v3。V1v213319/2719。第十四章第十四章 图基本概念基本概念定定义14.1714.17 设无向图G=,若存在E E,且E，使得P(G-E)P(G)，而对于任意E E，都有P(G-E)=P(G)，则称E是G边割集边割集，或简称为割集割集。若E是单元集，即E=e,则称e为割边割边或桥桥.定定义14.1614.16 设无向图G=,若存在VV,且V，使得P(G-V)P(G)，而对于任意VV，都有P(G-V)=P(G)，则称V是G点割集点割集，若V是单元集，即V=v,则称v为割点割点.v5v1e3v2v3v4e1e5e4e6e2v620/27
19、20第十四章第十四章 图基本概念基本概念14.414.4图矩矩阵表示表示定定义14.2414.24 设无向图G=,V=v1 1,v2 2,vn n,E=e1 1,e2 2,em m,令mij为顶点vi i与边ej j关联次数，则称(mij)nm为G关联矩阵关联矩阵，记作M(G)。以下列以下列图关关联矩矩阵为：。v3v1e4v2v4v5e1e3e5e6e7v6e21 0 0 0 1 0 010 0 0 0 0 10 0 1 0 0 1 00 0 1 1 0 0 10 0 0 1 1 0 00 2 0 0 0 1 0关关联矩矩阵性性质P P284284.21/2721第十四章第十四章 图基本概念基
20、本概念14.414.4图矩矩阵表示表示定定义14.2514.25 设有向图D=中无环,V=v1 1,v2 2,vn n,E=e1 1,e2 2,em m,令mij为顶点vi i与边ej j关联次数，则称(mij)nm为G关联矩阵关联矩阵，记作M(G)。1,vi i为ej j始点mij=0，vi i与ej j是不关联 -1，vi i为ej j终点则称(mij)nm为D关联矩阵，记作M(D)。22/2722第十四章第十四章 图基本概念基本概念关关联矩矩阵性性质P P285285.以下列以下列图关关联矩矩阵为：-1 -1 1 1 0 0 00 1 -1 0 1 0 00 0 0 -1 0 1 -11
21、 0 0 0 -1-1 -1e e3 3e e1 1e e2 2e e4 4e e5 5e e6 6e e7 723/2723第十四章第十四章 图基本概念基本概念定定义14.2614.26设有向图D=中无环,V=v1 1,v2 2,vn n,E=e1 1,e2 2,em m,令aij(1)为顶点vi i与邻接到顶点vj j边条数，称(aij(1)nn为D邻接矩阵邻接矩阵，记作A(D)，或简记为A。邻接矩接矩阵性性质P P286286.以下列以下列图邻接矩接矩阵为：e e3 3e e1 1e e2 2e e4 4e e5 5e e6 6e e7 70 1 1 01 0 0 10 0 1 01 0
22、 1 0邻接矩阵展示了两点间长度邻接矩阵展示了两点间长度为为1 1通路数，那么怎样求两点通路数，那么怎样求两点间长度为间长度为L L通路数呢？通路数呢？24/2724第十四章第十四章 图基本概念基本概念定定义14.2714.27 设D=为有向图,V=v1 1,v2 2,vn n,令可达矩可达矩阵实例例PP350350.1,vi i可达vj jpij=0，vi i不可达vj j称(pij)nn为D可达矩阵可达矩阵，记作P(D),简记作P。25/2725第十四章第十四章 图基本概念基本概念Warshall算法算法一个求一个求可达矩可达矩阵算法：算法：设设M为有向图为有向图D长度为长度为1可达矩阵，
23、则可达矩阵，则(1)置新矩阵置新矩阵N=M;(2)置置i=1;(3)对对j(1jn),若若N第第j 行第行第i 列处为列处为1，则对，则对k=1,2,n 做以做以下计算：下计算：将将N 第第j 行行k 列处元素与第列处元素与第i 行行k 列处元素进行逻辑加，列处元素进行逻辑加，然后将结果放到第然后将结果放到第j 行行k 列处，即列处，即 N j,k=N j,k+N i,k;(4)i=i+1;(5)若若in,go(3),不然停顿。不然停顿。最终得到矩阵最终得到矩阵N即为所求。即为所求。26/2726离散数学离散数学 第第2222讲讲本本讲小小结：l图论中基本概念中基本概念l握手定理及推握手定理及推论l完全完全图及其特征及其特征l通路及回路通路及回路27/2727
