一生只爱你。天涯海角,永不言弃。.ppt

第四篇 图 论 图论用‘结点’表示事物，而用‘边’表示事物间联系，并用‘结点’与‘边’所构成的图用以研究客观世界。为便于计算，建立了图的矩阵表示，这样可以将图论研究与计算相结合，从而使图论研究具有很大的实用性。由于图的形式很多，在实用中我们一般对若干种常用的图作研究，它们是树、平面图与两分图。 在图论学习中主要要掌握如下几个方面： ① 图论中的基本概念。 ② 图论中的基础理论。 ③ 图的矩阵计算。 ④ 几种常用的图。 在本篇中共有两部分组成，它们是图论原理与常用图，其中图论原理部分介绍图的基本概念、理论与计算而常用图部分则介绍树、平面图与两步图等三种常用图，这两部分的有机结合构成了图论的完整的整体。 第十二章 图论原理 §12.1 图的基本概念 §12.1.1 图 §12.1.2 图的基本概念 （1）图的概念 图由结点集V＝{v1，v2，…，vn}与边集E＝{l1，l2，…，lm}所组成，可记为： G＝V，E （2）有向图与无向图 ① 边为有向的图称为有向图 ② 边为无向的图称为无向图 （3）几种特殊的图 ① 零图：无边的图。 ② 平凡图：仅有一个结点所组成的图。 ③ 完全图：各结点间均有边相联的图。 ④补图：G＝V，E，G?＝V，E?如有＝V，E∪E?为完全图且E∩E?＝?，则称G为G的补图。 ⑤ 简单图与多重图：包括多重边的图称为多重图，否则称为简单图。 ⑥ 有权图：边带权的图。 §12.1.3 图的同构 ⑦ 同构图：G＝V，E，G?＝V?，E?，V与V?以及相应边的结点对中有一一对应关系。 §12.1.4 图中结点的次数 （4）图中结点的次数 ? 引入次数deg（v） 、引出次数deg（v）、次数deg（v）。 ? 定理： deg（vi）= 2m §12.2 通路、回路与连通性 （5）通路与回路 ① 通路：图中vi至vj的通路是在边的序列：（vi，vi1），（vi1，vi 2），…（vi k－1，vi k），其中vi k＝vj ② 基本通路与简单通路：图各边全不同的通路叫简单通路，各点全不同的通路叫基本通路。 ③ 环与回路：边的始点与终点相同称环，通路的起始点与终止点相同称回路。 ④ 简单回路与基本回路：简单（基本）通路的起始点与终止点相同称简单（基本）回路。 ⑤ 有向图（n , m）的基本通路长度≤ n－1，基本回路长度≤n。 （6）图的连通性 ① 图的可达性：图的结点vi到vj间存在通路则称从vi到vj是可达的。 ② 连通图：图的任何两结点间均可达。 ③ 三种连通图： ? 强连通：有向图中任何两结点间相互可达则称强连通。 ? 弱连通：有向图忽略其边的方向所构成的无向图为连通则称弱连通。 ? 单向连通：有向图两结点间至少有一向是可达的则称单向连通。 §12.3 图的矩阵表示法 （9）图的邻接矩阵： （10）通路计算： B＝A ，B＝（bij）n?×n?，Bij表示从vi到vj长度为 l 的通路数，Bij表示vi的回路数。 （11）可达性计算： P＝A（＋）A（2）（＋）……（＋）A（n），P＝（Pij）n × n，Pij表示从vi到vj是否可达（0不可达，1可达）。 （12）连通性计算： 可达性矩阵除对角线元素外均为1 第十三章 欧拉图与哈密尔顿图 §13.1