图论PPT教学课件

通路，各点全不同的通路叫基本通路。
③ 环与回路：边的始点与终点相同称环，通路的起始 点与终止点相同称回路。
④ 简单回路与基本回路：简单（基本）通路的起始点 与终止点相同称简单（基本）回路。
⑤ 有向图（n , m）的基本通路长度≤ n－1，基本回路 长度≤n。
（6）图的连通性
① 图的可达性：图的结点vi到vj间存在通 路则称从vi到vj是可达的。
B＝A ，B＝（bij）n×n，Bij表示从vi到vj 长度为 l 的通路数，Bij表示vi的回路数。
（11）可达性计算： P＝A（＋）A（2）（＋）……（＋l ）A（n），
P＝（Pij）n × n，Pij表示从vi到vj是否可达（0不可 达，1可达）。
（12）连通性计算：
可达性矩阵除对角线元素外均为1
在图论学习中主要要掌握如下几个方面：
① 图论中的基本概念。
② 图论中的基础理论。
③ 图的矩阵计算。
④ 几种常用的图。
在本篇中共有两部分组成，它们 是图论原理与常用图，其中图论原理部 分介绍图的基本概念、理论与计算而常 用图部分则介绍树、平面图与两步图等 三种常用图，这两部分的有机结合构成 了图论的完整的整体。
第十二章 图论原理
§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，
（8）哈密尔顿图 •哈密尔顿回路与哈密尔顿通路：通过G中每个结点一次的
回（通）路称哈密尔回（通）路，具此回路的图称哈密尔顿图。
•哈密尔顿图与哈密尔顿通路中的定理 哈密尔顿图的必要条件G＝<V , E>中V1V且P（G－V1）≤|V1|， 其中P（G－V1）为从G中删除V1（包括V1中各结点及其关联边） 后所得到的连通分支数。
② 树的性质 T为树两结点间只有一条通路。
§14.1.2 有向树 （14）有向树
（15）外向树与内向树：有向树中，仅有一个结点引入次数 为0（根），其它结点引入次数为1，有些结点引出次数为0（叶） 称外向树。有向树中，仅有一个结点引出次数为0（根），其它 结点引入次数为1，有些结点引入次数为0（叶）称内向树。
② 连通图：图的任何两结点间均可达。
③ 三种连通图：
• 强连通：有向图中任何两结点间相互可 达则称强连通。
• 弱连通：有向图忽略其边的方向所构成 的无向图为连通则称弱连通。
• 单向连通：有向图两结点间至少有一向 是可达的则称单向连通。
§12.3 图的矩阵表示法
（9）图的邻接矩阵：
（10）通路计算：
第四篇 图 论
图论用‘结点’表示事物，而用‘边’ 表示事物间联系，并用‘结点’与‘边’所构 成的图用以研究客观世界。为便于计算，建立 了图的矩阵表示，这样可以将图论研究与计算 相结合，从而使图论研究具有很大的实用性。 由于图的形式很多，在实用中我们一般对若干 种常用的图作研究，它们是树、平面图与两分 图。
E∪E>为完全图且E∩E＝，则称G为G的补图。 ⑤ 简单图与多重图：包括多重边的图称为多重
图，否则称为简单图。 ⑥ 有权图：边带权的图。
§12.1.3 图的同构
⑦ 同构图：G＝<V，E>，G＝<V，E>，V 与V以及相应边的结点对中有一一对应关系。
§12.1.4 图中结点的次数
（4）图中结点的次数
• 生成树寻找算法：在G中寻找基本回路，寻到后删除边， 并继续寻找，直到无基本回路出现为止。
§14.2 两分图
（21）两分图的概念：无向图G＝<V , E>，有V1， V2V，V1∩V2＝，G中每一边e都有：e＝（vi，vj）， viV1，vjV2，则称G为两分图。
（22）两分图的判别法：
图的所有回路长度为偶数。
• 引入次数deg（v） 、引出次数deg（v）、
次数deg（v）。
• 定理：n i 1
deg（vi）= 2m
§12.2 通路、回路与连通性
（5）通路与回路 ① 通路：图中vi至vj的通路是在边的序列：（vi，vi1），
（vi1，vi 2），…（vi k－1，vi k），其中vi k＝vj ② 基本通路与简单通路：图各边全不同的通路叫简单
哈密尔顿图的充分条件：G＝<V , E>无向简单图，|V|≥3，G 中每结点对次数之和≥|V|。 哈密尔顿通路：有向图D＝<V , E>，|V|≥2所有有向边均用无向 边替代后得无向图含生成子图Kn。
第十四章 特殊图
§14.1 树 §14.1.1 树的基本性质 （13）树的基本概念与属性
① 树：不含回路的连通图。 （n , m）树中必有m＝n－1
§14.1.3 二元树
（16）二元树与多元树：一个n个结点的外向树：（vi）≤m （i = 1 , 2 , …, n），称m元树。如（vi）＝m（i = 1 , 2 , …, n）（除叶外），称m元完全树，当m＝2时称二元树或 二元完全树。
§14.1.4 生成树
（17）生成树：连通图G＝<V , E>的生成树TG＝<V , E>G 的子图，且是树并满足V＝V，EE。
第十三章 欧拉图与哈密尔顿图
§13.1 欧拉图 （7）欧拉图
• 欧拉回路与欧拉通路：通过G中每边一 次的回（通）路称欧拉回（通）路，具此回路的图 称欧拉图。
③ 欧拉图与欧拉通路：欧拉图每个结点 次数为偶数。
由vi到vj欧拉通路vi，vj结点次数为奇数， 其它结点次数为偶数。
§13.2 哈密尔顿图
（20）平面图的判别法（库拉托夫斯基定理）： 图的任何子图都不可能减缩成下面两个图：
§14.3 平面图
§14.3.1 平面图的基本概念
（18）平面图的概念：图的边间可不出现交叉称为平面图。
§14.3.2 平面图区域
（n，m）连通平面图，区域数为r，必有：n－m＋r＝2。
（19）平面图区域性质
（n，m）连通平面图，且无环，边大于1，必有：m≤3n－6。
§14.3.3 判别平面图的库拉托夫斯基定理