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