(3) 若V?V,E?E，则称G是G的生成子图。 注：每个图都是自己的子图。
完全图：设图G?(V,E)是一个简单图，若V中任意两个不同的结点间都有边关
联，则称该图是一个完全图。
2注：一个完全(n,m)图，则m?Cn。
补图：图G的补图是由G的所有结点和为了使G成为完全图所需要添加的那些
边所组成的图，用G表示。
正则图：若图G的所有结点都具有同一度d，则称该图为d次正则图。 路：图G中l条边的序列{vi0,vi1},{vi1,vi2},路。
开路：若vi0?vil，则称该路为开路。 回路：若vi0?vil，则称该路为回路。 真路：若vi0,vi1,环：若vi0,vi1,接的。
连通：在图G中，任意两个结点均是连接的，则称图G是连通的，否则是不连
通的。
短程：在图G中，从结点vi到vj若由一条或者更多的路相连接，则其中必有长度
最短的路，称其为从vi到vj的短程。
距离：从vi到vj的短程的长度称为vi和vj间的距离，用d(vi,vj)表示。
,{vil?1,vil}称为连接vi0到vil的长度为l的
,vil各不相同，则称该路为真路。 ,vil各不相同，则称回路为环。
连接：在图G中，若存在一条路连接vi和vj，则称该图中的两个结点vi与vj是连
典型题解：
例1 证明在n个顶点的简单无向图G中，至少有两个结点的度相同，这里n?2。 证明：分三种情况讨论。
(1) G中无孤立点，则每个结点的度大于等于1，又由简单图的性质知每个结
点的度小于等于n?1，所以每个结点的度都属于集合{1,2,,n?1}，这是
在只有n?1个元素的集合中取n个元素，所以至少有两个结点的度相同。 (2) G中只有一个孤立点，则除孤立点外，每个结点的度大于等于1，又由简
单图的性质知每个非孤立点的度小于等于2，所以n?1个结点的度均属于集合{1,2,,n?2}，这是在只有n?2个元素的集合中取n?1个元素，所以
至少有两个结点的度相同。
(3) G中至少2个孤立点，则2个孤立点的度相同。
26
例2 下列各组数中，哪些能构成无向图的度数序列？哪些能构成无向简单图度
数序列？
(1) {1,1,1,2,3}；(2) {6,5,4,4,3,2,1}；(3){1,2,3,4,5}；(4){1,3,3,3}
解：非负整数序列能构成无向图的度数序列的充分必要条件是该序列之和为偶数。上述序列中(2)(3)中均有3个奇数，所以不能构成无向图的度数序列；(1)(4)能构成无向图的度数序列。(1)对应一个无向简单图，而(4)不能构成无向简单图的度数序列，因为若对应简单无向图G，设v1,v2,v3,v4是该图的4个结点，不妨设deg(v1)?1,deg(v2)?3,deg(v3)?3,deg(v4)?3，则结点v1仅仅能与v2,v3,v4之一相邻，不妨设与v2相邻，则除了v2能达到度数3外，其它两个点都达不到度数3，至多为2，因此矛盾，所以(4)不能构成无向简单图。
例3 考察下面图(a)和图(b)是否同构？
(a)
得到如下图：
(a) (b)
在图(a)中结点a,b相邻，而a?,b?不相邻，所以图(a)和图(b)不同构。
例4 求出下图的补图：
解：根据补图的定义，得补图如下：
27
(b)
解：图(a)和图(b)中都恰好有两个度为3的结点，分别将它们标记为a,b和a?,b?，
例5 下列各无向图中有几个结点？
(1)21条边，3个4度数结点，其余都是3度数的结点； (2) 12条边，各结点的度数相同。
解：设图中结点个数为n，根据握手定理： (1)
n?3?deg(v)?4?n?3?(n?n)?4?3?3?(n?3)?3n?3?42i11i?1n，所以
9?/。
(2) 设各结点的度数为k，则?deg(vi)?k?n?2m?2?12?24
1)若k?1，则n?24；2) 若k?2，则n?12；3)若k?3，则n?8；4)若k?4，则n?6；5)若k?4，则n?4；6)若k?8，则n?3。
例6 证明在9个工厂之间，不可能每个工厂只与其他3格工厂有业务联系，也不可能只有4个工厂与偶数个工厂有业务联系。
证明：将9个工厂看作9个结点，两个工厂有业务联系时看成对应两结点之间有边。
(1) 假设每个工厂只与其他3个工厂业务有联系，则每个结点的度数为3，所有结点的度数之和为27，这与结点度数之总和为偶数(边数的 2倍)矛盾，所以不可能每个工厂只与其他3个工厂有业务联系。
(2) 假设只有4个工厂均与偶数个工厂有业务联系，其他5个工厂均与奇数个工厂有业务联系，则4个偶数之和是偶数，5个奇数之和是奇数，从而9格结点的度数之和为奇数。这也与结点度数之总和为偶数相矛盾，所以不可能只有4格工厂与偶数个工厂有业务联系。
例7 设G为n阶简单无向图，n?2且n为奇数，G和G的补图G中度数为奇数的结点个数是否一定相等？证明你的结论！
解：一定相等。因为n?2且为奇数，对于奇数个结点的无向完全图，每个结点的度数必为偶数。若G的奇结点有k个，则对应补图G在这k个结点的度数必为奇数(偶数-奇数=奇数)；而对于G的偶结点，其在补图G中仍为偶结点(偶数-偶
28
i?1n数=偶数)，所以G和G的补图G中度数为奇数的结点个数是一定相等。 例8 已知n阶无向简单图G有m条边，各结点的度数均为3。 (1) 若m?3n?6，证明G在同构的意义下唯一，并求m,n； (2) 若n?6，证明G在同构的意义下不唯一。
证明：(1)由于各顶点的度数均为3，现有n个结点，m条边，所以 故n?2。 3m?degv(ii?1n 2?)?3n?m又m?3n?6?3?2，故m?6，则n?4。 3m?6?2m?6此时所得的无向图如下图(a)所示，该图为4个结点的无向完全图，对于4个结点的完全图，在同构意义下唯一。
(a) (2) 若n?6，有?deg(vi)?3?6?18?2m 故m?18/2?9。
i?1n此时有n?6,m?9，且每个结点的度数为3，对于无向简单图，6个结点，9条边及每个结点度数为3的图如图(b)(c)所示，这两个图是非同构的。所以n?6,m?9，结点度数全为3的图在同构的意义下不唯一。
(b) (c)
8.2 图的矩阵表示
8.2.1 基本知识点：
基本概念：邻接矩阵，关联矩阵，邻接向量矩阵，连接矩阵，布尔矩阵，布尔矩
阵运算。
基本理论：邻接矩阵、关联矩阵与结点度数的关系；邻接矩阵的乘幂与任意两结
点间路的条数的关系；图的连通性与连接矩阵的关系。
基本计算：求图的邻接矩阵和关联矩阵；利用邻接矩阵求结点的度；利用邻接矩
29
阵的幂判断任意两结点间不同长度的路的条数；求矩阵的连接矩阵；利用连接矩阵判断无向图的连通性。
8.2.2 重点与难点
邻接矩阵：设G?(V,E)，其中V?{v1,v2,矩阵，其中元素
,vn}，n阶方阵A?(aij)称为G的邻接
?1若{vi,vj}?Eaij??否则?0,vn}，m条边e1,e2,,em，则关联矩
关联矩阵：设G?(V,E)，其中V?{v1,v2,阵I?(bij)是一个n?m的矩阵，其中元素
?1若vi和ej是关联的bij?? 否则?0
连接矩阵：设G?(V,E)，其中V?{v1,v2,矩阵，其中元素
,vn}，n阶方阵C?(cij)称为G的连接
?1若vi到vj存在一条路cij??否则?0布尔矩阵和布尔运算：如果一个矩阵的所有元素均为0或1，则称这种矩阵为布
尔矩阵；对于布尔矩阵来说，若矩阵运算中元素的相加与相乘均规定为布尔加与布尔乘，则这种矩阵运算称为布尔矩阵运算。
求图的连接矩阵的两种方法：
(1) 利用邻接矩阵：若图G?(V,E)，#(V)?n，则Bn?A?A2??An，其中矩
阵Bn的(i,j)项元素bij给出连接vi和vj的长度小于或等于n的路的总和，若这个数不为0，则结点vi和vj是连接的；如果这个元素为零，则结点vi和vj非连接；若Bn每个元素都不为0，则判断图G是连通的，否则G不是连通的图。 (2) 利用布尔矩阵运算：C?A[?]A(2)[?][?]A(n)。对于任意的正整数l，当且仅
(l)当存在有连接vi到vj的长为l的路时，A(l)的(i,j)项元素aij?1，因此若G是
连通的则矩阵C中每个元素均为1，否则为非连通的。 邻接矩阵与路的条数的关系：设G?(V,E)，其中V?{v1,v2,记为A，则Al(l?1,2,3,)
,vn}，其邻接矩阵
(l)的(i,j)项元素aij是连接vi到vj的长度为l的路的总数。
典型题解：
例1 分别写出下图(a)的邻接矩阵，并根据矩阵的元素求图(a)中结点v1的度数
30