离散数学-图论-树课件

离散数学图论-树离散数学图论-树离散数学图论-树第16章树第十六章树、无向树1)定义:连通无回路(初级回路或简单回路)的无向图称为无向树,或简称树常用T表示树,平凡图称为平凡树若无向图G至少有两个连通分支,则称G为森林在无向树中,悬挂顶点称为树叶,度数大于或等于2的顶点称为分支结点2)树的等价定义B>是n阶条边的无向图则下面各命题是等价的(1)G是连通无回路(树)可通过循环证明(2)G中任意两个顶点之间存在惟一的路径(连通则存在路径,若不唯一,不同路径则构成回路)(3)G中无回路且m=n-1有长大于等于2的回路都与唯一路径矛盾对结点进行归纳:n=1平凡图m=0=n-1;设n=k成立;n=k+1时两个结点有唯一的路,去掉则为两个连通分支(各自满足假设)m=m1+m2+1=n1-1+n2-1+1=n1+n2-1=n-1(4)G是连通的且m=n-1若不连通,对各个(s>=2)连通分支是树且有mi=ni-1皿=n-8s>=2矛盾一、课前演讲激发学生情趣知识的掌握，能力的培养，情感的体验，说到底需要学生自己的体验和实践。教师主宰式的教学模式，使学生处于被动的位置上，心智处于压抑的状态中，积极性和主动性无法真正调动起来。只有当学生以主人的姿态出现在语文教学活动中，让学生成为课堂的主讲者，语文教学才会脱胎换骨、焕然一新。教师课前三分钟的演讲活动，为学生提供了参与的平台。为了演讲成功，获得大家的肯定，每个学生都在积极准备。他们精心地去搜集材料、组织材料、反复练习。经过一段时间的锻炼，同学们变得勇敢自信，由于演讲内容都是自己构思完成的，学生们爱讲、爱听，学习的积极性主动性也就极大地调动起来了。二、指导学生进行有效预习俗话说：凡是预则立，不预则废。当前教学，许多人都把课堂效率的目光投向老师，要老师精心备课，尽心设计，其实学生也需要备课，那就是课前预习。作为教师，我们深知：只有熟读课文才能领会文章的中心，形成自己独特的见解，领会作者的意图，体验作者的情感。“文不读熟不讲”，这是许多有教学经验的老师常说的一句话，那么对于学生，他们必须有充足时间自主接触文章，但课堂时间的是有限的，如果留足时间给学生熟读，势必会造成教学内容无法完成，如果不留足时间让学生接触文本，自主探究，文本的生疏课堂学习不仅节奏放慢，学生的讨论和交流也会停滞，或者说他们的讨论与交流就只能是蜻蜓点水或不找边际。如此以来课堂势必低效，无效。在这种情况下，预习的重要性凸现，它是课堂学习的铺垫，能为高质量的教与学打好基础。让学生做有效预习，才能确保新课改下课堂教学的高效率。三、以饱满的情感投入课堂（一）以饱满的热情激发学生的积极情感。情感是人类心理活动的一个组成部分，在课堂上，师生之间离不开情感的交流。实践证明，教师将积极向上的美好的情感运用到教学中，可以优化课堂效果。在语文课上，教师的情绪会直接影响着学生，教师一定要乐观、热情、饱满、自信。（二）借助形象和激情的体态语言来增强表达效果。每个学生都喜欢脸部表情丰富的教师，教师上课时脸带微笑，可以使学生能消除紧张、不安等感觉。此外，教师的手势也很重要。作为一名语文教师，手势语尤其重要，学生可以通过你的身体动作来猜测并理解你说的语文。实践证明，表情、动作丰富的语文教师教学效果明显要好得多。（三）与学生进行情感交融。在课堂上，教师要充分尊重学生，适时给予鼓励，一个微笑、一个赞赏的眼神、一个小小的表扬，都会让学生的心里开花，更乐于表现，更乐于参与，让课堂有理想的教学效果。四、积极运用“自主、合作、探究”的教学方式人本主义教育家罗杰斯认为：学生是知识意义的主动构建者，而不是外部刺激的被动接受者，只有通过自身体验和合作对话等方式，学生才能真正完成真正意义的构建。所以，教师的课堂教学要给学生自主学习的空间，教师不替学生说学生能说的话，不替学生做学生能做的事。教师要做的是指明方向，让他们去寻找，探索。我认为“小组合作学习”这一模式不仅可以使师生之间、学生之间更有效地进行语言交流，而且还可以培养学生的合作意识、团队精神，小组合作学习更能突出学生的主体地位，培养主动参与的意识，能为学生提供一个较为轻松的环境。现在，许多学校采用小组教学，改变了传统教学中师生之间单向或双向的交流模式，形成师生、学生与学生之间的全方位、多层次、多角度的交流模式，使小组中每个人都有机会发表自己的观点与看法，也乐于倾听他人的意见，也学会了借助他人力量成就自己。但让小组的合作真正动起来还真不容易。受家庭教育、社会环境的影响，一个班能专心学习的同学大多屈指可数，搞小动作、说话、出神、发呆、需要老师提醒两三次的的往往不下十几个。这样以来，合作学习不但达不到学生共同提高的目的，而且让学生形成了随随便便的习惯。因此，我们语文老师要提高学生学习语文的兴趣，吸引他们的注意力，努力让所有的学生思维一步步跟着老师的引导走，说思考就思考，说讨论就讨论。其次，教给学生讨论的方法，指导学生分工要具体，讨论时，不急于发言，要先思考，争取给每个学生发言的机会，鼓励学生不怕出错，勇于表达自己的见解。五、运用多媒体教学为高效课堂插上翅膀一位苏联教育家曾说，有趣味、有吸引力的东西使识记的可能性几乎增加一倍。在今天的语文课中，多媒体教学正以其特有的形象性、生动性、丰富性显示了独特魅力，能激发学生兴趣，产生强烈学习愿望，从而产生学习动机。由于语文本身蕴涵着丰富的情感，或豪迈或婉约，或赞扬或激励。所以，我们可以利用多媒体辅助教学，创设视听情境，营造特定氛围，激发学生的内在情感，把认知活动和情感活动很好地结合起来。这种以声音、图形创设课堂情境，代替枯燥乏味的口讲，大大激发学生兴趣，提高了课堂效率。总之，有利于学生身心发展的课堂才是真正有效的课堂，提高语文课堂教学实效性的途径，也远非上述的几点，它涉及到各个方面，既有教师因素，也有学生方面的影响，还有各种教学环境的制约。随着教学改革如火如荼的推进，随着教学新理念的深入人心，语文教学的课堂有效性将会日益凸显。作为新课程改革下的教师，我们应当不断地学习和反思，探索和改进，真正达到语文课堂教学的实效，进而提高语文课堂教学质量。1.任务驱动教学法的基本特征1.1学习活动是在课前设计好的任务中展开。信息技术课程作为实践性、应用性很强的学科，主要任务是培养学生良好的信息素养。在任务驱动教学法中，学习要学习的知识并非教师直接传授，而是隐藏在任务中，学生对教师分配的任务分析研究，明确完成任务时需要使用哪些知识解决任务中分配的问题，在教师的引导和帮助下，学会新知识，完成任务。1.2注重学生自学能力的培养。任务驱动的关键是让学生通过对问题的分析和解决来获取知识的过程，而并非传统的被动接受的过程，在整个完成任务的过程中，学生是任务的主体，只有积极主动的探究问题，分析问题及解决问题，才能高效的完成任务，因此在一定程度上能够提高学生的自主学习意识和自学能力。1.3问题涉及知识面广。任务驱动教学法涉及的知识和传统的知识结构体系具有较大的差别，是让学生根据教师所分配的任务围绕自主学习来进行的，因此教师在制定任务时，既要将新知识贯穿在其中，又要有旧知识做铺垫，将新旧知识有效的融合在一起，即符合教学目标，又能提高学生总结知识的能力，形成开放的学习过程。2.任务驱动教学法的应用步骤2.1学习任务的设计。任务驱动教学法的前提是任务的设计，它要求教师对于整个教学内容有深入的了解，并且针对学生的特点进行任务的设计。任务的设计要分层次，可以分为易中难三个层级：容易的是教学内容的模仿，其重点是练习；一般的任务设计要使部分学生能够发挥自己的想象力进行创作设计；有难度的任务设计则是完全留给学生空间，使其能够充分涉猎多方面知识完全凭学生创作。比如，教师给学生一个相册设计任务，就可以将这个任务分成三个阶段，第一完全按照老师给出的模板，包括图案、文字、排版等等格式进行设计，这考察学生对于基础知识的应用；第二，老师只是给出基本要求，明确相册的基本模板，剩余的文字、图案风格等等都可以由学生自由发挥；第三，老师只提出一个相册设计的任务，其他的都由学生自己完成，这样学生可以抛弃原有的束缚，完全改变相册的模式，可以添加FLASH动画，可以变换相册的播放形式，可以添加背景音乐等等，这样就将学生思维完全的放开，并且让他们从多个方面进行了知识的学习，提高了其自学的能力。2.2学习任务的布置与分析。在教学过程中学习任务的布置并不能像原来布置课后作业那样进行硬性的安排，它需要将任务融合在学生感兴趣并且真实的情景中，再者任务布置完成后，要对任务进行分析，明确里面的知识点。在布置任务的同时，教师要在课堂上创作相关的教学情景，可以通过图片、声音以及视频等方式来展示任务中的重点和难点。比如在布置图层应用这一章节任务：如何制作两架飞机在天空飞翔的效果。我们就可以给学生播放这样的视频情景：在偷袭珍珠港战役中，日军飞机在珍珠港上空盘旋，并不停投弹。此时，我们可以提示学生图层相关知识的运用。3.任务驱动法教学过程要注意事项3.1目标明确，精心创设问题情境。要让学生快速投入到任务中去，情境的创设极为重要，情境设计的好坏直接影响着学生参与的积极性，影响着课堂教学效果，教师要从教学内容和社会实践出发，深挖教材，创造合适的问题情境，使学生能够主动、积极的投入其中。3.2设计关键，注重任务的设计。在初中信息技术教育中，采用任务驱动教学法具有更加明确的教学目标和能力目标。首先，教师要根据任务驱动教学法的基本特点，挖掘和强化技能点，培养学生的分析问题的能力；其次，教师要根据关键知识点重视精讲多练，突出重点问题的解决；第三，将任务重所涉及的各种技能串成线，培养学生运用所学知识解决实际问题的能力。3.3导体和谐，处理好师生关系。任务驱动教学法的核心是教师为主导，学生为主题，积极发挥学生的主观能动性。在这种教学模式中，教师是任务的提出者和引导者，学生是任务的分析者和解决者。教师的主要任务是创设良好的情景，设计好科学合理的教学任务，引导学生独立完成学习的过程；学生是任务的完成者，教师要及时对学生进行指导和鼓励，两者平等相处，互相交流，共同提高。以上是我对初中信息技术教学模式改革的尝试，其中必然会存在很多问题，但它们是通过改进教学方法有力的依据，必然会逐渐的完善与成熟。第16章树第十六章树、无向树1)定义:连通无回路(初级回路或简单回路)的无向图称为无向树,或简称树常用T表示树,平凡图称为平凡树若无向图G至少有两个连通分支,则称G为森林在无向树中,悬挂顶点称为树叶,度数大于或等于2的顶点称为分支结点2)树的等价定义B>是n阶条边的无向图则下面各命题是等价的(1)G是连通无回路(树)可通过循环证明(2)G中任意两个顶点之间存在惟一的路径(连通则存在路径,若不唯一,不同路径则构成回路)(3)G中无回路且m=n-1有长大于等于2的回路都与唯一路径矛盾对结点进行归纳:n=1平凡图m=0=n-1;设n=k成立;n=k+1时两个结点有唯一的路,去掉则为两个连通分支(各自满足假设)m=m1+m2+1=n1-1+n2-1+1=n1+n2-1=n-1(4)G是连通的且m=n-1若不连通,对各个(s>=2)连通分支是树且有mi=ni-1皿=n-8s>=2矛盾(5)G中没有回路,但在任何两个不同的顶点之间加一条新边,在所得图中得到惟一的一个含新边的初级回路(6)G是连通的,但删去任何一条边后,所得图不连通G连通:若存在二个结点无通路,则在二个结点添加边后不会出现回路3)树的性质对于给定的无向图一树是边数最小的连通图(m<n-1则不连通)树是边数最多的无回路图(m>n-1则有回路)结点的度:∑d(vi)=2m=2(n-1)定理:设T是n阶非平凡的无向树,则T中至少有片树叶设:有x片树叶,其余结点度数至少为2x+2(n-x)<=2(n-1)例:无向树T中度为4、3、2的结点各一个,其余为树叶,树叶=?4+3+2+k=2(3+k-1)4)阶数n比较小的所有非同构的无向树例1:画出6阶所有非同构的无向树m=n-1=5从树的节点之和来分析:结点之和为10分配给6个结点111115111124111133111223112222例2:7阶无向树中有3片树叶和1个3度顶点,其余3个顶点的度数均无1和3.试画出满足要求的所有非同构的无向树解答:从树的节点之和来分析:7阶无向树的边数m于是∑d(vi)=12=3+3+d(v5)+d(v6)+d(v7)1112223加入2,2,2如何组成结点的度数序列使之不同构主要分析:度为3的结点v与其三个邻接点的关系邻接关系不同就能得到不同构的树三个邻接点度数:11216.2生成树(一些连通图不是树,但它的子图是树——重要的是生成树)1、定义:设T是无向图G的子图并且为树,则称T为G的树若T是G的树且为生成子图,则称T是G的生成树设T是G的生成树,ve∈E(G),若e∈E(T),则称e为T的树枝,否则称e为T的弦.并称导出子图G[E(G)-E(T]为T的余树,记作T注:T不一定连通,也不一定不含回路.(无规律)生成树的性质1)定理:无向图G具有生成树当且仅当G是连通图(破圈法-不断去掉回路)2)设G为n阶m条边的无向连通图,则皿=E(G)≥|E(T)|=n-1.3)设G是n阶m条边的无向连通图,T为G的生成树,则T的余树T中含m-n+1条边(即T有m-n+1条弦)4)任何无向连通图G,都存在生成树无向连通图G的生成树是不唯一的实边图为该图的一棵生成树T,余树T为虚边所示,它不连通,同时也含回路3、生成树的应用要建6个工厂,修建连接的通路(见图),为使5处都有路相通,至少要建几条路?如何铺设?由于n=6所以建5条路即可4、无向图G的生成树的确定二种方法:1