图的基本概念

第一章 图的基本概念第一节 图和有向图定义 1.1 一个无向图图（ graph） 是指一个二元组 ，其中集合 中的元素G),(EVV称为顶点（或点,或端点, 或结点） （or vertice, or node, or point), 集合 中元素为 中元素组成的无序对，称为边 (edge). 注意：1. 上述集合 中的元素可以相同，有的文献称这样的集合为多重集E2. 图 称为空图，它有时在举反例的时候用到，且有时将一个结论推广到包),(含空图时会引起不必要的麻烦, 故本书中假设所讨论的图都不是空图3. 在一个图 中，为了表示 和 分别是 顶点集合边集，常将 和G),(VVEGV分别记为 和 .E)(E我们经常用图形来表示一个图用小圆圈或实心点表示图的顶点，用线段把无序对中两个顶点连接起来表示边其中顶点的位置，连线的曲直、是否相交等都无关紧要. 例如， ， = ，G),(V54321,,vG， 的图形如下. ),()(,21vv3 4ve 25v1 2v1e图. 1.设 . 若 为有限集，则称 为有限图（finite graph） ；若 为单点集，G),(EVGV则称 为平凡图 (trivial graph ). 为方便起见，常用 e 表示边，例如在图 1 中 表示边i 2e, 而 , 称为 的端点. 两个顶点相同的边称为环 (loop), 具有相同顶点的多条边)(31v132e称为重边 (multiple edge), 不含环和重边的图称为简单图 (simple graph). 例如在图 1 中 为e环, 为重边，所以此图不是简单图 . 32e定义 1.2 设图 的顶点集为 ，边集为 .G)(Vnv,.21 )(GEme,21的邻接矩阵（adjacency matrix） 是一个 矩阵，元素 为端点的边的数目。

G)(GAnjia,的关联矩阵（incidence matrix） 是一个 矩阵，元素 为 1，当 是 的Mmji,ivje端点. 否则，元素 为 0. 顶点 的度（degree）是其作为边的端点的个数, 记为 .jim, v )(d例 1.3 图 1 的邻接矩阵和关联矩阵分别如下:注意：邻接矩阵由顶点的顺序决定. 任意邻接矩阵都是对称的. 邻接矩阵法是将一个图储存于计算机的方法之一. 在关联矩阵或邻接矩阵中，将某顶点对应的行的元素求和，就得到该顶点度数. 关于顶点度数，我们有下面的基本定理. 定理 1.4 设图 的顶点集为 ，边集为 = , 则G)(Vnv,.21Em= niivd1.m推论 图中度为奇数的顶点个数为偶数. 我们称一个图的所有顶点度数的非递增序列为这个图的度序列. 例如图 1 的度序列为（4,3,2,2,1）. 每个图都有一个度序列，反之，并非每个非递增序列都为度序列，例如（5,4,3,2,1）就不可能是某个图的度序列，因为定理 1.4 告诉我们，一个非递增序列要成为某个图的度序列，必须先满足序列的元素和为偶数. 其实，这个显然的必要条件也是充分的.定理 1.5 非负整数 , ,..., 是某个图的所有顶点度数当且仅当 是偶数.1d2n id证明 显然. 设 . 显然集合 : 是奇 的元素个数为偶数. 将此nvV,21ivid数集合中元素两两配对，对每个元素对，构造一条边使其端点为元素对. 则此时每个顶点需要的度数是偶数（非负） ，在 处加上 个环，就得到以 为顶点集的图，且ivi2/i V的度为 .iid定理 1.5 的证明是构造性的，当然可以用其它方法来证明，例如用归纳法（对 或 n进行归纳） ，证明留给读者. 定理 1.5 中对度序列的刻画比较简单是因为允许使用环.i如果不允许使用环， 是偶数的条件就不充分了. 我们在习题中给出无环图度序列的刻id画. 关于简单图度序列的刻画以及更多关于度序列的内容参考[1] .定义 1.6 图 中顶点和边的交替序列 = 称为一条 -通道Gnve.210 ),(0nv(-walk , 如果 和 是 的端点. 和 分别称为通道 的起点(origin)和终点),(0nv1iviievn(terminus)，其它顶点称为内点. 中边的数目 称为通道的长度. 若起点和终点相同，称此通道是闭的. 如果 中的边互不相同，则称 为一条迹（ tail）; 如果 中的顶点互不相同，则称 为一条路径（path ）. 起点和内点互不相同的闭通道称为圈（cycle). 若对于图中任意两个顶点 和 ，都存在一条 -通道，则称此图是连通的（connected ）.ivj ),(jiv在图 2 中， 为通道， 为闭迹， 为路径定义 1.7 设 ， 是两个图. 若 , , 则称 是G),(EV),(''' V' E' 'G的子图（subgraph). 若 是 的子图且 , 则称 是 的生成子图（spanning ' V' 'Gsubgraph). 设 , 以 为顶点集, 以两端点全在 中的全体边为边集的 的子图称11 1为 的导出子图(induced subgraph), 记为 .G][1在图 3 中，定义 1.8 图 的连通分支(connected component) 是指其最大连通子图. 图 的割点G G(cutvertex) (割边 (cut-edge or bridge))是指一个顶点（一条边）且删除它会增加连通分支的数目. 我们用 来表示删除点 边 所得到的子图 .v)ev()e在图 4 中， 下面来刻画割边.定理 1.9 一条边是割边当且仅当它不属于任何一个圈.证明: 设 ,不妨设 是连通的（为什么?）.e)(GE若 位于某个圈中 , 则不难证明 连通，这与 是割边矛盾，故 不属于eEee任何一个圈.若 不是割边, 则 连通. 设 的两个顶点分别为 . 由于 连通.ee21,vE连通，故 中存在一条( )-路径，这条路径加上 就构成了一个圈.E21,ve定义 1.10 一个有向图（digraph） 是指一个二元组 ，其中集合 中的元素称D),(EVV为顶点（或点,或端点, 或结点), 集合 中元素为 中元素组成的有序对，称为边或有向边. E有向图也可以用图形表示. 例如：但要注意有向图中边 是有方向的，箭头必须从 指向 . 有些概念对有向图或无向图),(baab都适用; 有些概念对有向图和无向图而言是有差异的. 在习题中我们给出有向图中一些基本概念的定义.习 题1. 证明：一条 -通道都包含一条 -路径.),(vu),(vu2. (1) 如果简单图 的每个顶点的度数为 2， 一定是圈吗？GG(2) 证明：如果图 中每一个点的度至少是 2，则 含有一个圈.3. 给定下列各序列：（1） （2,2,2,2,2） ；（2） （3,2,2,1,1） ；（3） （2,2,2,1,1） ； （4） （3,3,3,1,0） ； （5） （5,4,4,3,1）.以上五组数中，那几组数可以构成简单图的度数序列?4. 证明：含有 个顶点和 条边的图至少有 个连通分支.nkkn5. 证明：如果一个图的所有顶点的度都为偶数(这样的图称为偶图) ，则此图没有割边.6. 对于含有 个顶点的简单图，如果任意两个顶点都有边相连( 即每个顶点的度为)，则称此图为完全图(complete graph), 记为 . 确定 是否包含以下情况(给出例子1n nK4或证明不包含).(1) 一个不是迹的通道.(2) 一个不是路径的闭迹.(3). 一个不是圈的闭迹.7. 对于图 和 ，如果存在两个双射 ： 和 使GH)()HVG)():HEG得对于任意的 , 是 的两个端点, 则称 和 同构)(,(Euve(),vue(isomorphism), 记为 . 一个简单图 的补图（complement） 也是一个简单图，其c顶点集为 , 且 .)(GV)(,()GEvvc(1) 证明： （4 个顶点的路径）和其补图同构. 像这样和其补图同构的图称为自补P的 (self-complementary).(2) 证明： .cH(3) 证明简单图集合的同构关系时一种等价关系.(4) 按同构关系给下面 4 个图分类. 第 2 节 树的性质本节和下一节学习图论中最有用的概念之一——树. 作为图，树在数据存储、查询，通信，电网分析，化学等方面有着重要应用.定义 2.1 一个森林（forest ）是指一个无圈图. 一棵树（tree ）是指一个连通的森林. 度为 1 的顶点称为叶子（leaf）. 若果一个图的生成子图是一棵树，则称该树是图的生成树 (spanning tree).例 2.2 给一所大学的所有学生编排学号，形成一颗树. 以 0 表示学校，以 01, 02, 03,.... 表示学院, 以 01, 02, 03...表示各个学院的班级，以 001, 002, 003,....表示各班级的学生 这一结果如下图所示，注意树中的叶子表示一个学生.下面给出树的定价刻画.定理 2.3 对于 个顶点的图 ，下面命题等价:nG（1） 是连通的且无圈.G(2) , 中只有一条 -路径且 无环.)(,Vvu),(vuG（3） 有 条边且无圈.1（4） 是连通的且有 条边.n证明：（1） （2）. 由于 是连通的，故 , 中有一条 -路)(,Vv),(vu径. 若 中还有一条不同的 -路径，则不难证明 中有圈 (证明留作练习) ，与 中G),(vuGG无圈矛盾，所以 中只有一条 -路径. 无圈推出无环.（2） （3）. 上面证明已经指出： , 若 中只有一条 -路)(,Vvu),(vu径，则 中无圈. 下面用归纳法证明 有 条边. 如果 ，结论是显然的 (由于1n1n无环)，下设对于顶点数小于 ( )的图命题成立. 对于 中任意一条边 ，在Gn2G),(vu图 中删除此边得到图 . 由于 中只有一条 -路径，故 不连通. 不难证明 有HG),(vuHH两个连通分支且无圈，设这两个连通分支分别为 和 . 由（1） （2）知这两个连通12分支中任意两顶点间只有一条路径，又由于 和 的顶点数都小于 ，由归纳假设知n(其中 分别表示 的边和顶点数， ). 又1iineine,iH,i+ = + +1+1= +1, 证毕. 2e（3） （4）. 设 使 的连通分支. 由 (1) (2) (3)知，对每个k,21G连通分支 都有 (其中 分别表示 的边和顶点数, ) . 故iHiineineiHki,21，即 .ki1ki1kne由于 ，故 ，即 连通.1e（4） （1）. 若 中有圈，则从各个圈中删除边. 直到 中无圈. 又因为删除GG圈中的边不会破坏连通性 (也即圈中的边一定不是割边，见定理 1.9)，故最后得到的图是连通的无圈图且顶点数为 . 由于(1) (2) (3)，故 有 条边. 所以Gn1n且是无圈的 .我们在习题中给出树的其它的定价刻画，下面给出关于生成树的一个结果.定理 2.4. 是连通的当且仅当它有生成树.充分性是显然的，必要性的证明类似于定理 2.3 证明中的（4） （1） ，故我们略去. 注意定理 2.4 给出了确定图 是否连通的方法，我们将在下一节讨论检测 是否有一个生GG成树的算法. 我们下面讨论树在计算机学科的一些应用，先给出根树的定义.每一颗树都可以按下面的方式画出来 (例如图 ). 每一个顶点都有层次 (level)0, 1, 2,..., k. 存在的唯。