离散数学有大题..docx

总复习题（一）一．单选题1 (C)。一连通的平面图，5个顶点3个面，则边数为（）。、4、5、6、72、 (A)。如果一个简单图，则称为自补图，非同构的无向4阶自补图有（）个。、1、2、3、43、 (D)。为无环有向图，为的关联矩阵，则（）。、是的终点、与不关联、与关联、是的始点4、 (B)。一连通的平面图，8个顶点4个面，则边数为。、9、10、11、125、 (D)。如果一个简单图，则称为自补图，非同构的3阶有向完全图的子图中自补图有个。、1、2、3、46、21条边，3个4度顶点，其余顶点为3度的无向图共有个顶点。、13、12、11、107、 (D)。有向图的通路包括。、简单通路、初级通路、复杂通路、简单通路、初级通路和复杂通路8、 (D)。一连通的平面图，9个顶点5个面，则边数为。、9、10、11、129、21条边，3个4度顶点，其余顶点为3度的无向图共有个顶点。、13、12、11、1010、 (D)。有向图的通路包括。、简单通路、初级通路、复杂通路、简单通路、初级通路和复杂通路11、 (D)。一连通的平面图，9个顶点5个面，则边数为。、9、10、11、1212、 (B)。为有向图，为的邻接矩阵，则。、邻接到的边的条数是５、接到的长度为４的通路数是５、长度为４的通路总数是５、长度为４的回路总数是５13、 (C)。在无向完全图中有个结点，则该图的边数为（）。A、 B、 C、 D、14、 (C)。任意平面图最多是（）色的。A、3 B、4 C、5 D、615、 (A)。对与10个结点的完全图，对其着色时，需要的最少颜色数为（）。A、10 B、9 C、11 D、1216、(C)。对于任意的连通的平面图，且每个面的次数至少为有，其中，分别为的阶数、边数。、、、、二．判断题1、 (A)。有向图的关联矩阵要求图是无环图。（　　）2、 (A)。是某图的度数序列。（　　）3、 (A)。无向连通图的点的连通关系是等价关系（　　）4、 (B)。是某图的度数序列。（　　）5、 (A)。V和E分别为无向连通图G1的点割集和边割集. G1 -E的连通分支个数为2。 ( )6、 (A)。彼得森图不是哈密尔顿图。（　　）7、 (B)。是平面图。（　　）8、 (B)。设是平面图，若，则它们的对偶图。（　　）9、 (A)。是平面图。（　　）10、 (A)。一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。（）11、 (B)。平面图中，任何两条边除端点外可以有其他交点。（）12、 (B)。余树一定是树。（　　）13、 (A)。为无向连通图，是的生成子图，并且是树，则是的生成树。（　　）14、 (A)。是非平凡的无向树，则至少有两片树叶（　　）15、 (B)。无向树有3个3度、2个2度顶点，其余顶点都是树叶，共有4片树叶。 ( )16、 (A)。无向树有3个3度、2个2度顶点，其余顶点都是树叶，共有5片树叶。( )17、 (B)。已知n(n=2)阶无向简单树具有n-1条边，他一定是树。( )18、 (A)。一个连通无向图中，存在两个结点和，如果结点和的每一条路都通过结点，则结点比为割点。（）19、 (A)。一个有向图，如果中有一个回路，至少包含每个结点一次，则是强连通。20、 (A)。给定图，则关于树的定义是每一对结点之间有且仅有一条路。（）21、 (A)。完全叉树是每一个结点的出度等于或0的根树。（）22、 (A)。在正则叉树中，所有的树叶层次相同。（）23、 (B)。树中分支点的通路长度为外部通路长度。（）24、 (B)。树中树叶的通路长度为内部通路长度。（）25、 (A)。任何一棵二叉树的树叶可对应一个前缀码。（）26、(A)。任何一个前缀码都对应一棵二叉树。（）三．综合题1.证明:若图是自对偶的，则.2.T是一棵树,有两个2度结点，一个3度结点，三个4度结点，T有几片树叶？解：设树T有x片树叶，则T的结点数 n=2+1+3+x T的边数m=n-1=5+x又由得 2 ·（5+x）=2·2+3·1+4·3+x?所以x=9，即树T有9片树叶。3.图所示的赋权图G表示七个城市a,b,c,d,e,f,g及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小,并计算出最小造价。解：最小生成树为因此如图TG架线使各城市间能够通讯，且总造价最小，最小造价为：　Ｗ(Ｔ)＝１＋３＋４＋８＋９＋23＝484.求出下所示图的邻接矩阵和可达性矩阵，并找出。解：邻接矩阵5.求下图的一棵最小生成树.解：因为图中n＝8，所以按算法要执行n－1＝7次，其过程见下图中(1)~(7)。6.v1到v4,v4到v1长为3的通路各有多少条?求出下所示图的邻接矩阵和可达性矩阵v1到v4长为3的通路