1-2图的概念和术语精华版解读.ppt

* * Graphs / 图 论 图/Graph 可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。 * * 图论/Graphs 1 图的概念/Introduction of Graph 2 图的术语/Graph Terminology 3 图的表示/ Representing Graph 4 连通性/Connectivity 5 欧拉与哈密尔顿图/ Euler and Hamilton Graphs 6 树/Tree 7 平面图/Planar Graphs 图的着色/Graph Coloring 二部图/Biparties * * 相邻(adjacent),关联(incident) 相邻(邻接)(adjacent): 点与点,边与边 邻接到,邻接于: u邻接到v, v邻接于u 关联(incident),端点:点与边 关联次数: 环(loop):只与一个顶点关联的边 孤立点(isolated vertex): 平行边(parallel edge): 关联集: IG(v) = { e | e与v关联 } 邻域: NG(v)={u | u与v相邻但u?v } ? 2 1 +1 -1 1 u v * * 握手定理 定理14.1:设G=V,E是无向图, V={v1,v2,…,vn}, |E|=m, 则 d(v1)+d(v2)+…+d(vn)=2m. # 定理14.2:设D=V,E是有向图, V={v1,v2,…,vn}, |E|=m, 则 d+(v1)+d+(v2)+…+d+(vn) = d-(v1)+d-(v2) +…+d-(vn) = m. # 推论:任何图中,奇数度顶点的个数是偶数. # * * 简单图(simple graph) 简单图(simple graph): 无环,无平行边 若G是简单图, 则 0 ? ?(G) ? n-1(定理14.4) * * 可图化 定理14.3:非负整数列d=(d1,d2,…,dn)是可图化的, 当且仅当d1+d2+…+dn=0(mod 2). 证明: (?) 握手定理 (?) 奇数度点两两之间连一边, 剩余度用环来实现. # 例3: (1)d=(5,4,4,3,3,2); (2)d=(5,3,3,2,1). 5 3 3 1 5 3 3 1 * * 可简单图化(Havel定理) 定理 (V. Havel, 1955):设非负整数列d=(d1,d2,…,dn)满足: d1+d2+…+dn=0(mod 2), n-1?d1?d2?…?dn?0, 则d可简单图化当且仅当 d’=(d2-1,d3-1,…,dd1+1-1,dd1+2,…,dn) 可简单图化. 例: d=(4,4,3,3,2,2), d’=(3,2,2,1,2) * * 图同构(graph isomorphism) 图同构: 设(有向)图G1=V1,E1, G2=V2,E2, 若存在双射 f:V1?V2, 满足?u?V1,?v?V1, (u,v)?E1 ? (f(u),f(v))?E2 ( u,v?E1 ? f(u),f(v)?E2 ) 则称G1与G2同构, 记作G1?G2 说明: 同构的图,其图论性质完全一样 * * 子图,生成子图 子图(subgraph): G=V,E, G’=V’,E’, G’?G ? V’?V ? E’?E 真子图(proper subgraph): G’?G ? G’?G ? (V’?V ? E’?E) 生成子图(spanning subgraph): G’是G的生成子图 ? G’?G ? V’=V * * 导出子图(induced subgraph) 导出子图: G=V,E, 若V1?V, E1= E ? V1V1,则称 G[V1] = V1,E1 为由V1导出的子图 若??E1?E, V1={v|v与E1中的边关联}, 则称 G[E1] = V1,E1 为由E1导出的子图 * * 完全图(complete graphs) 无向完全图：每个顶点均与其余的n-1个顶点相邻。Kn(n?1） 有向完全图：每个顶点均邻接到其余的n-1个顶点。 n阶竞赛图：基图是无向完全图Kn * * 补图(complement graph) 补图: G=V,E, G=V,E(Kn)-E 自补图(self-complement graph):G?G * * 二部图(偶图)(bipartite graphs) 二部图: G=V1,V2; E, 也称为偶图 * * 练习 PP291 1,5,6,7,8,9 * * 练习 PP292 12,13,16 * 所有顶点的度数和与边的个数有什么关系？