1、离离 散散 数数 学学Discrete Mathematics 山东科技大学信息科学与工程学院 图的定义 点的度数 特殊的图 图同构7-1 图的基本概念三、特殊的图1、多重图定义 7-1.4：含有平行边的图称为多重图。2、简单图：不含平行边和环的图称为简单图。3、完全图定义 7-1.5：简单图 G=中，若每一对结点间均有边相连，则称该图为完全图。有 n个结点的无向完全图记为 Kn。无向完全图：每一条边都是无向边不含有平行边和环每一对结点间都有边相连如果在 Kn中，对每一条边任意确定一个方向，则称该图为 n个结点的有向完全图。显然它的边数为 n(n-1)/2。定理 7-1.4 在任何在任何 图中
2、 , n个结点的无向完全图 Kn的边数为 n(n-1)/2。 证明： n个结点中任取两个结点的组合数为Cn2 = n(n-1)/2故的边数为|E| = n(n-1)/2 5、 相对于完全图的补图定义 7-1.6：给定一个简单图 G，由 G中所有结点和所有能使G成为完全图的添加边组成的图，称为 G的相对于完全图的补图，或简称为 G的补图，记为 G。即 G=，G=， 其中 E2=(u， v)u， vV， (u， v)E1。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全图 K5 (b)图 G (c)图 G的补图 G6、子图定义 7-1.7：设图 G=， 如果有图 G=，且 E
3、E， VV， 则称 G为 G的 子图。当 V=V时，则称 G为 G的生成子图。例如，下图， 图 (b)的 G和图 (c)的 G 都是图 (a)的 K5的子图。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全图 K5 (b)图 G (c)图 G的补图 G7、 相对于图 G的补图定义 7-1.8： 设 G=是 G=的子图，若 给定另一个图 G”=使得 E”=E-E，且 V”中仅包含 E”的边所关联的结点，则称 G”是子图 G相对于图 G的补图。例如，上图 (b)的 G是图 (c)的 G 相对于图 (a)的 K5的补图。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全图 K5 (b)图 G (c)图 G的补图 G 图的定义 点的度数 特殊的图 图同构7-1 图的基本概念四、同构定义 7-1.9：设图 G=及图 G=，如果存在一一对应的映射 g： ViVi且 e=(vi， vj)(或 )是 G的一条边，当且仅当 e=(g(vi)，g(vj)(或 )是 G的一条边，则 称 G与 G同构，记作 G G。两图同构的一些必要条件：1.结点数目相同；2.边数相等；3.度数相同的结点数目相等。以上几个条件不是两个图同构的充分条件。见 279页图 7-1.10同构必须是结点和边分别存在一一对应。练习279页（ 3）对应结点度数不同，所以两图不同构。
