离散数学导论第5版-第四篇.ppt

《离散数学导论第5版-第四篇.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1离散数学导论（第5版）电子教案徐洁磐2第四篇图论图论用‘结点’表示事物，而用‘边’表示事物间联系，并用‘结点’与‘边’所构成的图用以研究客观世界。为便于计算，建立了图的矩阵表示，这样可以将图论研究与计算相结合，从而使图论研究具有很大的实用性。由于图的形式很多，在实用中我们一般对若干种常用的图作研究，它们是树。在图论学习中主要要掌握如下几个方面：3①图论中的基本概念。②图论中的基础理论。③图的矩阵计算。④几种常用的图。在本篇中共有两部分组成，它们是图论原理与常用图，其中图论原理部分介绍图的基本概念、理论与计算而常用图部分则介绍树与

2、欧拉图。这两部分的有机结合构成了图论的完整的整体。4第8章图论原理§8.1图的基本概念§8.1.1图§8.1.2图的基本概念（1）图的概念图由结点集V＝{v1，v2，…，vn}与边集E＝{l1，l2，…，lm}所组成，可记为：G＝（2）有向图与无向图①边为有向的图称为有向图②边为无向的图称为无向图5（3）几种特殊的图①零图：无边的图。②平凡图：仅有一个结点所组成的图。③完全图：各结点间均有边相联的图。④补图：G＝，G＝如有＝为完全图且E∩E＝，则称G为G的补图。⑤简单图与多重图

3、：包括多重边的图称为多重图，否则称为简单图。⑥有权图：边带权的图。6§8.1.3图的同构⑦同构图：G＝，G＝，V与V以及相应边的结点对中有一一对应关系。§8.1.4图中结点的次数（4）图中结点的次数引入次数deg（v）、引出次数deg（v）、次数deg（v）。定理：deg（vi）=2m7§8.2通路、回路与连通性（5）通路与回路①通路：图中vi至vj的通路是在边的序列：（vi，vi1），（vi1，vi2），…（vik－1，vik），其中vik＝vj②基本通路与简单通路：图各边全不同的通路叫简单通

4、路，各点全不同的通路叫基本通路。③环与回路：边的始点与终点相同称环，通路的起始点与终止点相同称回路。④简单回路与基本回路：简单（基本）通路的起始点与终止点相同称简单（基本）回路。⑤有向图（n,m）的基本通路长度≤n－1，基本回路长度≤n。8（6）图的连通性①图的可达性：图的结点vi到vj间存在通路则称从vi到vj是可达的。②连通图：图的任何两结点间均可达。③三种连通图：强连通：有向图中任何两结点间相互可达则称强连通。弱连通：有向图忽略其边的方向所构成的无向图为连通则称弱连通。单向连通：有向图两结点间至少有一向是可达的则称单向

5、连通。9§9.2欧拉图（15）欧拉图欧拉回路与欧拉通路：通过G中每边一次的回（通）路称欧拉回（通）路，具此回路的图称欧拉图。③欧拉图与欧拉通路：欧拉图每个结点次数为偶数。由vi到vj欧拉通路vi，vj结点次数为奇数，其它结点次数为偶数。10§8.3图的矩阵表示法（7）图的邻接矩阵：G＝为（n，m）图，其邻接矩阵：A＝（aij）n×n.1（vi，vj）Eaij＝0（vi，vj）E（8）通路计算：B＝A，B＝（bij）n×n，Bij表示从vi到vj长度为的通路数，Bij表示vi的回路数。（9）可达性计算：P＝A

6、（＋）A（2）（＋）……（＋）A（n），P＝（Pij）n×n，Pij表示从vi到vj是否可达（0不可达，1可达）。（12）连通性计算：可达性矩阵除对角线元素外均为111第9章常用图§9.1树§9.1.1树的基本性质（10）树的基本概念与属性①树：不含回路的连通图。（n,m）树中必有m＝n－1②树的性质T为树两结点间只有一条通路。§9.1.2有向树（11）有向树12（12）外向树与内向树：有向树中，仅有一个结点引入次数为0（根），其它结点引入次数为1，有些结点引出次数为0（叶）称外向树。有向树中，仅有一个结点引出次数为0（根），其

7、它结点引入次数为1，有些结点引入次数为0（叶）称内向树。§9.1.3二元树（13）二元树与多元树：一个n个结点的外向树：（vi）≤m（i=1,2,…,n），称m元树。如（vi）＝m（i=1,2,…,n）（除叶外），称m元完全树，当m＝2时称二元树或二元完全树。§9.1.4生成树（14）生成树：连通图G＝的生成树TG＝G的子图，且是树并满足V＝V，EE。生成树寻找算法：在G中寻找基本回路，寻到后删除边，并继续寻找，直到无基本回路出现为止。13§9.2欧拉图（15）欧拉图欧拉回路与欧拉通路：通过G中每

8、边一次的回（通）路称欧拉回（通）路，具此回路的图称欧拉图。③欧拉图与欧拉通路：欧拉图每个结点次数为偶数。由vi到vj欧拉通路vi，vj结点次数为奇数，其它结点次数为偶数。14谢谢