发布时间 : 星期二 文章图的基本概念更新完毕开始阅读5d9aa27002768e9951e7389e
第一章 图的基本概念
第一节 图和有向图
定义1.1 一个无向图图（graph）G是指一个二元组(V,E)，其中集合V中的元素称为顶点（或点,或端点, 或结点）（or vertice, or node, or point), 集合E中元素为V中元素组成的无序对，称为边 (edge).
注意：1. 上述集合E中的元素可以相同，有的文献称这样的集合为多重集。 2. 图(?,?)称为空图，它有时在举反例的时候用到，且有时将一个结论推广到包含空图时会引起不必要的麻烦, 故本书中假设所讨论的图都不是空图。
3. 在一个图G?(V,E)中，为了表示V和E分别是G顶点集合边集，常将V和E分别记为V(G)和E(G).
我们经常用图形来表示一个图。用小圆圈或实心点表示图的顶点，用线段把无序对中两个顶点连接起来表示边。其中顶点的位置，连线的曲直、是否相交等都无关紧要. 例如，
G?(V,E)，V=?v1,v2,v3,v4,v5?，G??(v1,v1),(v1,v2),(v1,v2),(v1,v3),(v2,v4),(v4,v5)?，
G的图形如下.
e2 v5 v1 v2 e1 图. 1.
设G?(V,E). 若V为有限集，则称G为有限图（finite graph）；若V为单点集，则称G为平凡图 (trivial graph ). 为方便起见，常用ei表示边，例如在图1中e2表示边(v1,v3), 而v1,v3称为e2的端点. 两个顶点相同的边称为环 (loop), 具有相同顶点的多条边称为重边 (multiple edge), 不含环和重边的图称为简单图 (simple graph). 例如在图1中e1为环, e2,e3为重边，所以此图不是简单图.
定义1.2 设图G的顶点集为V(G)??v1,v2,...,vn?，边集为E(G)??e1,e2,...,em?.G的邻接矩阵（adjacency matrix）A(G)是一个n?n矩阵，元素ai,j为端点的边的数目。G的
v3 v4
关联矩阵（incidence matrix）M(G)是一个n?m矩阵，元素mi,j为1，当vi是ej的端点. 否则，元素mi,j为0. 顶点v的度（degree）是其作为边的端点的个数, 记为d(v). 例1.3 图1的邻接矩阵和关联矩阵分别如下:
??? ????????? ????
注意：邻接矩阵由顶点的顺序决定. 任意邻接矩阵都是对称的. 邻接矩阵法是将一个图储存于计算机的方法之一. 在关联矩阵或邻接矩阵中，将某顶点对应的行的元素求和，就得到该顶点度数. 关于顶点度数，我们有下面的基本定理.
定理1.4 设图G的顶点集为V(G)??v1,v2,...,vn?，边集为E=m, 则
?d(v)= 2m.
ii?1n 推论 图中度为奇数的顶点个数为偶数.
我们称一个图的所有顶点度数的非递增序列为这个图的度序列. 例如图1的度序列为（4,3,2,2,1）. 每个图都有一个度序列，反之，并非每个非递增序列都为度序列，例如（5,4,3,2,1）就不可能是某个图的度序列，因为定理1.4告诉我们，一个非递增序列要成为某个图的度序列，必须先满足序列的元素和为偶数. 其实，这个显然的必要条件也是充分的. 定理1.5 非负整数d1,d2,...,dn是某个图的所有顶点度数当且仅当 证明 ? 显然.
? 设V??v1,v2,...,vn?. 显然集合?vi: di是奇数的元素个数为偶数. 将此集合中元素两两配对，对每个元素对，构造一条边使其端点为元素对. 则此时每个顶点vi需要的度数是偶数（非负），在vi处加上?di/2?个环，就得到以V为顶点集的图，且vi的度为di.
定理1.5的证明是构造性的，当然可以用其它方法来证明，例如用归纳法（对n或 ，证明留给读者. 定理1.5中对度序列的刻画比较简单是因为允许使用环.?d进行归纳）
i?di是偶数.
?如果不允许使用环，
?d是偶数的条件就不充分了. 我们在习题中给出无环图度序列的刻
i画. 关于简单图度序列的刻画以及更多关于度序列的内容参考[1] .
定义1.6 图G中顶点和边的交替序列?=v0e1v1e2...envn称为一条(v0,vn)-通道
((v0,vn)-walk), 如果vi?1和vi是ei的端点. v0和vn分别称为通道?的起点(origin)和终点
(terminus)，其它顶点称为内点. ?中边的数目n称为通道的长度. 若起点和终点相同，称此通道是闭的. 如果?中的边互不相同，则称?为一条迹（tail）; 如果?中的顶点互不相同，则称?为一条路径（path）. 起点和内点互不相同的闭通道称为圈（cycle). 若对于图中任意两个顶点vi和vj，都存在一条(vi,vj)-通道，则称此图是连通的（connected）. 在图2中， 为通道， 为闭迹， 为路径
'''''' 定义1.7 设G?(V,E)，G?(V,E)是两个图. 若V?V,E?E, 则称G是G的子图（subgraph). 若G是G的子图且V?V, 则称G是G的生成子图（spanning subgraph). 设V1?V, 以 V1为顶点集, 以两端点全在V1中的全体边为边集的G的子图称为G的导出子图(induced subgraph), 记为G[V1]. 在图3中，
定义1.8 图G的连通分支(connected component) 是指其最大连通子图. 图G的割点(cutvertex) (割边 (cut-edge or bridge))是指一个顶点（一条边）且删除它会增加连通分支的数目. 我们用G?v(G?e)来表示删除点v(边e)所得到的子图. 在图4中，
'''
下面来刻画割边.
定理1.9 一条边是割边当且仅当它不属于任何一个圈.
证明: 设e?E(G),不妨设G是连通的（为什么?）.
? 若e位于某个圈中, 则不难证明E?e连通，这与e是割边矛盾，故e不属于任何一个圈.
? 若e不是割边, 则E?e连通. 设e的两个顶点分别为v1,v2. 由于E?e连通.连通，故E?e中存在一条(v1,v2)-路径，这条路径加上e就构成了一个圈.
定义1.10 一个有向图（digraph）D是指一个二元组(V,E)，其中集合V中的元素称为顶点（或点,或端点, 或结点), 集合E中元素为V中元素组成的有序对，称为边或有向边.
有向图也可以用图形表示. 例如：
但要注意有向图中边(a,b)是有方向的，箭头必须从a指向b. 有些概念对有向图或无向图都适用; 有些概念对有向图和无向图而言是有差异的. 在习题中我们给出有向图中一些基本概念的定义.
习 题
1. 证明：一条(u,v)-通道都包含一条(u,v)-路径.
2. (1) 如果简单图G的每个顶点的度数为2，G一定是圈吗？
(2) 证明：如果图G中每一个点的度至少是2，则G含有一个圈. 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. 证明：含有n个顶点和k条边的图至少有n?k个连通分支.
5. 证明：如果一个图的所有顶点的度都为偶数(这样的图称为偶图)，则此图没有割边.