图的基本概念

图的基本概念1Lu Chaojun,SJTU 图论的研究对象 世界由事物组成,事物之间有联系.图可以直观地描述事物及其间联系.用结点表示事物 用边表示它们之间的联系 可见,图模型几乎可用于任何领域.图论图论(graph theory)就是以这种结点和边构成的图为研究对象.2Lu Chaojun,SJTU 图的例子 七桥问题 红楼家谱 乙烷Lu Chaojun,SJTU 3图的定义 定义:图图(graph)G是一个二元组:G=(V,E),其中V是非空结点结点(vertex)集合,E是边边(edge)的集合,每条边与V中两个结点(可相同)相关联.对任意图G,约定用V(G)和E(G)表示该图的顶点集和边集.例如右图G:V(G)=A,B,CE(G)=AB,BC,ACLu Chaojun,SJTU 4有限图vs无限图 有限图:V和E是有限集合 无限图:V或E是无限集合 我们只讨论有限图:V=v1,v2,vnE=e1,e2,em ek 可记为无序或有序的顶点对(vi,vj).称ek 与vi、vj关联,vi、vj是ek的端点称vi和vj相邻(adjacent或neighbors)以后不加说明时,都假定图有n个顶点,m条边.Lu Chaojun,SJTU 5无向图vs有向图 无向边无向边(undirected edge):边无方向.对无向边ek=(vi,vj),vi和vj称为ek的端点.有向边有向边(directed edge):边有方向.对ek=(vi,vj):vi称始点(initial vertex),vj称终点(terminal vertex).vi是vj的直接前趋,vj是vi的直接后继.无向图无向图(undirected graph):都是无向边.有向图有向图(directed graph):都是有向边.混合图:既有无向边也有有向边.Lu Chaojun,SJTU 6简单图vs多重图 自环自环(loop):两端点重合的边.即ek=(vi,vi).重边重边(multiple edges):两结点间的多条边.多重图多重图(multigraph):有重边的图.简单图简单图(simple graph):无重边无自环的无向图.空图(null/empty graph):无边的简单图,记作Nn.有的书定义空图是(,).完全图(complete graph):任意两结点间都有边的简单图.n个顶点的完全图记作Kn.Lu Chaojun,SJTU 7结点的度 结点的度度(degree):与结点v关联的边数,记作d(v).v上自环对d(v)的贡献为2.对有向图:d(v)=d+(v)+d(v)正度(出度out-degree)d+(v)=以v为始点的边数负度(入度in-degree)d(v)=以v为终点的边数自环对正度,负度各贡献1.例如:Kn中各结点的度都为n1.度为0的顶点称为孤立点.Lu Chaojun,SJTU 8若干基本性质(1)握手定理 G=(V,E),|E|=m.则 .(2)图G中度为奇数的结点必有偶数个.(3)有向图中:正度之和=负度之和=边数.(4)Kn的边数为n(n1)2.(5)非空简单图中一定存在度相同的结点.Lu Chaojun,SJTU 9mvdVv2)(赋权图 定义:如果给图G=(V,E)的每条边ek 都赋以一个实数wk作为该边的权权(weight),则称G是赋权图赋权图.特别地,如果权都是正数,称为正权图正权图.应用中往往是赋权图.权可以表示长度、时间、费用等.例:Lu Chaojun,SJTU 10子图 定义:给定G=(V,E),如果G=(V,E)满足VV,E E,则称G是G的子图子图(subgraph),记作G G.如果V=V,就称G是G的支撑支撑(spanning)子图子图或者生成子图生成子图;如果VV且对任何vi,vi V,若ek=(vi,vj)E则ekE,则称G是G的导出导出(induced)子图子图.平凡子图:G和Nn11Lu Chaojun,SJTU 例:子图 下图中G和G都是G的子图G是G的导出子图,而G不是G是G的支撑子图,而G不是Lu Chaojun,SJTU 12图的运算 定义G1=(V1,E1)和G2=(V2,E2)的 并:G1G2=(V1V2,E1E2)交:G1G2=(V1V2,E1E2)对称差:G1G2=(V1V2,E1E2)=(V1V2,(E1E2)(E2E1)13Lu Chaojun,SJTU 图的运算(续)若G2是G1的子图,则定义 差:G1G2=(V1,E1E2)n个结点的简单图G的补图补图G:Kn G显然:G=G 从G中删去结点v及其关联的边:G v 显然:G v是G的导出子图 从G中删去边e:G e 显然:G e是G的支撑子图 向G中增加边eij=(vi,vj):G eij Lu Chaojun,SJTU 14顶点的邻点 无向图G中,顶点v的邻点集定义为(v)=u|(v,u)E(G)有向图G中,顶点v的直接后继集或外邻集定义为+(v)=u|(v,u)E(G)v的直接前趋集或内邻集定义为(v)=u|(u,v)E(G)Lu Chaojun,SJTU 15图的同构 定义:给定两个图G1=(V1,E1)和G2=(V2,E2).如果在V1和V2之间存在双射f 使得(u,v)E1 iff (f(u),f(v)E2则称G1和G2同构同构(isomorphic),记作 .若 ,则有(1)|V(G1)|=|V(G2)|,|E(G1)|=|E(G2)|;(2)G1和G2结点度的非增序列相同;(3)G1的任一导出子图在G2中都有与之同构的导出子图;反之亦然.Lu Chaojun,SJTU 1621GG 21GG 例:同构 下图显示了图G与它的补图同构.Lu Chaojun,SJTU 17例题证明:任意6个人中必有三人相互认识或者有三人互不相识.证:作K6并给边涂色:红=认识,蓝=不认识.只要证图中必有同色三角形.v1有5条边,由抽屉原则必有三边同色(设为红),这三边的另一顶点设为v2,v3,v4.v2v3v4有一边为红色,则与v1构成红色;v2v3v4的三边无红色,则构成蓝色.Lu Chaojun,SJTU 18图的表示法:邻接矩阵 图G=(V,E)的邻接矩阵邻接矩阵(adjacency matrix)是一个nn矩阵A,其元素为:邻接矩阵可以表示自环,但不能表示重边.对有向图:A的第i行之和是vi的正度,第j列之和是vj的负度.对无向图:A是对称矩阵.Lu Chaojun,SJTU 19图的表示法:权矩阵 赋权图常用权矩阵表示:即将前面邻接矩阵的1改成权wij.可见,邻接矩阵是权矩阵的特例(所有边的权都是1).Lu Chaojun,SJTU 20图的表示法:关联矩阵 有向图的关联矩阵(incidence matrix)是一个nm阶矩阵B,其元素为 性质(1)每列只有两个非零元素:1和1(2)第i行1的数目是d(vi),其中1的数目是d+(vi),1的个数是d(vi).(3)能表示重边,但不能表示自环.无向图的关联矩阵:类似,只是没有1.Lu Chaojun,SJTU 21图的表示法:边列表 对关联矩阵的列进行压缩.存储边的信息:分别用m维向量A和B存储每条边的始点编号和终点编号.如果是赋权图,再用m维向量C存储每条边的权.即:对每条边ek=(vi,vj),有Ak=iBk=jCk=wkLu Chaojun,SJTU 22图的表示法:正向表 对邻接矩阵的行进行压缩.n维向量A:Ai存储vi的第一个直接后继的存储地址.(BAi是vi的第一个直接后继)m维向量B:存储m个直接后继顶点的编号.同一个顶点的直接后继在B中连续存储.显然有:vi的后继:BAi,BAi+1,BAi+11.d+(vi)=Ai+1 AiAi=d+(v1)+d+(v2)+d+(vi1)+1 对赋权图,可再用一个m维向量C存储权值.对无向图,B中存储邻点.由于vi和vj互为邻点,所以需要2m维向量.Lu Chaojun,SJTU 23图的表示法:逆向表 对邻接矩阵的列进行压缩n维向量A:Ai存储vi的第一个直接前趋的存储地址.m维向量B:存储m个直接前趋顶点的编号.Lu Chaojun,SJTU 24图的表示法:邻接表 将正向表的m维向量B拆成n个列表,第i个列表存储vi的所有后继.列表通常采用链表结构.链表中每个单元除了可以存储后继结点,还可以存储权值,形如:Lu Chaojun,SJTU 25vi的(直接)后继#wij viEnd26Lu Chaojun,SJTU