1、图论图的基本概念教师：孙继荣教师：孙继荣电话：电话：8776860987768609Email:sunjrEmail:计算机数学基础孙继荣图论图的基本概念n教学要求n理解图的概念：结点、边、有向图，无向图、图的同构、简单图、完全图、结点的度数、子图、边的重数和平行边等n理解握手定理n了解通路与回路概念：通路(简单通路、初级通路和复杂通路)，回路(简单回路、初级回路和复杂回路)，会求通路和回路的长度n了解无向图的连通性，会求无向图的连通分支。了解点割集、割点、边割集、割边、点连通度、边连通度等概念n了解有向图的强连通强性；会判别其类型n了解(有向图、无向图)关联矩阵、(无向图)相邻矩阵和(有向图
2、)邻接矩阵的概念，掌握构造方法及其应用。n知道带权图、最短通路概念，知道关键路径概念 计算机数学基础孙继荣图论图的基本概念n学习内容：学习内容：n图的概念 （图的表示，有向图、无向图、度、同构）n图的矩阵表示（邻接矩阵，关联矩阵）计算机数学基础孙继荣图论图的基本概念n本章重点本章重点n图的概念n握手定理n通路n回路n图的矩阵表示.计算机数学基础孙继荣图论图的基本概念n图的基本概念图是指某些具体的事物以及这些事物之间的联系n图是一个有序对，V是结点集，E是边集，当V,E有限时，称为有限图；否则称无限图.n无向边,与无序结点(v,u)相关联的边n有向边，与有序结点相关联的边.n无向图，每条边都是无
3、向边的图，记作G;每条边都是有向边的图，记作D.n混合图，既有有向边，也有无向边的图.计算机数学基础孙继荣图论图的基本概念n图的基本概念n平凡图平凡图，仅有一个结点的图；n零图零图（空图）：边集为空集的图，即仅有结点的图.n自回路自回路(环)，关联于同一个结点的边.n无向平行边无向平行边，联结相同两个结点的多于1条的无向边；有向平行边有向平行边，联结两个结点之间的多于1条且方向相同的有向边.n简单图简单图，不含平行边和自回路的图.计算机数学基础孙继荣图论图的基本概念n图的基本概念n在无向图G中，与结点v(V)关联的边数，即为结点度数度数deg(v)或d(v).；n有向图G中，以结点v为始点的变
4、的条数为该点的出度出度，记作deg+(v);以结点v为终点的边为该点的入度，记作deg(v)；结点v的出度和入度之和为度数度数.n最大度数最大度数，(G)maxd(v)vV；最小度数最小度数，(G)=mind(v)vV计算机数学基础孙继荣图论图的基本概念1n图的基本概念n有n个结点的且每对结点都有边相连无向简单图，无向完全图无向完全图Kn.此时有 ；有n个结点的且每对结点之间都有两条方向相反的边相关连的有向简单图为有向完全图有向完全图，.此时有n设G,V，E的子集V,E构成的图G=是图G的子图子图；若GG且GG，(VV或EE)，G是G的真子图真子图.n生成子图生成子图，设图G,若EE,则图是的
5、生成子图.即结点与原图G相同的子图，为生成子图.)1(21nnE)1(nnE计算机数学基础孙继荣图论图的基本概念n图的基本概念n补图 G=，设G,以V为结点集，以使G成为完全图所添加的边为边集E的图，就是图G的补图G，即是完全图,其中EE.n图的同构，设G1=和G2=,存在双射f：V1V2，(vi,vj)E1,当且仅当(f(vi),f(vj)E2，且(vi,vj)与(f(vi),f(vj)的重数相同.则G1 G2.n同构充分条件：建立两个图的对应关系，这个关系是双射函数.n同构必要条件：结点数相同；边数相同；度数相同的结点个数相同.计算机数学基础孙继荣图论图的基本概念n图的基本概念n握手定理:
6、结点度数之和为边数的两倍 设G=，有n在有向图图D中，n奇数度结点的个数为偶数个.n如果一个图中只有两个奇数度节点，则这两个节点相连通。VvEv2)deg(VvVvvv)(deg)(deg计算机数学基础孙继荣图论图的基本概念n通路、回路、图的连通性 n通路与通路的长度，设图G，Vv0,v1,vn,E=e1,e2,em,结点与边的交替序列v0e1v1e2vi-1eivi,成为结点v0到结点vi的通路.v0,vi是通路的起点和终点.通路中边的数目就是通路的长度.n回路，起点和终点重合的通路.n简单通路(回路)：边不重复的通路(回路).n初级通路(回路)：结点不重复的通路(回路).n复杂通路(回路)
7、：边有重复的通路(回路).计算机数学基础孙继荣图论图的基本概念n通路、回路、图的连通性n定理：若图中具有n各结点，从结点vi多幅奥结点vj存在一条通路，则从vi到vj存在一条不多于n1条边的通路n推论：在一个具有n个结点的图中，如果存在结点vi到vj的一条通路，则必存在一条从vi到vj的不多于n1条边的初级通路n定理：在一个具有n个结点的图中，如果存在结点vi到自身的回路，则从vi到自身存在不多于n条边的回路。n推论：在一个具有n个结点的图中，如果存在结点vi到自身的简单回路，则从vi到自身存在不多于n条边的初级回路。计算机数学基础孙继荣图论图的基本概念n通路、回路、图的连通性n连通与连通图，
8、无向图G中，结点u,v存在通路，那么u,v是连通的，G中任意结点u,v都是连通的，G是连通图.n连通分支，设G，V的连通等价类V1，V2，,Vm,子图G(V1),G(V2),G(Vm)成为连通分支，P(G)表示图G连通分支的个数.计算机数学基础孙继荣图论图的基本概念n通路、回路、图的连通性n点割集与割点点割集与割点，设无向图G，存在结点集VV，使得P(GV)P(G)，而对任意VV，都有P（GV）P(G)，V称为图G的点割集.若V是单元集，Vv，v叫做割点.n边割集与割边边割集与割边，设无向图G，存在边集EE，使得P(GV)P(G)，而对任意EE，都有P（GE）P(G)，E称为图G的边割集.若E
9、是单元集，Ee，e叫做割边(桥).计算机数学基础孙继荣图论图的基本概念n通路、回路、图的连通性n点连通度：最小的点割集的点数目n边连通度：最小的边割集的边数目n定理5：)()()(GGGK计算机数学基础孙继荣图论图的基本概念n通路、回路、图的连通性n单侧通路单侧通路，有向图中，任意一对结点之间至少有一个结点可达另一结点.n强连通强连通，在有向图中任何一对结点都相互可达.n弱连通弱连通，略去有向图D各边的方向成为无向连通图，称D是弱连通图.n由定义可知：强连通 单侧连通 弱连通.必是必是计算机数学基础孙继荣图论图的基本概念n通路、回路、图的连通性n定理：一个有向图是强连通的充分必要条件是G中有一
10、个回路，它至少经过每个结点一次的。n强分图：既有强连通性的最大子图n单侧分图：既有单侧连通性的最大子图n弱分图：既有弱连通性的最大子图n定理：在有向图D中，它的每个结点位于且仅位于一个强分图中计算机数学基础孙继荣图论图的基本概念n图的矩阵表示 n(无向图)关联矩阵设G=,关联矩阵M(G)=,其中mij=vi与ej的关联次数(行为结点，列为边)n性质：n列元素和为2n行元素和为结点的度数n若行元素和为0，则对应的结点为孤立点n全部元素之和为G的总度数n平行边对应的两列完全相同mEnV,mnijm21miijm)deg(1imjijvmmmnimjij211 计算机数学基础孙继荣图论图的基本概念n
11、图的矩阵表示n(无向图)相邻矩阵:设G,，相邻矩阵 A(G)=，其中aij=vi与vj相关联的边的条数(行、列均为结点)n性质：nA(G)是对称矩阵n对角线上的元素表示该结点处环的个数n ，若vi是孤立结点，则mEnV,nija)deg()(11iniijmjijvaa01mjija计算机数学基础孙继荣图论图的基本概念n图的矩阵表示n（无环有向图）关联矩阵：设D=,关联矩阵M(D)=,(行为结点，列为边)，其中mnijm的终点是边结点不关联边结点的起点是边结点jijijiev1ev0ev1ijm计算机数学基础孙继荣图论图的基本概念n图的矩阵表示n（无环有向图）关联矩阵：n ，列元素和为0n每行
12、元素绝对值之和等于对应点的度数，其中1的个数为对应点的出度，1的个数为对应电的入度n所有元素的和为0，1的个数等于1的个数，都等于边数m01niijm)deg(1imjijvm计算机数学基础孙继荣图论图的基本概念n图的矩阵表示n（有向图）邻接矩阵：设D，相邻矩阵 A(D)=，其中aij=vi邻接到vj的边的条数(行、列均为结点)n所有元素之和为D中长度为1的通路 n有向图的邻接矩阵不一定对称nijamanimjij 11计算机数学基础孙继荣图论图的基本概念n图的矩阵表示n由有向图D的邻接矩阵推断从ai到aj 的长度为l的通路的数目：Al(D)n由有向图D的邻接矩阵推断D的可达矩阵P(D)P(D)=，其中 P(D)A1(D)A2(D)An(D)将其中大于0的元素都改为1，再将主对角线上的元素改为1。nijp否则可达01jiijvvp计算机数学基础孙继荣图论图的基本概念n最短路径和关键路径n带权图：G，其中W为每边权的集合，即对无向图vij的每边都有一个实数wij与之对应n路径：指的是一条初级通路 初级通路的权n最短路径：在带权图中，从vi到vj的各通路中权和最小的通路n关键路径：在有向带权图中两结点之间的最长通路问题计算机数学基础孙继荣图论图的基本概念n求最短路径的方法n求关键路径的方法n求各结点的最早完成时间n求各结点的最晚完成时间n求缓冲时间n求关键路径
