当前位置：文档之家 › 第四次辅导-欢迎访问安徽广播电视大学网站!

第四次辅导-欢迎访问安徽广播电视大学网站!

  • 格式：docx
  • 大小：210.94 KB
  • 文档页数：15

1 《计算机数学基础(1)》第四单元辅导 本单元重点：欧拉图和哈密顿图、平面图和树的基本概念. 代数运算及性质，群的概念，交换群和循环群.

一、重点内容 1. 欧拉图 欧拉通路(回路)与欧拉图 通过图G的每条边一次且仅一次，而且走遍每个结点的通路(回路)，就是欧拉通路(回路). 存在欧拉回路的图就是欧拉图. 欧拉回路要求边不能重复，结点可以重复. 笔不离开纸，不重复地走完所有的边，且走过所有结点，就是所谓的一笔画. 欧拉图或通路的判定 (1) 无向连通图G是欧拉图G不含奇数度结点(G的所有结点度数为偶数):(定理1) (2) 非平凡连通图G含有欧拉通路G最多有两个奇数度的结点；(定理1的推论) (3) 连通有向图D含有有向欧拉回路(即欧拉图)D中每个结点的入度＝出度 连通有向图D含有有向欧拉通路D中除两个结点外，其余每个结点的入度＝出度，且此两点满足deg－(u)－deg＋(v)＝1. (定理2) 2. 哈密顿图 哈密顿通路(回路)与哈密顿图 通过图G的每个结点一次，且仅一次的通路(回路)，就是哈密顿通路(回路). 存在哈密顿回路的图就是哈密顿图. 判断哈密顿图是较为困难的. 哈密顿图的充分条件和必要条件 (1) 在无向简单图G=中V3,任意不同结点VvuGvu)deg()deg(,,,则G

是哈密顿图.(充分条件，定理4) (2) 有向完全图D＝, 若3V，则图D是哈密顿图. (充分条件，定理5推论)

(3) 设无向图G=,V1V，则P(G－V1)V1(必要条件，定理3) 若此条件不满足，即V1V，使得P(G－V!)>V1,则G一定不是哈密顿图(非哈密顿图的充分条件). 3.平面图 平面图 一个图能画在平面上，除结点之外，再没有边与边相交. 面、边界和面的次数 由连通平面图G的边围成的其内部不含G的结点和边的区域是面，常用r表示. 围成面的各边组成的回路是边界. 边界回路的长度是面的次数，记作deg(r). 重要结论

(1)平面图ereEvVEVGrii2)deg(,,,,1则(所有面的次数之和＝边的2倍)(定理6). (2)欧拉公式：平面图,,,,eEvVEVG 面数为r，则2rev(结点数

与面数之和＝边数＋2)(定理7) (3)平面图633,,,,veveEvVEVG，则若(定理8)

判定条件：图G是平面图的充分必要条件是G不含与K3，3或K5在2度结点内同构的子图. 4. 树 2 树 连通无回路的无向图. 树的判别 图mEnVEVT,,,,T是树的充分必要条件是(六个等价定义)

(定理14): (1) T是无回路的连通图； (2) 图T无回路且m＝n－1； (3) 图T连通且m＝n－1 (4) 图T无回路，若增加一条边，就得到一条且仅一条回路； (5) 图T连通，若删去任一边，G则不连通； (6) 图T的每一对结点之间有一条且仅有一条通路. 生成树 图G的生成子图是树，该树就是生成树. 权与带权图 n个结点的连通图G，每边指定一正数，称为权，每边带权的图称为带权图. G的生成树T的所有边的权之和是生成树T的权，记作W(T). 最小生成树 带权最小的生成树. 有向树 有向图删去边的方向为树，该有向图就是有向树. 根树与树根 非平凡有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1，该树为根树. 每个结点的出度小于或等于2的根树为二元树(二叉树)；每个结点的出度等于0或2的根树为二元完全树(二叉完全树)；每个结点的出度等于2的根树称为正则二元树(正则二叉树). 哈夫曼树 用哈夫曼算法得到的最优二叉树. 4. 有关树的求法 生成树的破圈法和避圈法求法； 最小生成树的克鲁斯克尔求法； 哈夫曼树的哈夫曼求法. 二、实例

例6.1 判别图6－1的两幅图 是否可以一笔画出？ 解 在图6－1(a) 中， deg(v1)=deg(v2)=deg(v3)＝3 有两个以上的结点的度为3. 故在(a)中不存在欧拉通路，不能一笔画出. 在图6－1(b) 中，deg(A)=2, deg(B) =deg(C)= deg(D)=4，deg(E) =deg(F)=3 只有两个奇数度的结点，所以存在欧拉通路，可以一笔画出. 一条欧拉通路，如EDBEFCABCDF. 例6.2 判定图6－2中，两个图是否有欧拉回路？若有请把欧拉回路写出来. 解 在图D1中，v1点的出度为2， 入度为0； v5的出度为0，入度为2， 且这两点出度与入度之差不等于1， 所以，图D1不存在欧拉通路，图D1

不是欧拉图.

图D2中，各个结点的出度、入度 都相等2，所以存存欧拉回路，图D2 是欧拉图. 一个欧拉回路为v1 a v2 b v3 f v1 e v3 c v4 h v2 g v4 dv1 例6.3 指出图6－3各图是否哈密顿图，有无哈密顿通路， 回路？ 解 (1) 容易判断，存在哈密顿回路，故是哈密顿图. (2) 只有哈密顿通路，无哈密顿回路，故不是哈密顿图. (3) 无哈密顿通路，显然不是哈密顿图.

v4 v5 E  F  A v2  v3 B  C v1  D （a） (b) 图6－1

v1 v1 d  v4 v2  v5 f h a g e c v3   v4 v2  b  v3 D1 D2

图6－2 3 例6.4 画出具有下列条件的有5个结 点的无向图. (1) 不是哈密顿图，也不是欧拉图； (2) 有哈密顿回路，没有欧拉回路； (3) 没有哈密顿回路，有欧拉回路； (4) 是哈密顿图，也是欧拉图. 解 作图如图6－4(不唯一).

(1) (2) (3) (4) 图6－4 例6.5 判断图6－5是否为平面图？ 解 在G中，将(v1,v4)和(v3,v4) 改画成如虚线所示.可见G是平面图. v1 例6.6 在具有n个结点的完全 图Kn中，需要删去多少条边才能 v2 v3 .得到树？

v4 v5 G 图6－5

解 n个结点的完全图共有2n条边，而n个结点的树共有n－1条边. 因此需要删去

2)2)(1()1(2nnnn 条边后方可得到树. 例6.7 设G是图，无回路，但若外加任意一条边于G后，就形成一回路. 试证明G必为树. 证明 由树的定义可知，只需证G连通即可. 任取不相邻两点u,v, 由题设，加上边就形成一回路，于是去掉边,从u到v仍有路u,…,v，即u,v连通，由u,v的任意性可知，G是连通的，故G必是树. 例6.8 如图6－6是有6个结点a,b,c,d,e,f 的带权无向图，各边的权如图所示. 试求 其最小生成树. 解 构造连通无圈的图，即最小生成树， .用克鲁斯克尔算法： 第一步： 取ab＝1；第二步： 取af=4；第三步： 取fe=3；第四步： 取ad=9； 第五步： 取bc=23. 如图6－7。权为1+4+3+9+23=30 例6.9 单项选择题

              (1) (2) (3)

图6－3

b • 23 1 15 c• 25 • a 4 • f 28 9 16 3 d • 15 • e 图6－6

b • 23 1 c• • a 4 • f 9 3 d • • e 图6－7 4 1.无向图G是欧拉图，当且仅当( ) (A)G的所有结点的度数为偶数 (B) G的所有结点的度数为奇数 (C) G连通且所有结点的度数为偶数 (D) G连通且所有结点的度数为奇数 答案：(C) 解答：见本单元定理1. 2. 设mEnVEVG,,,为连通平面图且有r个面，则r＝( )

(A) m－n+2 (B) n－m－2 (C) n+m-2 (D) m+n+2 答案：(A) 解答：见定理7欧拉公式. 3. 设G是5个结点的无向完全图，则从G中删去( )条边可以得到树. (A) 4 (B)5 (C)6 (D)10 答案：(C)

解答：删去边的公式为2)2)(1()1(2nnnn. 故选择(C)正确. 4. 在5个结点的二元完全树中，若有4条边，则有 ( )片树叶。 (A) 2 (B) 3 (C) 5 (D) 4 答案：(B) 解答：二元完全树，即每个结点只有0个或2树枝的树，树根必有2个树枝，于是2个树枝只能其一又有2个树枝，而另一个就无树枝. 满足5个结点4条边. 可见有3片树叶. 选择(B)正确. 一般地，在二元完全树中，有m条边，t片树叶，则有m=2(t－1) 5. 图6－8是( ) (A) 完全图 (B)欧拉图 (C) 平面图 (D) 哈密顿图 答案：(D) 解答：因为n=6, 每对结点度数之和 大于或大于6，满足存在哈密顿回路的条 件，故为哈密顿图. 选择(D)正确. 例6.10 填空题 1.设G是完全二叉树，G有15个结点， 其中有8个是树叶，则G有 条边，G的总度数是 ，G的分支点数是 ，G中度数为3的结点数是 . 答案： 14； 28； 7； 6. 解答：可画图如图6－9. 有8个树叶，15个结点的完全二叉树， 2. 连通有向图D含有欧拉回路 的充分必要条件是 答案：D中每个结点的入度＝出度. 解答：见欧拉回路的判断方法，定理2. 3. 设G是n个结点的简单图，若G中每对结点的度数之和 ，则G一定是哈密顿图. 答案：大于或等于n 解答：见定理4. 4.设G是有n个结点，m条边的连通图，要确定G的一棵生成树，必须删去G的 条边.

      图6－8

        图6－9

合集下载

安徽财经大学新生指南.pdf

安徽财经大学新生指南.pdf

安徽财经大学新生指南安徽财经大学网络电视台整理新生指南安徽财经大学网络电视台整理二〇一四年七月目录新生指南之生活篇一、宿舍二、必备物品三、网络、手机、银行卡、饭卡、水卡、洗衣卡四、超市、购物、理发、洗浴五、军训、天气、医疗新生指南之交通篇一、铁路二、公交三、飞机新生指南之学习篇一、专业介绍二、转专业介绍三、双专业介绍四、奖学金介绍新生指南之选课篇新生指南之社团篇新生指南之风光篇一、校内风光二、校外风光新生指南之娱乐篇一、美食（校内、校外）二、旅游新生指南之生活篇一、宿舍1、东校区宿舍东校区学生宿舍是五人间，下面书桌上面床，每个人都有柜子，描述：宿舍里每人一张电脑桌，上网、看书都很方便，上面的书架可以放书和日用品，下面还有个小柜子和抽屉。

宿舍楼六层，进楼需要刷校园卡。

床尺寸是80*190的，个人觉得5号床最好，3，4次之。

阳面宿舍是最佳的。

大家可以带点特产来学校给同宿舍的，促进一下宿舍关系和谐。

寝室生活是大学里不可缺少的一部分，寝室的兄弟或者姐妹会是你大学四年最好的伙伴，好好的与人相处，好好的享受大学寝室生活。

宿舍没独立卫生间，楼层有公共厕所，每个寝室有单独的洗漱水池，喝水是桶装水（寝室饮水机需缴纳订金，大四时会退还。

有专人将水送至寝室门口，不强制喝桶装水，楼层内也有打热水的地方）。

宿舍内有空调可以使用。

每栋楼下有洗衣房。

宿舍十一点关门（晚上十一点断网，周五周六为晚上十一点半。

），不能使用大功率电器，跳电会被骂的很惨，而且大功率被学校检查宿舍的搜出来后果很严重，会被记过，整个宿舍取消评优，入党等等等。

宿舍限电1200w左右。

当然，每个宿舍也许不一样。

电费的话是每个月25度免费，超过的交钱，宿舍成员AA或者根据个人用电多少分摊。

缴费登陆http://211.86.241.62/用饭卡交钱买电就可以了。

2、西校区宿舍西校宿舍楼主要为六栋，七栋和十栋。

六，七栋为女生宿舍楼，十栋为男生宿舍楼。

六栋条件相对较简陋，不过据悉暑假期间正在进行装修，住六栋的小伙伴们住宿条件有望得到改善。

“电大在线”选课、学习、发帖、考试平台介绍及操作步骤详解

“电大在线”选课、学习、发帖、考试平台介绍及操作步骤详解

“电大在线”选课、学习、发帖、考试平台介绍及操作步骤详解一、“成都电大在线”操作步骤（一）、选课登录（成都电大在线首页）在页面左侧“用户登录”栏输入账号（学号）、密码（身份证8位生日号码如：19800101）点“登录”。

进入后在右上方分本、专科选你所学专业，如（若过去已选过课，则直接在“我的学习课程列表”下方点击“选课”，再选专业）就会出显课程列表，如：然后对照本期课表，勾选本学期所要选的课（在框里打“”），如：勾选完后，点击最下面“保存选课”，这样课就选好了。

（二）、网上学习（要求：每门课程在网上学习时间达到60分钟以上，点击浏览或下载视频、课件、文字等学习资源25次以上；发帖或回帖、跟帖1次以上。

）点击“我的学习课程”，左下方会出显示“我的课程列表”，点击你要学习的课程，如：即进入该课程的课程学习页面：这些就是所需学习的内容，点击这些内容进行学习即可。

【特别注意：1、进入课程学习页面后系统便开始自动计录你的学习活动（包括在线学习时间、点击浏览和下载学习资源的次数等），但是，如1小时内无学习活动（点击浏览或下载学习资源），系统将自动退出，且不计录学习时间；2、点击打开一个学习资源后必须停留5分钟以上才能继续打开第二个资源，每次学习活动最多只能同时打开三个学习资源。

每个学习资源打开后的停留时间不能超过60分钟，且文字类学习资源打开后30分钟无动作（鼠标移动、翻动页面等）或视频类资源播放完后30分钟不关闭的系统都将视其学习活动无效，不予记录；3、在完成某项内容学习后，点击下面的“关闭页面”，可继续点击打开其他内容学习；4、在退出课程学习页面时一定要从该页面右上的“退出系统”退出，不能直接关闭课程学习页面，否则你的学习活动也将不被记录】（三）、发帖、回帖、跟帖（要求：每门课程1次以上）1.发帖：学员可根据需要在多个“论坛”发帖（亦可回帖、跟帖）（1）、在课程论坛发帖：【特别注意：所发帖子必须为有效帖！即：帖子内容必须与该门课程学习的内容、方法等有关：如学习中的问题、体会、感悟、学习方法交流以及实时导学签到等。

安徽大学学分制与网上选课介绍2

安徽大学学分制与网上选课介绍2

安徽大学学分制与网上选课介绍欢迎各位同学来到国家“211工程”重点建设高校——安徽大学学习和生活。

安徽大学以“至诚至坚，博学笃行”为校训，倡导“以人为本、以学生为中心”的办学理念，逐步完善多样性、个性化的人才培养途径。

学校实施“三基并重、全面发展”的人才培养模式，着力培养具有扎实的基本理论、较强的基本技能和良好的基本素质，德智体美全面发展，具有宽口径、厚基础、高素质、强能力的创新人才。

学校推行以选课制、导师制和弹性学制为特征的学分制，科学制定各专业的人才培养方案，系统设计第一课堂的专业学习和第二课堂的社会实践活动；优化教育模块，使专业教育与自主学习有机结合；允许学生在3～6年内自主选择修业年限和申请辅修第二专业；改革公共基础课程，实行分类分级教学，不断提高教学质量。

从2008年开始，我校对一年级新生实施“启航工程”，加强大学适应性教育、学习能力教育和学科专业兴趣培养，引导新生尽早适应大学学习与生活。

下面将对我校实行的学分制、本科专业人才培养方案、现代教务系统和网上选课以及学籍管理做一简要介绍，以方便同学今后几年在大学的学习。

一、学分制概况学分制是以选课和学分累积为主要特点的教学管理模式，其目的在于尊重学生的学习兴趣，促进学生多样性和个性化发展，更加有利于培养学生的创新精神和实践能力，其主要特点是：1、以学分作为计算学生学习“量”的基本单位在学分制管理模式中，每门课程都配置了相应的学分。

学分通常按照课程教学的18学时折算为1学分。

但考虑到课程教学的难易程度课时学分有所变化，对公共基础课、大学体育课程、课程教学中的实验课程或单独设置的实验实践类等课程的学分可作适当调整。

例如，《微观经济学》计划学时为54学时，对应的学分为3个学分；公共基础课程《大学体育（一）》计划学时为36学时, 对应的学分为1个学分，《普通物理实验A（上）》计划学时为54学时，对应的学分为1个学分。

2、以取得规定最低学分作为学生毕业、获得学士学位的标准从2004级学生开始，我校本科各专业教育总学分均设定为160学分。

2.安徽大学学生学习指导手册

2.安徽大学学生学习指导手册

安徽大学学生学习指导手册（安徽大学教务处 2008年9月整理）一、前言为了方便学生在校学习，根据安徽大学本科教学管理文件的精神和有关内容，结合学生学习过程中出现的具体情况，整理和编印了安徽大学学生学习指导手册。

本手册是学校有关文件的摘录和整理，基本涵盖了学生从入学注册到毕业离校过程中参与学校学习的各个环节。

二、学制我校从2000年开始对接受普通高等学历教育的标准四年制本科学生实行学分制学籍管理，实行弹性学制，学生在校学习年限为三至六年。

艺术学院实行学年学分制，其学制为四年。

三、入学（一）按国家招生规定录取的新生，持录取通知书、本人身份证，按学校有关要求和规定的期限到校办理入学手续。

（二）因故不能按期入学者，应当向学校招生办公室请假，说明理由并交附原单位或所在街道、乡镇证明，假期一般不超过两周。

未请假或者请假后逾期两周不报到者，除因不可抗力等正当事由以外，视为放弃入学资格。

（三）新生入学后，学校在新生报到之日起三个月内按照国家招生规定对新生进行复查。

复查合格者予以注册，取得学籍，发给学生证。

复查不合格者，由学校区别情况，予以处理，直至取消入学资格。

凡属弄虚作假、徇私舞弊取得学籍者，一经查实，学校应当取消其学籍。

情节恶劣的，应当请有关部门查究。

（四）对患有疾病的新生，经学校指定的二级甲等以上医院(下同)诊断不宜在校学习的，可由本人申请，所在院（系）和教务处签署意见，经分管校长批准，准许保留入学资格一年，并发给证明。

保留入学资格者不具有学籍。

保留入学资格期间医疗费用等均由学生自理，不享受本校在籍学生的一切待遇。

在保留入学资格期内经治疗康复，可以向学校申请入学，由学校指定医院诊断，符合体检要求，经学校复查合格后，重新办理入学手续。

复查不合格或者逾期不办理入学手续者，视为放弃入学资格。

四、注册（一）在校学生应当于每个学年、学期开学时按学校有关要求和规定的期限到学校财务部门缴纳学费，并持学生证和收费凭证到院系教学办公室办理注册手续，方能取得该学期学籍。