《(47)--5.3 子图与同构图离散数学离散数学.ppt》由会员分享，可在线阅读，更多相关《(47)--5.3 子图与同构图离散数学离散数学.ppt（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、子图与同构图G=，G=(1)若V V，E E，则G是G的母图，G是G的子图，记作：G G。(2)若G G且G G，则称G是G的真子图。(3)若G G 且V=V，则G是G的生成子图。(4)设V1 V，且V1 ，以V1为结点集，以两端点均在V1中的全体边为边集的G的子图，称为V1导出的子图。(5)设E1 E，且E1 ，以E1为边集，以E1中边关联的结点的全体为结点集的G的子图，称为E1导出的子图。1、子图与母图一些基本的结论：n图G是G的子图；n平凡图是任何图的子图；n零图是任何同阶图的子图；n若G是图G的子图，则G的任何子图也是G的子图。1、子图与母图v1v4v3v2e1e2e3e4e5e8e6
2、e7v5图G图G1子图真子图子图真子图生成子图子图真子图导出子图图G2图G31、子图与母图补图：给定一个n阶简单图G=（V,E），以V为结点集，以所有能使G 成为完全图的添加边组成边集的图。记作：G。画补图时，边和原图是互补的，但结点不变。尤其不要漏掉孤立结点。图G图D图G图D2、补图n很显然，这两个图形表示的是同一个无向图G。abcde1e6e4e5e3e2abcde1e6e4e5e3e2图a图bn图是表达事物之间关系的工具，结点所在的位置，边的曲直，不影响事物之间的关系，从而引入图的同构，同构图可以看成是同一个图。3、同构图同构：对于G=，G =，如果存在双射g:VV，满足：(1)任意e=
3、(vi,vj)（或）E 当且仅当 e=(g(vi),g(vj)（或）E(2)e与e的重数相同则称G与G 同构，记作G G。3、同构判断以下两图是否同构。构造结点之间的双射函数f：f(1)=a,f(2)=b,f(3)=c,f(4)=d,f(5)=g,f(6)=f,f(7)=e,f(8)=h。容易验证，f 满足图的同构定义，所以G G。12348765图Gacegbdfh图G3、同构判断同构图的必要条件：结点数目相同，边数相同，关联相同边数的结数目相等。H1H2H1、H2虽然满足以上3个条件，但不同构。图H1中的4个关联3条边的结点与H2中的4个关联3条边的结点的相互间的邻接关系显然不相同。3、同构THANK YOU