《(46)--5.2 图的定义离散数学离散数学.ppt》由会员分享，可在线阅读，更多相关《(46)--5.2 图的定义离散数学离散数学.ppt（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图的定义现实世界中的很多问题都可以表示为图，例如用结点来表示城市，如果两个城市之间有火车可以直达，就用边将表示这两个城市的点连接起来，就形成了一个图。再如将工厂表示为结点，两个工厂之间若存在业务联系，则用边将它们对应的结点相连，就构成了工厂间的业务联系图。一个图就是由一些结点和连接这些结点的一些边所组成的离散结构。无序积：设A,B为二集合，称(a,b)|a A b B 为A与B的无序积，记作：A&B。(a,b)是无序对且(a,b)=(b,a)。有序积：设A,B为二集合，称|a A b B 为A与B的有序积，记作A B。是有序对且 。多重集：元素可重复出现的集合。如集合 a，a，b，c 是多重集
2、，并且 a，a，b，c a，b，c。1、基本图类无 向 图：二元组 G=称为无向图，V是一个非空有限集，V 中元素称为结点；E是无序积V&V的多重子集，E中元素称为无向边（简称边）。无向图的画法：用小圆圈表示V中的每一个元素，如果(vi,vj)E，则在结点vi与vj之间连线段。如：G=，V=v1,v2,v3,v4，E=(v1,v2),(v1,v2),(v2,v3),(v2,v3),(v3,v4),(v2,v4),(v1,v4)v1v4v3v2e1e7e2e3e4e5e61、基本图类有 向 图：二元组 D=称为有向图，V是一个非空有限集，V 中元素称为结点；E是有序积V V 的多重子集，E中元素
3、称为有向边。有向图的画法：同无向图，只是要根据E中元素的次序，由第一元素 用方向线段指向第二元素。如：D=，V=v1,v2,v3,v4，E=,v1v4v3v2e1e2e3e4e5e61、基本图类自 环：仅关联一个结点的边。v1v4v3v2e1e2e3e4e5e6孤立点：无边关联的结点。e1e2e3e4e5e6v1v2v3v5v4v6图G图D2、相关概念平行边：两个结点之间重复的关系定义。结点 与 边 关 联：如果ek=(vi,vj)E，称ek与vi关联，或ek与vj关联。结点与结点相邻：如果ek=(vi,vj)E，称vi与vj相邻；边 与 边 相 邻：如果ek和ei至少有一个公共结点关联，则称
4、ek与ei相邻。若ek为有向边，则称vi邻接到vj,vj邻接于vi。2、相关概念v1v4v3v2e1e2e3e4e5e6e1e2e3e4e5e6v1v2v3v5v4v6图G图D有限图：V，E均为有穷集合。零 图：E 平凡图：E 且|V|=1(n,m)图：|V|=n 且|E|=mn 阶图：|V|=n简单图：不出现自环和平行边的图称为简单图。多重图：包含平行边的图。2、相关概念v1v4v3v2e1e2e3e4e5e6e1e2e3e4e5e6v1v2v3v5v4v6图G图D无向完全图：设G=是n阶无向简单图，如果G中任何一个结点都与其余n1个结点有边相连，则G为无向完全图，记作：Kn。边数？有向完全图：设D=是n阶有向简单图，如果D中任意结点u，v V(u v)，即有有向边，又有有向边，则称D为n阶有向完全图。边数？K5图D2、相关概念THANKYOU