离散数学测验题--图论部分
更新时间:2023-10-03 16:11:01 阅读量:2 综合文库 文档下载
离散数学图论单元测验题
一、单项选择题(本大题共10小题,每小题2分,共20分) 1、在图G=
(A) deg(vi)=2?E? (B) deg(vi)=?E? (C)
?deg(v)?2E (D) ?deg(v)?E
v?Vv?V2、设D是n个结点的无向简单完全图,则图D的边数为( ) (A) n(n-1) (B) n(n+1) (C) n(n-1)/2 (D) n(n+1)/2
3、 设G=
(A) ?(G)
4、图G与G?的结点和边分别存在一一对应关系,是G≌G?(同构)的( ) (A) 充分条件 (B) 必要条件 (C)充分必要条件 (D)既非充分也非必要条件 5、设V?{a,b,c,d},则与V能构成强连通图的边集合是( )
(A) E?{?a,d?,?b,a?,?b,d?,?c,b?,?d,c?} (B) E?{?a,d?,?b,a?,?b,c?,?b,d?,?d,c?} (C) E?{?a,c?,?b,a?,?b,c?,?d,a?,?d,c?}
6、有向图的邻接矩阵中,行元素之和是对应结点的( ),列元素之和是对应结点的( (A)度数 (B) 出度 (C)最大度数 (D) 入度
7、设图G的邻接矩阵为
??00100??00011?
??10000??
?01001????01010??则G的边数为( ).
A.5 B.6 C.3 D.4
8、设G??V,E?,V?n,E?m为连通平面图且有r个面,则r=( ) (A) m-n+2 (B) n-m-2 (C) n+m-2 (D) m+n+2
9、在5个结点的二元完全树中,若有4条边,则有 ( )片树叶。 (A) 2 (B) 3 (C) 5 (D) 4 10、图2是( ) (A) 完全图 (B)欧拉图 (C) 平面图 (D) 哈密顿图 ? ? ?
? ? ?
图2
)
二、填空题(本大题共10小题,每题2分,共20分)
1、设图G=
2、设G是完全二叉树,G有15个结点,其中有8个是树叶,则G有 条边,G的总度数是 ,G的分支点数是 ,G中度数为3的结点数是 . 3、一棵树有两个结点度数为2,一个结点度数为3,三个结点度数为4,问它有几个度数为1的结点。
4、画出满足下列条件的图:
(1) 画一个有一条欧拉回路和一条哈密顿回路的图; (2) 画一个有一条欧拉回路,但没有哈密顿回路的图; (3) 画一条没有欧拉路,但有一条哈密顿回路的图.
5、设G是n个结点的简单图,若G中每对结点的度数之和 ,则G一定是哈密顿图.
6、一个有向树T称为根树,若 ,其中 称为树根,
称为树叶. 7、设G是平面图,G有8个面,每个面的度数都是3,则G有__________条边,G有__________个顶点。 8、设G是有n个结点,m条边的连通图,要确定G的一棵生成树,必须删去G的 条边.
9、在下图中,哪些是欧拉图?哪些是哈密顿图?哪些是平面图?
? ?
? ? ? (1) ? ? (3) (2) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (4) ? ? ? ? (6) (5) 10、设G是n阶无向带权边连通图,各边的权均为a(a>0),设T是G的一棵最小生成树,则T的权W(T)=________(n-1)*a_______________。
三、计算题(本大题共4小题,每小题10分,共40分)
1、设G=
E?{(v1,v2),(v2,v3),(v3,v1),(v1,v5),(v5,v4),(v3,v4),(v7,v8)}
(1) G=
2、设图G是具有3个顶点的无向完全图,试问
(1) G有多少个子图? (2) G有多少个生成子图?
(3) 如果没有任何两个子图是同构的,则G的子图个数是多少?将它们构造出来.
3.图G=
f), (e, f)},对应边的权值依次为5,2,1,2,6,1,9,3及8.
(1)画出G的图形; (2)写出G的邻接矩阵;
(3)求出G权最小的生成树及其权值.
4.设有一组权为2,3,5,7,11,13,17,19,23,29,31,试
(1)画出相应的最优二叉树; (2)计算它们的权值.
四、证明题(本大题共3小题,任选2题,每小题10分,共20分)
1.若无向图G中只有两个奇数度结点,则这两个结点一定是连通的.
2.设G是一个n阶无向简单图,n是大于等于2的奇数.证明图G与它的补图G中的奇数度顶点个数相等.
3.设连通图G有k个奇数度的结点,证明在图G中至少要添加欧拉图.
k条边才能使其成为2
补充
1、若图G是不连通的,则G的补图G是连通的。
2、当且仅当G的一条边e不包含在G的回路中时,e才是G的割边。 3、设G是简单平面图,则它—定有一个度数≤5的结点。
解答:
一、单项选择题(本大题共10小题,每小题2分,共20分) 1、在图G=
(A) deg(vi)=2?E? (B) deg(vi)=?E? (C)
?deg(v)?2E (D) ?deg(v)?E
v?Vv?V 答案:(C)
2、设D是n个结点的无向简单完全图,则图D的边数为( ) (A) n(n-1) (B) n(n+1) (C) n(n-1)/2 (D) n(n+1)/2 答案: (C)
3、 设G=
解答:因为G中无平行边和环,任何结点最多有n-1条边与其相关联,最大度数小于或等于n-1. 故选择(A)
4、图G与G?的结点和边分别存在一一对应关系,是G≌G?(同构)的( ) (A) 充分条件 (B) 必要条件 (C)充分必要条件 (D)既非充分也非必要条件 答案:(B) 解答:见图的同构定义. 5、设V?{a,b,c,d},则与V能构成强连通图的边集合是( )
(D) E?{?a,d?,?b,a?,?b,d?,?c,b?,?d,c?} (E) E?{?a,d?,?b,a?,?b,c?,?b,d?,?d,c?} (F) E?{?a,c?,?b,a?,?b,c?,?d,a?,?d,c?} (G) E?{?a,b?,?a,c?,?a,d?,?b,d?,?c,d?}
答案:(A) 解答:有向图G任何一对结点间都互相可达,称该图是强连通的. (A)所给的边的集合存在一个通过所有结点的通路. 故选择(A).
6、有向图的邻接矩阵中,行元素之和是对应结点的( ),列元素之和是对应结点的( ) (A)度数 (B) 出度 (C)最大度数 (D) 入度 答案:(B),(D)
解答:见邻接矩阵的定义. 7、设图G的邻接矩阵为
正在阅读:
离散数学测验题--图论部分10-03
《小蝌蚪找妈妈教学反思》反思05-19
《众神与野兽》影评10篇12-12
公共关系案例试题05-22
灯具购销合同范本专业版(1)07-19
我要飞作文350字06-25
一件难忘的事情作文450字07-02
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 离散
- 测验
- 数学
- 部分
- “十三五”重点项目-环保型煤锅炉项目申请报告
- 种群、生物群落和生态系统
- 动态结构图
- 心字上面减两点(打一字)
- 算法设计与分析 复习
- 2016届吉林省吉林大学附属中学高三上学期第五次摸底考试数学(理)试题
- 电大社区护理学形成性考核册答案
- 中普审计软件实验报告
- CAXA期末试题附答案
- 现代英语语法形容词短语和比较(2018年1月17日) - 图文
- 影视鉴赏作业二
- 动词-5
- sspulinux 正则表达式简单易学法
- 北京理工大学-数据库-实验 - 3-视图、函数
- 计算机网络安全教程第二版课后答案石志国主编(终极版)
- 2017年初一数学12月份月考试题及答案
- 高中文言文阅读练习题
- 抓斗天车点检事项及作业分配 - 图文
- 工程造价基础知识讲
- 血液透析题库