清欠考试--2010-2011第一学期《图论》试卷.doc

《清欠考试--2010-2011第一学期《图论》试卷.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、南京邮电大学2010/2011学年第一学期《图论与代数系统》清欠考试试卷本试卷共4页；考试时间110分钟；装订线内不要答题自觉遵守考试规则，诚信考试，绝不作弊专业班级学号姓名题号一二三四总分分数得分一、填空题（20分，每空2分）1．由布尔格，可以诱导一个代数系统，这个代数系统称为。2．在代数系统中，对运算的幺元是__________，对运算的幺元是____________。3．设是一个偏序集，　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　则称为

2、格。4．有限布尔代数的元素的个数必定等于　　　　　　　　　　　　　　。5．n个结点的无向完全图的边数为　　　　　　。6．给定无孤立结点图G，G中的欧拉路是指　　　　　　　　　　　　。7．若一条路中所有的边均不相同，称作　　　　　　　　　　。8．一个代数系统，其中是非空集合，是上的一个二元运算。如果：（1）　　　　　　　　　　　　　　，（2）　　　　　　　　　　　　　，则称代数系统为半群。得分二、判别题，正确的打√、错误的打´。（20分，每题2分）1．分配格一定是布尔格。　　　　　　　　　　　　　　

3、　　（　　）2．自然数集合上的减法运算是封闭的。　　　　　　　　　　（　　）3．强连通图一定是单侧连通的。　　　　　　　　　（　　）4．群中一定有零元。　　（　　）5．代数系统每个元素都有逆元。　　　　　　　　　　　（　　）6．元素个数为4的格一定是布尔格。　　　　　　　　　　　　　（　　）7．一个图的生成子图必是唯一的。　　　　　　　　　　　　　　（　　）8．存在割点的连通图其连通度必为1。　　　　　　　　　　　　　（　　）9．对于两个图，如果结点数目相等，边数相等，度数相等的结点数目

4、也相等，则这两个图同构。　　　　　　　　　　　　（　　）10．在任何有向图中，所有节点的入度之和等于所有节点的出度之和。（）　　　　　　　　　　　　　　　　　得分三、解答题（50分，每题10分）1.请画出两个含有5个元素的非分配格。2.写出下图的邻接矩阵，并求出可达性矩阵。　3.下面各图中，哪些可以一笔画？哪些可以从任一点一笔画？（a）(b)(c)a4．判断所给的图G是否为汉密尔顿图，如果是，则给出汗密尔顿回路，否则证明其不是汉密尔顿图。fedcb5.求下图的一棵最小生成树。装订线内不要答题自觉遵

5、守考试规则，诚信考试，绝不作弊得分四、证明题（10分）1．给定代数系统＜R，+＞，其中，R为实数集，+为普通加法运算，证明＜R，+＞是群。