图的基本概念Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望图论的研究对象世界由事物组成,事物之间有联系.图可以直观地描述事物及其间联系.用结点表示事物用边表示它们之间的联系可见,图模型几乎可用于任何领域.图论图论(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, emek 可记为无序或有序的顶点对(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 9赋权图定义:如果给图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 16例:同构下图显示了图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