华东理工大学网络教育学院.doc

1、华东理工大学网络教育学院离散数学（专）阶段练习三（第五章、第六章）一、判断题（对的在括弧中打个“”，错的在括弧中打个“”）1、对任何无向图，奇其点的个数必然为奇数.（）2、对于简单无向图G 而言，其所有顶点的度数和等于其两倍的边数.（）3、自补图对应的完全图的边数必为偶数.（）4、简单通路就是边不重复的一个点边交替序列.（）5G必然是不连通的.（）、若图 G 是连通的，则其补图6、若 A(G ) 是图 G 的邻接矩阵，则矩阵幂次(A(G) 2中的对角线上元素aii(2)等于它对应的顶点 vi 的度 deg(vi ) .（）7、所有顶点的度都为偶数的无向图一定是欧拉图.（）8、含有汉密尔顿路的图

2、就是汉密尔顿图.（）9G 而言，其边数e、点数v、面数r必然满足 v e r2.（）、对连通平面图10、不存在点数、边数奇偶性不同的欧拉图.（）11、完全图 K5 不是欧拉图 .（）12、若图 G 是哈密尔顿图，则对G 中任意不相邻的顶点对u,v，均满足度数之和d(u)+d(v) n.（）13、不含奇圈（长度为奇数的圈）的无向图一定是二部图.（）14、完美匹配一定不是最大匹配 .（）15、边子集 M 是图 G 的最大匹配，当且仅当G中不含 M可扩路 .（）116、边子集 M 是图 G 的一个匹配，所谓M 交错路，就是一条通路，满足路上相邻两条边一条在 M 中，另一条不在M 中.（）二、简单作图

3、题1、画出一个自补图；2、画出一个既有欧拉回路、又有汉密尔顿圈的无向图；3、画出一个有欧拉回路、但没有汉密尔顿圈的无向图；4、画出一个无欧拉回路、但却有汉密尔顿圈的无向图；5、画出一个自对偶图.6、画出含有4 个顶点的含圈的所有非同构的连通图.三、填空题1、完全二部图K m,n 中的边数为.2、对无向图G 而言，若M 是 G 的一个匹配， G 中的一条通路P，满足相邻的两条边交替属于 M 和不属于M 这个条件的话，称通路P 为.3、对无向图G 而言，若 M 是 G 的一个匹配，则满足条件称为 M 可扩路 .4、点不重复的回路（即起、终点重合的通路）叫做.5、不连通图G 的几个不相连通的子图叫做

4、.6、删除图 G 中某个顶点关联的所有边之后，所剩的图（选填 “连通” 或“不连通”）.7、无向图的关联矩阵中，第i 行的元素和等于.8、有向图的关联矩阵中，第i 行里“ 1”的个数等于.9、有向图 D 的邻接矩阵 A 的 k 次幂 Ak 中，元素 a(k)表示图中从点vi 到 v的有向路ijj的条数 .10、如果只关心有向图D 中点 vi 到 v j 是否存在有向路可达，而不关心路的长度那么我们可以考虑（选填“关联矩阵” ，“邻接矩阵”或“可达矩阵”）.11、对无向图图G 而言，若M 是 G 的一个匹配，则M 是图 G 的最大匹配当且仅当.12、 n 个点的图G 的边数若为m，则它的补图G

5、的边数为.2四、 若无向图 G 中恰有两个奇点，试证明这两点之间必有一条路相连.五、 试证明完全二部图K 3, 3 不是平面图 .六、选择题1、下列选项中唯一不正确的是（）.（A）无向图的所有顶点的度的和，等于图中边数的2 倍 .（B）简单无向图G 是欧拉图，当且仅当它是每一个顶点的度都是偶数的连通图.（C）点、边、面数分别为v、 e、 r 的简单连通平面图的欧拉公式是v+er2 .（D ）不存在6 个顶点的自补图.2、具有 6 个顶点， 12 条边的连通简单平面图中，围成每个面的边数必为().（A）3；（B） 2 ；（ C） 4 ；（D）5.3、下列关于无向平面图的对偶图的描述，正确论断的个

6、数是（） .（1）任一简单平面图 G 的对偶图的对偶图一定是 G.（2）两个同构的简单连通平面图，它们的对偶图也是同构的.（3）任一平面图的对偶图一定是连通的.（4）简单平面图的对偶图一定也是简单平面图.（5）平面图G 的对偶图一定是平面图.3（6）平面图G 的面色数一定等于其对偶图的点色数.（A） 2；（B） 3；（C） 4；（D）5.4、下列关于图的描述的选项中，唯一不正确的是（） .（A）子图中的点数小于等于图中的点数（B）补图与原图的点数相等，但边数就不一定相等了（C）同构的两个图的点数对应相等，边数对应相等，但反之未必（D）彼得森（ Peterson ）图是哈密尔顿图七、 求证 ：若

7、简单无向图G 不连通，则其补图G 必然连通 .八、我们称与其补图同构的简单无向图为自补图。证明：每个自补图的阶或者能被4 整除，或者被 4 除余 1.九、 给出一个如下图的有向连通图G .1、写出它的邻接矩阵A ；2、图中长度为3 的回路（注意起点的不同）一共有多少条？3、求图的可达矩阵P .4离散数学（专）阶段练习三（第五章、第六章）答案一、判断题（对的在括弧中打个“”，错的在括弧中打个“”）题号12345678答案题号910111213141516答案二、简单作图题解：画图如下6、三、填空题1、 mn .2、M 交错路 .3、起终点均为非M 饱和点的M 交错路 .4、初级回路，或者圈5、连

8、通分图，或连通分支.6、不连通 .7、第 i 个点的度8、第 i 个点的出度 .9、长度为k 的 .10、可达矩阵 .11、 G 中不含 M 可扩路 .n(n1)12、m .2四、 证明：（反证法）不妨设着两个奇点为u、 w ，且它俩在图G 中没有路相连，那么它俩必存在于两个连通分支中，即存在于图G 的两个不连通的子图Gu 、 Gw 当中，而作为每个5子图来说，其中奇点的数目一定为偶数，故子图Gu 、 Gw 当中至少分别存在两个奇点，即图 G 中至少有 4 个奇点，这显然与图 G 中恰有两个奇点矛盾。故这两点之间必有一条路相连.五、证明：（反证法）设完全二部图K 3, 3 是平面图，且点数、边

9、数、面数分别为v 、 e 、 r ，由于图中任何三条边围不成一个面，即围成一个面至少需要4 条边，于是有2e4r，即r12 v er 中即得 e 2v4 。而 K 3 , 3 中的 e 9， v6e，代入欧拉公式，且292 6 4 8 ，于是矛盾，故而K 3, 3 不是平面图 .六、选择题题号1234答案CABD七、 证明：依题意， G 至少含有两个连通分支，不妨设为 G i 和 G j ，由于 G 的补图 G 与 G有相同的结点集合，所以，对任意的两点u 和 v ，分以下两种情形讨论：（ 1）若两点 u 和 v 属于 G 的不同连通分支， 则 u 和 v 在 G i 中无边相连， 由补图的定

10、义，即知 u 和 v 在 G 中必有一条边相连，即在G中连通 ；（ 2）若两点 u 和 v 属于 G 的同一个连通分支 G i ，则在另一个连通分支G j 中必存在一点w ，u和w在 G 中必有一条边相连，且v 和w在 G 中也必有一由第一种情形的证明，知条边相连，进而，在G 中，有 一条连接 u 和 v 的路 uwv 存在，即 u 和 v 在 G 中连通 .综合上述，知命题得证.八、证明：设图 G 是个自补图，且阶数为 n。由于图 G 与其补图 G 同构，所以， G 中的边数必然与G 中边的数目相同。于是，这两个图的边数均为完全图K n 中边数的一半，即6n(n1)4 。由于 n 和 (n 1) 中有且仅有一个偶数，所以，或者是n 能够被4 整除，或者是 (n1)能够被 4 整除。于是，该图的阶或者能被4 整除，或者被4除余 1.九、1、解：邻接矩阵如下所示：01001010A0011001