14.1 无向图 有向图概念.pptVIP

* 同构的定义 定义 设G1=V1,E1, G2=V2,E2为两个无向图,若存在双射函数 f: V1?V2, 使得对于任意的 vi,vj?V1, (vi,vj)?E1当且仅当 (f(vi),f(vj))?E2， 并且, (vi,vj)与 (f(vi),f(vj)) 的重数相同，则称G1与G2是同构的，记作G1?G2. 例: v1 v2 v3 v4 v5 u1 u2 u3 u4 u5 设G1=V1,E1,G2=V2,E2,存在一个双射函数f: V1?V2,使得f(vi)=ui. G1 G2 * 如何判断图是否同构? 同构的必要条件, 但它们都不是充分条件: ① 边数相同，顶点数相同 ② 度数列相同 ③ 对应顶点的关联集相同，等等 若破坏必要条件，则两图不同构 但这些都是必要条件,不是充分条件. 至今没有找到判断两个图是否同构的有效算法?,还只能根据定义来判断 例: * 例 :下图中G=(V,E),G’=(V’,E’)是同构的. v1 v2 v3 v4 v5 v6 u1 u2 u3 u4 u5 u6 对任意vi,vj ?V,当(vi,vj) ?E时,有(ui,uj) ?E’ 如:(v1,v2) ?E,有(u1,u2) ?E’ vi和ui一一对应. G G’ * 例 下图中G=（V，E）与G?=（V?，E?）同构吗？ 虽然有相同的结点,边数,但不满足同构的定义,原因是两个图边与结点的关联关系不同. G’中度为3的4个结点构成一个长为4的回路,而G中没有. G G’ * 课堂练习: 例1 试画出4阶3条边的所有非同构的无向简单图 例2 判断下述每一对图是否同构: 度数列不同 不同构 3,4,3,2 2,5,2,3 * 例2 (续) (2) 不同构 入(出)度列不同 (3) 度数列相同 但不同构 为什么? * 完全图 定义 设G为n阶无向简单图,若G中每个顶点均与其余的n-1个顶点相邻,则称G为n阶无向完全图,记作Kn。 例 下图分别给出了一个结点、二个结点、三个结点、四个结点和五个结点的完全图。 什么是简单图:不含平行边也不含环. * n阶无向完全图Kn性质: 边数m=n(n-1)/2, ?=?=n-1 右图为5阶完全图K5 边数:m=5(5-1)/2=10 度数: ?=?=4 * n阶有向完全图: 每对顶点之间均有两条方向相反的有向边的n阶有向简单图. 性质: 边数m=n(n-1), ?=?=2(n-1), ?+=?+=?-=?-=n-1 右图为3阶有向完全图. 边数m=3(3-1)=6 度数?=?=2(3-1)=4 * n阶k正则图: 设G为n阶无向简单图,若对所有顶点,均有d(v)=k,则称G为n阶k正则图. 性质: 边数m=nk/2 右图是3 正则图,也叫彼得森图. d(v)=3 边数:m=10×3/2=15 * 完全图与正则图(续) (1) 为5阶完全图K5 (2) 为3阶有向完全图 (3) 为彼得森图, 它是3 正则图 (1) (2) (3) 彼得森图 * 都有15条边，顶点数都是10，所有顶点的度数都是3，这样的图叫彼得森图。它的一般形状是下面的第一张图，与之同构的图多种多样，形状各异，共有100多种。 * 子图 定义 设G=V,E, G ?=V ?,E ?是2个图 若V ??V且E ??E, 则称G ?为G的子图, G为G ?的母图, 记作G ??G. 如:G1,G2是G的子图. (2) 若G ??G 且V ?=V，则称G ?为G的生成子图. G2是G的生成子图. (3) 若V ??V 或E ??E，称G ?为G的真子图. G1,G2是G的真子图. G G1 G2 * 子图(续) 例 画出K4的所有非同构的生成子图 * 导出子图 (4) 设V ??V 且V ???, 以V ?为顶点集, 以两端点都在V ?中的所有边为边集的G的子图称作V ?的导出子图，记作 G[V ?] 下图,V’={a,b},G1是V’的导出子图.G2呢? G G1 G2 练习:画出V’={a,d,c}的导出子图. * (5) 设E ??E且E ???, 以E ?为边集, 以E ?中边关联的所有顶点为顶点集的G的子图称作E ?的导出子图, 记作 G[E ?] . 下图,E’={e1,e2,e3},G1是E’的导出子图. 练习:画出E’={e1,e6,e7}的导出子图. G G1 * 补图 定义 设G=V,E为n阶无向简单图，以V为顶点集,所有使G成为完全图Kn的添加边组