离散数学 7-3 图的矩阵表示ppt课件.ppt

《离散数学 7-3 图的矩阵表示ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学DiscreteMathematics山东科技大学信息科学与工程学院图的定义点的度数特殊的图图同构7-1图的基本概念三、特殊的图1、多重图定义7-1.4：含有平行边的图称为多重图。2、简单图：不含平行边和环的图称为简单图。3、完全图定义7-1.5：简单图G=中，若每一对结点间均有边相连，则称该图为完全图。有n个结点的无向完全图记为Kn。无向完全图：每一条边都是无向边不含有平行边和环每一对结点间都有边相连如果在Kn中，对每一条边任意确定一个方向，则称该图为n个结点的有向完全图。显然它的边数为n(n-1)/2。定理7-1.4在任何图中,n个结点的无

2、向完全图Kn的边数为n(n-1)/2。证明：n个结点中任取两个结点的组合数为Cn2=n(n-1)/2故的边数为

3、E

4、=n(n-1)/25、相对于完全图的补图定义7-1.6：给定一个简单图G，由G中所有结点和所有能使G成为完全图的添加边组成的图，称为G的相对于完全图的补图，或简称为G的补图，记为G。即G=，G=，其中E2={(u，v)u，vV，(u，v)E1}。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全图K5(b)图G(c)图G的补图G’6、子图定义7-1.7：设图G=，如果有图G’=

5、’，E’>，且E’E，V’V，则称G’为G的子图。当V’=V时，则称G’为G的生成子图。例如，下图，图(b)的G和图(c)的G’都是图(a)的K5的子图。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全图K5(b)图G(c)图G的补图G’7、相对于图G的补图定义7-1.8：设G’=是G=的子图，若给定另一个图G”=使得E”=E-E’，且V”中仅包含E”的边所关联的结点，则称G”是子图G’相对于图G的补图。例如，上图(b)的G是图(c)的G’相对于图(a)的K5的补图。v5v1v2v3v4v5v1v2

6、v3v4v5v1v2v3v4(a)完全图K5(b)图G(c)图G的补图G’图的定义点的度数特殊的图图同构7-1图的基本概念四、同构定义7-1.9：设图G=及图G’=，如果存在一一对应的映射g：ViVi’且e=(vi，vj)(或)是G的一条边，当且仅当e’=(g(vi)，g(vj))(或)是G’的一条边，则称G与G’同构，记作G≌G’。两图同构的一些必要条件：1.结点数目相同；2.边数相等；3.度数相同的结点数目相等。以上几个条件不是两个图同构的充分条件。见279页图7-1.10同构必须是结点和边分

7、别存在一一对应。练习279页（3）对应结点度数不同，所以两图不同构。作业279页:(5)（6）7-2路与回路在现实世界中，常常要考虑这样的问题：如何从一个图中的给定结点出发，沿着一些边连续移动而达到另一指定结点，这种依次由点和边组成的序列，就形成了路的概念。学习本节要熟悉如下术语(22个)：路、路的长度、迹、回路、通路、圈、连通、连通分支、点割集、连通图、割点、点连通度、边割集、边连通度、割边、可达、单侧连通、强连通、强分图、弱连通、弱分图、单侧分图掌握5个定理，一个推论。路无向图的连通性有向图的连通性7-2路与回路一、路定义7-2.1给定图G=,设v

8、0,v1,…,vnV，e1,…,enE,其中ei是关联于结点vi-1,vi的边，交替序列v0e1v1e2…envn称为结点v0到vn的路（拟路径Pseudopath）。v0和vn分别称为路的起点和终点，边的数目n称作路的长度。当v0=vn时，这条路称作回路（闭路径closedwalk）。若一条路中所有的边e1,…,en均不相同,称作迹（路径walk）。若一条路中所有的结点v0,v1,…,vn均不相同,称作通路(Path)。闭的通路,即除v0=vn之外，其余结点均不相同的路，称作圈（回路circuit）。例如路：v1e2v3e3v2e3v3e4v2e6v5e7

9、v3迹：v5e8v4e5v2e6v5e7v3e4v2通路：v4e8v5e6v2e1v1e2v3圈：v2e1v1e2v3e7v5e6v2在简单图中一条路v0e1v1e2…envn，由它的结点序列v0，v1，…，vn确定，所以简单图的路，可由其结点序列表示。在有向图中，结点数大于1的一条路亦可由边序列e1e2…en表示。定理7-2.1在一个具有n个结点的图中，如果从结点vj到结点vk存在一条路，则从结点vj到结点vk必存在一条不多于n-1条边的路。证明思路：多于n-1条边的路中必有重复出现的结点，反复删去夹在两个重复结点之间的边之后，剩余的边数不会超过n-1条边。

10、推论在一个具有n个结点