华东理工大学 网 络 教 育 学 院
《离散数学（专）》阶段练习三
（第五章、第六章）
一、判断题（对的在括弧中打个“√”，错的在括弧中打个“⨯”）
1、对任何无向图，奇其点的个数必然为奇数. （ ）
2、对于简单无向图G 而言，其所有顶点的度数和等于其两倍的边数. （ ）
3、自补图对应的完全图的边数必为偶数. （ ）
4、简单通路就是边不重复的一个点边交替序列.
（
）
5、若图G 是连通的，则其补图G 必然是不连通的.
（ ）
6、若)(G A 是图G 的邻接矩阵，则矩阵幂次2
))((G A 中的对角线上元素)
2(ii a 等于它对应的
顶点i v 的度)deg(i v .
（ ） 7、所有顶点的度都为偶数的无向图一定是欧拉图. （ ）
8、含有汉密尔顿路的图就是汉密尔顿图. （ ）
9、对连通平面图G 而言，其边数e 、点数v 、面数r 必然满足2=+-r e v . （ ）
10、不存在点数、边数奇偶性不同的欧拉图. （
）
11、完全图5K 不是欧拉图.
（ ）
12、若图G 是哈密尔顿图，则对G 中任意不相邻的顶点对u,v ，均满足度数之和d (u )+d (v ) ≥ n . （ ）
13、不含奇圈（长度为奇数的圈）的无向图一定是二部图. （ ）
14、完美匹配一定不是最大匹配. （ ）
15、边子集M 是图G 的最大匹配，当且仅当G 中不含M 可扩路. （ ）
16、边子集M 是图G 的一个匹配，所谓M 交错路，就是一条通路，满足路上相邻两条边一条在M 中，另一条不在M 中. （ ）
二、简单作图题
1、画出一个自补图；
2、画出一个既有欧拉回路、又有汉密尔顿圈的无向图；
3、画出一个有欧拉回路、但没有汉密尔顿圈的无向图；
4、画出一个无欧拉回路、但却有汉密尔顿圈的无向图；
5、画出一个自对偶图.
6、画出含有4个顶点的含圈的所有非同构的连通图.
三、填空题
1、完全二部图,m n K 中的边数为 .
2、对无向图G 而言，若M 是G 的一个匹配，G 中的一条通路P ，满足相邻的两条边交替属于M 和不属于M 这个条件的话，称通路P 为 .
3、对无向图G 而言，若M 是G 的一个匹配，则满足条件 称为M 可扩路.
4、点不重复的回路（即起、终点重合的通路）叫做 .
5、不连通图G 的几个不相连通的子图叫做 .
6、删除图G 中某个顶点关联的所有边之后，所剩的图 （选填“连通”或“不连通”）.
7、无向图的关联矩阵中，第i 行的元素和等于 .
8、有向图的关联矩阵中，第i 行里“1”的个数等于 .
9、有向图D 的邻接矩阵A 的k 次幂k
A 中，元素()
k ij a 表示图中从点i v 到j v 的 有向路的条数.
10、如果只关心有向图D 中点i v 到j v 是否存在有向路可达，而不关心路的长度那么我们可以考虑 （选填“关联矩阵”，“邻接矩阵”或“可达矩阵”）.
11、对无向图图G 而言，若M 是G 的一个匹配，则M 是图G 的最大匹配当且仅当 . 12、n 个点的图G 的边数若为m ，则它的补图G 的边数为 .
四、若无向图G 中恰有两个奇点，试证明这两点之间必有一条路相连.
五、试证明完全二部图3,3K 不是平面图.
六、选择题
1、下列选项中唯一不正确的是（ ）.
（A ）无向图的所有顶点的度的和，等于图中边数的2倍.
（B ）简单无向图G 是欧拉图，当且仅当它是每一个顶点的度都是偶数的连通图. （C ）点、边、面数分别为v e r 、、的简单连通平面图的欧拉公式是+2v e r -=. （D ）不存在6个顶点的自补图.
2、具有6 个顶点，12条边的连通简单平面图中，围成每个面的边数必为( ). （A ）3；
（B ） 2；
（C ） 4；
（D ）5.
3、下列关于无向平面图的对偶图的描述，正确论断的个数是（ ）. （1）任一简单平面图G 的对偶图的对偶图一定是G . （2）两个同构的简单连通平面图，它们的对偶图也是同构的. （3）任一平面图的对偶图一定是连通的. （4）简单平面图的对偶图一定也是简单平面图. （5）平面图G 的对偶图一定是平面图.
（6）平面图G的面色数一定等于其对偶图的点色数.
（A）2；（B）3；（C）4；（D）5.
4、下列关于图的描述的选项中，唯一不正确的是（）.
（A）子图中的点数小于等于图中的点数
（B）补图与原图的点数相等，但边数就不一定相等了
（C）同构的两个图的点数对应相等，边数对应相等，但反之未必
（D）彼得森（Peterson）图是哈密尔顿图
七、求证：若简单无向图G不连通，则其补图G必然连通.
八、我们称与其补图同构的简单无向图为自补图。
证明：每个自补图的阶或者能被4整除，或者被4除余1.
九、给出一个如下图的有向连通图G.
1、写出它的邻接矩阵A；
2、图中长度为3的回路（注意起点的不同）一共有多少条？
3、求图的可达矩阵P.
《离散数学（专）》阶段练习三 （第五章、第六章）答案
一、判断题（对的在括弧中打个“√”，错的在括弧中打个“⨯”）
二、简单作图题
解：画图如下
6、
三、填空题
1、mn .
2、M 交错路.
3、起终点均为非M 饱和点的M 交错路.
4、初级回路，或者圈
5、连通分图，或连通分支.
6、不连通.
7、第i 个点的度 8、第i 个点的出度. 9、长度为k 的. 10、可达矩阵.
11、G 中不含M 可扩路. 12、
(1)
2
n n m --.
四、证明：（反证法）不妨设着两个奇点为w u 、，且它俩在图G 中没有路相连，那么它俩必存在于两个连通分支中，即存在于图G 的两个不连通的子图u G 、w G 当中，而作为每个
子图来说，其中奇点的数目一定为偶数，故子图u G 、w G 当中至少分别存在两个奇点，即图G 中至少有4个奇点，这显然与图G 中恰有两个奇点矛盾。
故这两点之间必有一条路相连.
五、
证明：（反证法）设完全二部图3,3K 是平面图，且点数、边数、面数分别为v 、e 、r ，
由于图中任何三条边围不成一个面，即围成一个面至少需要4条边，于是有r e 42≥，即
e r 2
1
≤
，代入欧拉公式r e v +-=2中即得42-≤v e 。
而3,3K 中的9=e ，6=v ，且84629=-⋅>，于是矛盾，故而3,3K 不是平面图.
六、选择题
七、 证明：依题意，G 至少含有两个连通分支，不妨设为i G 和j G ，由于G 的补图G 与G 有相同的结点集合，所以，对任意的两点u 和v ，分以下两种情形讨论：
（1）若两点u 和v 属于G 的不同连通分支，则u 和v 在i G 中无边相连，由补图的定义，即知u 和v 在G 中必有一条边相连，即在G 中连通；
（2）若两点u 和v 属于G 的同一个连通分支i G ，则在另一个连通分支j G 中必存在一
点w ，由第一种情形的证明，知u 和w 在G 中必有一条边相连，且v 和w 在G 中也必有一条边相连，进而，在G 中，有一条连接u 和v 的路uwv 存在，即u 和v 在G 中连通. 综合上述，知命题得证. 八、
证明：设图G 是个自补图，且阶数为n 。
由于图G 与其补图G 同构，所以，G 中的边数必然与G 中边的数目相同。
于是，这两个图的边数均为完全图n K 中边数的一半，即
(1)4n n -。
由于n 和(1)n -中有且仅有一个偶数，所以，或者是n 能够被4整除，或者
是(1)n -能够被4整除。
于是，该图的阶或者能被4整除，或者被4除余1.
九、 1、
解：邻接矩阵如下所示：
0100101010010
01
0A ⎡⎤⎢⎥⎢
⎥=⎢⎥⎢⎥⎣⎦
2、 解：由
2
1010110101101
00
1A ⎡⎤⎢⎥⎢
⎥=⎢⎥⎢⎥⎣⎦
及
3
1101112020110
11
0A ⎡⎤⎢⎥⎢
⎥=⎢⎥⎢⎥⎣⎦
，即知长度为3的回路个数等于
3()1113tr A =++=.
注：若直接从图上找出3条回路（写出顶点顺序），也可以. 3、
解：由2
3
4
+++P A A A A =，并将所得矩阵中的非零元换成“1”，即得
1
111111111111
11
1P ⎡⎤⎢⎥⎢
⎥=⎢⎥⎢⎥⎣⎦
.。