资源描述：
《离散数学网上作业》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、离散数学网上作业作业4：图的矩阵表示及计算作业内容： 1．已知图G如下图所示． （1）试给出图G的集合表示； （2）求图G的邻接矩阵A； （3）利用矩阵A及其幂，求出从结点v1到v5长度为2和3的路的数目并写出这些路． 2.设G=，V={v1，v2，v3，v4，v5}，E={(v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}． （1）试给出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形．
2、 活动说明：图的矩阵表示及计算的内容是图论的应用之一，本次活动是一次运用图的矩阵解决实际问题的实践，也是学习过程中的一次形成性考核．本次活动共两个题目，第1题共45分，每小题15分；第2题共55分，其中第1、2、4小题各15分，第3小题各10分． 本次活动是一次学习过程中的形成性考核，凡是参加活动的学生都能获得相应的形成性考核分. 活动要求： 1．学生在Word下编辑完成作业，文件命名为“作业次数+学号”（这是第4次作业，即可命名为：4×××××××××.doc）． 2．完成作业后，采用“上传单个文件”的功能提交作业． 活动形式：首先在线下完成“图的
3、矩阵表示及计算”作业、然后采用上传单个文件的形式，把作业交给辅导教师批阅．作业上传时间：2009年3月30日—— 5月 24日作业5：平面图的概念及性质网上讨论题： 1．下面四个图中，（ ）不是平面图． 2．设平面图G＝有r个面：，则有2
4、E
5、=（）． 3．设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，则v,e和r满足的关系式是．4．给定图一如下图所示，试判断它是否为平面图，并说明理由（请用文字表述）．作业6：树的性质有最小生成树的算法网上讨论题 1．在一个有6个结点，8条边的连通图G中，从图G中删去多少条边后可
6、以确定图G的一棵生成树？ 2．在1棵有2个2度结点，4个3度结点，其余为树叶的无向树中，应该有几片树叶？ 3．有6个结点a,b,c,d,e,f的带权无向图各边的权如图所示．试求其最小生成树（请用文字表示，不必作图）． 4．设图G=，其中V={a,b,c,d,e}，E={(a,b),(a,c),(b,c),(b,d),(b,e),(c,e),(c,d),(d,e)}，对应边的权值依次为1、2、3、4、2、3、5及6，试 （1）下列三个图中，（ ）是本题图G的图形； （2）求出G权最小的生成树及其权值（请用文字表示，不必作图）．
7、 活动说明：本次活动是一次加深学生对树的性质理解的学习过程，也是进一步对树的性质应用的学习过程．本次活动共有四个题目，第1、2题是计算题，每题15分，共30分；第3、4题是应用题，每题35分，共70分． 本次活动是一次学习过程中的形成性考核，凡是参加活动的学生都能获得相应的形成性考核分. 活动要求：每位学生应该在规定时间内参加讨论，给出自己的解题过程，也可以对其他同学的做法进行评价．每位同学自己的作业请发一次贴即可，回帖不限。教师评分请通过学生发言后的“评价”选择分数，选择“呈送我的最新评分”即可。 活动形式：实时讨论 讨论时间：2009年4月27日—
8、—5月 24日（由教师按照教学进度确定具体时间） 5．给定图二如下图所示，试判断它是否为欧拉图、汉密尔顿图、或平面图？并说明理由（请用文字表述）． 活动说明： 1．本次活动是一次加深同学们对平面图的概念及性质理解的学习过程，也是一次学习过程中的形成性考核，凡是按照要求参加活动的学生都能获得形成性考核分． 2．本次活动共有三种题型．第1题是单项选择题，占10分；第2、3题是填空题，每题15分，共30分；第4、5题是判断题，要求作出判断，并说明理由，每题30分，共60分． 注意：大家在做第4、5题时，必须给出自己判断并要说明理由，如果只给
9、出自己判断而没有说明理由，并且判定正确，每题只能得到10分． 活动要求：每位学生应该在规定时间内参加讨论，必须发表自己的答案、判断和理由，也可以对其他同学的观点进行评价．每位同学自己的作业只发一次贴即可，回帖次数不限。教师评分请通过学生发言后的“评价”选择分数，选择“呈送我的最新评分”即可。 活动形式：实时讨论 讨论时间：2009年4月13日——5月24日（由教师按照教学进度确定具体时间）
