图的基本概念.ppt

Lu Chaojun, SJTU Lu Chaojun, SJTU 图的基本概念 * Lu Chaojun, SJTU 图论的研究对象 世界由事物组成,事物之间有联系. 图可以直观地描述事物及其间联系. 用结点表示事物 用边表示它们之间的联系 可见,图模型几乎可用于任何领域. 图论(graph theory)就是以这种结点和边构成的图为研究对象. * Lu Chaojun, SJTU 图的例子 七桥问题 红楼家谱 乙烷 Lu Chaojun, SJTU * 图的定义 定义:图(graph) G是一个二元组:G=(V,E),其中V是非空结点(vertex)集合,E是边(edge)的集合,每条边与V中两个结点(可相同)相关联. 对任意图G,约定用V(G)和E(G)表示该图的顶点集和边集. 例如右图G: V(G)={A,B,C} E(G)={AB, BC, AC} Lu Chaojun, SJTU * 有限图vs无限图 有限图:V和E是有限集合 无限图:V或E是无限集合 我们只讨论有限图: V = {v1, v2,…, vn} E = {e1, e2,…, em} ek 可记为无序或有序的顶点对(vi,vj). 称ek 与vi、vj关联, vi、vj是ek的端点 称vi和vj相邻(adjacent或neighbors) 以后不加说明时,都假定图有n个顶点,m条边. Lu Chaojun, SJTU * 无向图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 * 简单图vs多重图 自环(loop):两端点重合的边.即ek = (vi, vi). 重边(multiple edges):两结点间的多条边. 多重图(multigraph):有重边的图. 简单图(simple graph):无重边无自环的无向图. 空图(null/empty graph):无边的简单图,记作Nn . 有的书定义空图是(?,?). 完全图(complete graph):任意两结点间都有边的简单图.n个顶点的完全图记作Kn . Lu Chaojun, SJTU * 结点的度 结点的度(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中各结点的度都为n?1. 度为0的顶点称为孤立点. Lu Chaojun, SJTU * 若干基本性质 (1)[握手定理] G=(V,E),|E|=m.则 . (2) 图G中度为奇数的结点必有偶数个. (3) 有向图中:正度之和=负度之和=边数. (4) Kn的边数为n(n?1)?2. (5) 非空简单图中一定存在度相同的结点. Lu Chaojun, SJTU * 赋权图 定义:如果给图G=(V,E)的每条边ek 都赋以一个实数wk作为该边的权(weight),则称G是赋权图. 特别地,如果权都是正数,称为正权图. 应用中往往是赋权图.权可以表示长度、时间、费用等. 例: Lu Chaojun, SJTU * 子图 定义:给定G=(V,E), 如果G? = (V?,E?)满足V??V, E?? E,则称G?是G的子图(subgraph),记作G?? G. 如果V?=V,就称G?是G的支撑(spanning)子图或者生成子图; 如果V??V且对任何vi, vi ?V?,若ek=(vi, vj) ?E则ek?E?,则称G?是G的导出(induced)子图. 平凡子图: G和Nn * Lu Chaojun, SJTU 例:子图 下图中 G?和G?都是G的子图 G?是G的导出子图,而G?不是 G?是G的支撑子图,而G?不是 Lu Chaojun, SJTU * 图的运算 定义G1=(V1,E1)和G2=(V2,E2)的 并: G1?G2=(V1?V2, E1?E2) 交: G1?G2=(V1?V2, E1