图的基本概念

《图的基本概念》由会员分享，可在线阅读，更多相关《图的基本概念（11页珍藏版）》请在金锄头文库上搜索。

1、第一章第一章 图的基本概念图的基本概念第一节第一节 图和有向图图和有向图定义定义 1.1 一个无向图图（graph）是指一个二元组，其中集合中的元素G),(EVV称为顶点（或点,或端点, 或结点） （or vertice, or node, or point), 集合中元素为中元素EV 组成的无序对，称为边 (edge). 注意：1. 上述集合中的元素可以相同，有的文献称这样的集合为多重集。E2. 图称为空图，它有时在举反例的时候用到，且有时将一个结论推广到包),(含空图时会引起不必要的麻烦, 故本书中假设所讨论的图都不是空图。3. 在一个图中，为了表示和分别是顶点集合边集，常将和G),(EV

2、VEGV分别记为和.E)(GV)(GE我们经常用图形来表示一个图。用小圆圈或实心点表示图的顶点，用线段把无序对 中两个顶点连接起来表示边。其中顶点的位置，连线的曲直、是否相交等都无关紧要. 例如，=，G),(EVV54321,vvvvvG，的图形如下. ),(),(),(),(),(),(544231212111vvvvvvvvvvvvG3v4ve 25v1v2v1e图. 1.设. 若为有限集，则称为有限图（finite graph） ；若为单点集，G),(EVVGV则称为平凡图 (trivial graph ). 为方便起见，常用 e 表示边，例如在图 1 中表示边Gi2e, 而,称为的端点

3、. 两个顶点相同的边称为环 (loop), 具有相同顶点的多条边),(31vv1v3v2e称为重边 (multiple edge), 不含环和重边的图称为简单图 (simple graph). 例如在图 1 中为1e环, 为重边，所以此图不是简单图. 32,ee定义定义 1.2 设图的顶点集为，边集为.G)(GVnvvv,.,21)(GEmeee,.,21的邻接矩阵（adjacency matrix）是一个矩阵，元素为端点的边的数目。G)(GAnnjia,的关联矩阵（incidence matrix）是一个矩阵，元素为 1，当是的G)(GMmnjim,ivje端点. 否则，元素为 0. 顶点的

4、度（degree）是其作为边的端点的个数, 记为.jim,v)(vd例例 1.3 图 1 的邻接矩阵和关联矩阵分别如下:注意：邻接矩阵由顶点的顺序决定. 任意邻接矩阵都是对称的. 邻接矩阵法是将一个 图储存于计算机的方法之一. 在关联矩阵或邻接矩阵中，将某顶点对应的行的元素求和， 就得到该顶点度数. 关于顶点度数，我们有下面的基本定理. 定理定理 1.4 设图的顶点集为，边集为=, 则G)(GVnvvv,.,21Em= niivd1)(.2m推论推论 图中度为奇数的顶点个数为偶数. 我们称一个图的所有顶点度数的非递增序列为这个图的度序列. 例如图 1 的度序列为 （4,3,2,2,1）. 每个

5、图都有一个度序列，反之，并非每个非递增序列都为度序列，例如 （5,4,3,2,1）就不可能是某个图的度序列，因为定理 1.4 告诉我们，一个非递增序列要成为 某个图的度序列，必须先满足序列的元素和为偶数. 其实，这个显然的必要条件也是充分 的.定理定理 1.5 非负整数,.,是某个图的所有顶点度数当且仅当是偶数.1d2dndid证明证明 显然. 设. 显然集合: 是奇的元素个数为偶数. 将此nvvvV,.,21ivid数集合中元素两两配对，对每个元素对，构造一条边使其端点为元素对. 则此时每个顶点需要的度数是偶数（非负） ，在处加上个环，就得到以为顶点集的图，且iviv2/idV的度为.ivi

6、d定理 1.5 的证明是构造性的，当然可以用其它方法来证明，例如用归纳法（对或 n进行归纳） ，证明留给读者. 定理 1.5 中对度序列的刻画比较简单是因为允许使用环.id如果不允许使用环，是偶数的条件就不充分了. 我们在习题中给出无环图度序列的刻id画. 关于简单图度序列的刻画以及更多关于度序列的内容参考1 .定义定义 1.6 图中顶点和边的交替序列=称为一条-通道Gnnveevev.2110),(0nvv(-walk , 如果和是的端点. 和分别称为通道的起点(origin)和终点),(0nvv)1ivivie0vnv(terminus)，其它顶点称为内点. 中边的数目称为通道的长度. 若

7、起点和终点相同，称此n 通道是闭的. 如果中的边互不相同，则称为一条迹（tail）; 如果中的顶点互不相同， 则称为一条路径（path）. 起点和内点互不相同的闭通道称为圈（cycle). 若对于图中任意两个顶点和，都存在一条-通道，则称此图是连通的（connected）.ivjv),(jivv在图 2 中， 为通道， 为闭迹， 为路径定义定义 1.7 设，是两个图. 若, 则称是G),(EV),(EVG VV EE G的子图（subgraph). 若是的子图且, 则称是的生成子图（spanning GGGVV GGsubgraph). 设, 以 为顶点集, 以两端点全在中的全体边为边集的的子

8、图称1VV1V1VG为的导出子图(induced subgraph), 记为.G1VG在图 3 中，定义定义 1.8 图的连通分支(connected component) 是指其最大连通子图. 图的割点GG (cutvertex) (割边 (cut-edge or bridge)是指一个顶点（一条边）且删除它会增加连通分支的数目. 我们用来表示删除点边所得到的子图.vG )(eG v() e在图 4 中，下面来刻画割边. 定理定理 1.9 一条边是割边当且仅当它不属于任何一个圈.证明证明: 设,不妨设是连通的（为什么?）.e)(GEG若位于某个圈中, 则不难证明连通，这与是割边矛盾，故不属于

9、eeE ee 任何一个圈.若不是割边, 则连通. 设的两个顶点分别为. 由于连通.eeE e21,vveE 连通，故中存在一条()-路径，这条路径加上就构成了一个圈.eE 21,vve定义定义 1.10 一个有向图（digraph）是指一个二元组，其中集合中的元素称D),(EVV为顶点（或点,或端点, 或结点), 集合中元素为中元素组成的有序对，称为边或有向边. EV有向图也可以用图形表示. 例如：但要注意有向图中边是有方向的，箭头必须从指向. 有些概念对有向图或无向图),(baab都适用; 有些概念对有向图和无向图而言是有差异的. 在习题中我们给出有向图中一些基本 概念的定义.习习 题题1.

10、 证明：一条-通道都包含一条-路径.),(vu),(vu2. (1) 如果简单图的每个顶点的度数为 2，一定是圈吗？GG(2) 证明：如果图中每一个点的度至少是 2，则含有一个圈.GG3. 给定下列各序列：（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. 对于含有个顶点的简单图，

11、如果任意两个顶点都有边相连(即每个顶点的度为n)，则称此图为完全图完全图(complete graph), 记为. 确定是否包含以下情况(给出例子1nnK4K或证明不包含).(1) 一个不是迹的通道.(2) 一个不是路径的闭迹.(3). 一个不是圈的闭迹.7. 对于图和，如果存在两个双射：和使GH)()(HVGV)()(:HEGE得对于任意的, 是的两个端点, 则称和同构)(),(GEuve)(),(vu)(eGH(isomorphism), 记为. 一个简单图的补图（complement）也是一个简单图，其HG GcG顶点集为, 且.)(GV)(),()(),(GEvuGEvuc(1) 证明

12、：（4 个顶点的路径）和其补图同构. 像这样和其补图同构的图称为自补4P的 (self-complementary).(2) 证明：.ccHGHG(3) 证明简单图集合的同构关系时一种等价关系.(4) 按同构关系给下面 4 个图分类.第第 2 节节 树的性质树的性质本节和下一节学习图论中最有用的概念之一树. 作为图，树在数据存储、查询， 通信，电网分析，化学等方面有着重要应用.定义定义 2.1 一个森林（forest ）是指一个无圈图. 一棵树（tree）是指一个连通的森林. 度为 1 的顶点称为叶子（leaf）. 若果一个图的生成子图是一棵树，则称该树是图的生成树 (spanning tre

13、e).例例 2.2 给一所大学的所有学生编排学号，形成一颗树. 以 0 表示学校，以 01, 02, 03,. 表示学院, 以 01, 02, 03.表示各个学院的班级，以 001, 002, 003,.表示各班级的学生这一结果如下图所示，注意树中的叶子表示一个学生.下面给出树的定价刻画.定理定理 2.3 对于个顶点的图，下面命题等价:nG（1）是连通的且无圈.G(2) , 中只有一条-路径且无环.)(,GVvuG),(vuG（3）有条边且无圈.G1n（4）是连通的且有条边.G1n证明证明：（1）（2）. 由于是连通的，故, 中有一条-路G)(,GVvuG),(vu径. 若中还有一条不同的-路

14、径，则不难证明中有圈 (证明留作练习) ，与中G),(vuGG无圈矛盾，所以中只有一条-路径. 无圈推出无环.G),(vu（2）（3）. 上面证明已经指出：, 若中只有一条-路)(,GVvuG),(vu径，则中无圈. 下面用归纳法证明有条边. 如果，结论是显然的 (由于GG1n1n无环)，下设对于顶点数小于()的图命题成立. 对于中任意一条边，在Gn2nG),(vu图中删除此边得到图. 由于中只有一条-路径，故不连通. 不难证明 有GHG),(vuHH两个连通分支且无圈，设这两个连通分支分别为和. 由（1）（2）知这两个连通1H2H分支中任意两顶点间只有一条路径，又由于和的顶点数都小于，由归纳

15、假设知1H2Hn(其中分别表示的边和顶点数，). 又1iineiine ,iH2 , 1i+=+1+1=+1, 证毕. n1n2n1e2ee（3）（4）. 设使的连通分支. 由 (1) (2) (3)知，对每个kHHH.,21G连通分支都有 (其中分别表示的边和顶点数, ) . 故iH1iineiine ,iHki,.,2 , 1，即.kiiie1kiiin1kkne由于，故，即连通.1 ne1kG（4）（1）. 若中有圈，则从各个圈中删除边. 直到中无圈. 又因为删除GG 圈中的边不会破坏连通性 (也即圈中的边一定不是割边，见定理 1.9)，故最后得到的图是连通的无圈图且顶点数为. 由于(1) (2) (3)，故有条边. 所以GnG1n且是无圈的.GG我们在习题中给出树的其它的定价刻画，下面给出关于生成树的一个结果.定理定理 2.4. 是连通的当且仅当它有生成树.G充分性是显然的，必要性的证明类似于定理 2.3 证明中的（4）（1） ，故我们略去. 注意定理 2.4 给出了确定图是否连通的方法，我们将