统筹法与图论初步

国家高中数学课程标准正在研究的15个课题编者按：国家高中数学课程标准正在制订。

一个以“课程标准”为主题的高级研讨班己在南京举行。

为了集思广益，我们征得有关方面同意，将正在研究的15个课题内容在此发表，供关心中国未来课程发展的同志参考。

1、高中数学的选择性高中数学课程是否要有选择性，意见差异很大。

一种意见是应当文理兼通，数学不分文理。

前几年高考数学文理分卷的做法被认为不合适，某些地方己决定文理全卷。

另一种意见则相反，高中阶段应当有更大的选择空间。

一部分喜欢数学的学生，应该学得比现在课程中的数学多得多，而另一部分需要数学相对少的专业，则不必学得那么多（例如某些艺术类、高等职业类）。

文科类、一般理工类、数理科学类的学生，所要求的数学不应该是一样的。

从国际比较来看，绝大多数国家的高中数学都设置了多种选修系列。

日本高中实行学分制。

学生毕业的数学学分，从3学分到18不等，差异很大。

2、信息技术在高中课程中的位置及其作用众所周知，中国要想在科学技术领域与当今世界发达国家一较高下，必须充分发展信息技术。

这使得信息技术进入整个高中数学课程己是必然。

如何依据国家的相关需求与发展趋势，明确信息技术在未来高中数学课程中的地位与作用，将是该课题研究的主要任务。

具体内容凶手：从学生数学学习的角度不看，信息技术的意义究竟是什么；哪些信息技术可以（必须）进入高中数学课堂；科学计算器、图形计算器和CBL、计算机、网络？由于相关信息技术的介入，函数、几何、微积分、数据处理等内容将做相应的调整，有哪些需要调整、如何调整？更进一步，信息技术的介入，特别是一网以后将对学生学数学和教师教数学的方式产生什么样的影响？3、算法内容的设计与安排算法，是古代中国数学的一大特色，也是现代数学发展的一个重要方向随着计算机技术的迅猛发展，诸如排序算法、图论中的算法、无限的迭代算法等等，己为当代数学教育所密切关注。

遗憾的是，中国数学教育对此尚缺乏应有的重视。

图论初步华中师大一附中陈开懋★基础知识★一、图由若干个不同的顶点与连接其中某些顶点的边所组成的图形叫做图。

用G 表示图，用V 表示所有顶点的集合，E 表示所有边的集合，并且记作G=（V ，E ）．||V p =称为G 的阶.二、简单图与完全图（1）若在一个图G 中的两个顶点j i v v 与之间有边e 相连，则称点j i v v 与是相邻的，否则就称j i v v 与是不相邻的．（2）如果顶点v 是边e 的一个端点，称点v 与边e 是相邻的．（3）如果顶点本身也有边相连，这样的边称为环．如果连接两个顶点的边可能不止一条，若两个顶点之间有k )2k (≥条边相连，则称这些边为重边（或平行边）．（4）如果一个图没有环，并且没有重边，这样的图称为简单图．竞赛中的图论问题涉及到的图一般都是简单图．（5）如果一个简单图中，每两个顶点之间都有一条边，这样的图称为完全图，通常将有n 个顶点的完全图记为n K ．（6）在图G=(V,E)中，顶点个数|V|和边数|E|都是有限的，则称图G 是有限图；如果|V|或|E|是无限的，则称G 为无限图．三、顶点的度设G 是n 阶图，它的顶点集合为},,,{21n v v v V =，与顶点),3,2,1( =i v i 相关联的边的条数叫做顶点i v 的度，记作)(i v d ；若顶点i v 的度)(i v d 为奇数，则称顶点i v 为奇顶点，若顶点i v 的度)(i v d 为偶数，则称顶点i v 为偶顶点.与度相关的定理：定理（握手定理）：n 阶图G 中所有顶点的度之和是它的边数的两倍，即有1()2||n i i d v E ==∑推论：任何图G 的奇顶点个数必为偶数.四、连通图与树在图G 中，一个有不同的边组成的序列：121,,,;m i i i e e e e A A -= 如果其中边，01,2,,m i m A A = ，则称这个序列是从到的链。

数m 称为这条连长.0m A A 与称为这条链的端点，并且这条链记为01m A A A .如果一条链的两个端点0m A A 与重合，称这条链为圈。

【最新精选】统筹学资料统筹方法所谓统筹，就是在面临多个任务时，通过重组、优化等手段合理安排工作(管理)流程，提升工作(管理)效率的一种思想与方法。

完成任务总是需要消耗一些资源，如时间、金钱、信息等，下面所附的华罗庚的《统筹方法》一文中举的是时间的例子，其实统筹方法还可以扩展到其他很多领域。

比如，金钱或是其他需消耗的物质资源以及信息等。

统筹方法提供给我们一种解决复杂问题的方案，其本质上是一种安排工作进程的数学方法，应用的关键是抓住主要环节，合并次要环节，这样可以帮助我们缩短工时，提高工作效率。

因此我们必须时时思考，深入理解，仔细体会其中的数学思维，才能使我们无论是在安排庞大复杂的系统相互协作这样的事情上，还是生活中一些琐碎的小事中，都能最有效的利用资源。

资源的优化配置可以采用项目管理中的网络技术、运筹学中的博弈论、排序模型、网络优化模型等方法或是这些方法的有机集成，这些方法构成了资源优化配置的系统方法。

华罗庚是我国最早把数学理论研究和生产实践紧密结合作出巨大贡献的科学家。

从五十年代末期开始，他就走出书斋和课堂，来到广阔的工农业生产实践之中。

他把数学方法创造性地应用于国民经济领域，筛选出了以改进生产工艺和提高质量为内容的“优选法”和处理生产组织与管理问题为内容的“统筹法”(简称“双法”)，并用深入浅出的语言写出了《优选法平话及其补充》和《统筹法平话及补充》两本科普读物。

附: 《统筹方法》——华罗庚统筹方法，是一种安排工作进程的数学方法。

它的实用范围极广泛，在企业管理和基本建设中，以及关系复杂的科研项目的组织与管理中，都可以应用。

怎样应用呢,主要是把工序安排好。

比如，想泡壶茶喝。

当时的情况是:开水没有;水壶要洗，茶壶茶杯要洗;火生了，茶叶也有了。

怎么办,办法甲:洗好水壶，灌上凉水，放在火上;在等待水开的时间里，洗茶壶、洗茶杯、拿茶叶;等水开了，泡茶喝。

办法乙:先做好一些准备工作，洗水壶，洗茶壶茶杯，拿茶叶;一切就绪，灌水烧水;坐待水开了泡茶喝。

1. 统筹问题实例与统筹图-湘教版选修4-8统筹法与图论初步教案一、学习目标1.了解统筹问题的定义及实例；2.掌握画统筹图的方法；3.能够通过统筹图解决实际问题。

二、知识概述1. 统筹问题实例统筹问题是指在多种资源之间进行协调和平衡，以获得最佳的效益和利用效率的问题。

在实际生活中，有很多问题需要采取统筹的思路来解决。

下面是两个统筹问题的实例：实例1小李家住在城市的东边，他每天都要去市中心上班，而去市中心只有两条路可选：第一条路长，但是路面宽阔，车辆流畅；第二条路短，但是路面狭窄，车辆拥堵。

于是小李在选择路线时需要进行权衡，采取什么样的策略才能在时间和安全上得到平衡呢？实例2某个工厂的管理人员需要决定如何分配生产资源，以便达到最优效益。

但是该工厂生产的产品样式多种多样，每种产品的生产资源需求都不同。

为了使最终产生的产品种类搭配合理、利润最大化，管理人员需要进行资源配置方案的制定，这也是一个典型的统筹问题。

2. 统筹图统筹图是一种用图表和标志来表示调度问题的图形方法，也是求解统筹问题的重要工具。

统筹图由一个方框和若干条箭头组成，箭头上标有数字和符号，代表着一条任务的开始时间、结束时间、所需资源以及其他限制条件。

统筹图能够清晰地展现任务之间的依赖关系和资源需求情况，为调度和分配资源提供了有效的依据。

下面是一个简单的统筹图示例：┌──────────────┬─────────┬─────────┬─────────┬───┐│ 任务│ 资源需求│ 开始时间│ 结束时间│说明│├──────────────┼─────────┼─────────┼─────────┼───┤│ 任务1 │ 2 │ 0 │ 4 │ │├──────────────┼─────────┼─────────┼─────────┼───┤│ 任务2 │ 1 │ 4 │ 5 │ │├──────────────┼─────────┼─────────┼─────────┼───┤│ 任务3 │ 3 │ 5 │ 8 │ │└──────────────┴─────────┴─────────┴─────────┴───┘三、教学重点与难点教学重点：掌握画统筹图的方法。

统筹法与图论初步统筹法是运筹学中的一个基本方法,是现代项目管理理论中最重要的方法之一。

本专题将通过实例介绍统筹法及其应用,同时介绍图的基本概念,给出图上最短路和最小生成树算法,使学生对图论及其应用有一初步了解。

内容与要求1. 统筹方法(1)通过实例了解统筹问题的思想及其应用的广泛性。

(2)通过实例理解统筹法中的基本概念。

(3)通过实例掌握绘制统筹图的方法。

(4)学会计算统筹图中的参数:事项最早开始时间和最迟到达时间,工序的时差。

(5)学会寻找统筹图的关键路,掌握寻找关键路的算法,理解关键路的重要性。

(6)会用统筹方法分析和处理简单的实际问题。

2. 图论初步(1)通过实例了解图的基本概念和图在刻画实际问题中关系的作用。

(2)通过实例了解图的生成树,掌握求图的生成树和最小生成树的算法。

(3)通过实例了解图的最短路问题,掌握求图的最短路的算法。

(4)了解一些图论的其他问题,并知道算法的复杂性。

3. 完成一个学习总结报告。

报告应包括三方面的内容:(1)知识的总结。

对本专题的内容或部分内容(统筹法或图论)的整体思路、结构的理解,对其中蕴涵的数学思想方法的认识。

(2)拓展。

通过查阅资料、调查研究、访问求教、独立思考,对某些内容、某些结果和应用进行拓展和深入。

(3)对本专题的感受、体会、看法。

说明与建议1. 统筹法是一个应用十分广泛的方法,在学习时不仅要求学生掌握该方法,还应培养学生的应用意识,即让学生结合自己的生活实际,有意识地收集可以应用该方法的实际问题。

2. 应让学生认识到,在解决实际问题时,可能会出现各种复杂因素(如时间的随机性、成本的变动、人力的调动等),一些现成的方法可能不能完全适用,需要结合其他数学工具来进行处理。

3. 在图论初步的教学中,一方面应让学生认识到图和网络是许多实际问题的重要数学模型,认识到研究它们的重要性;另一方面,本专题侧重介绍一些算法,要求学生能清楚地表述这些算法,同时能对算法的复杂性问题有所了解。

统筹图画法中的技巧简介统筹图是一种图形表达方式，用于描述复杂的系统以及其中的相关组件和关系。

在湘教版选修4-8统筹法与图论初步教案中，学生学习到了统筹图的绘制方法和使用技巧。

本文将介绍统筹图画法中的一些常见技巧，帮助读者更好地理解和使用统筹图。

统筹图基本概念回顾在介绍具体的统筹图画法技巧之前，我们先回顾一下统筹图的基本概念。

统筹图通常是由若干个节点和边组成的图形，其中：•节点代表一个实体或组件，比如一个部门、一个产品、一条生产线等；•边则表示不同实体之间的关系，比如流程、依赖关系等。

统筹图可以用来描述复杂系统的组件和关系，例如工厂的各个部门和生产流程、软件系统的各个模块和相互依赖关系等。

统筹图的绘制需要注意以下几点：1.对于一个系统，如何将它分解成若干个组件？2.每个组件如何表达？3.组件之间的关系如何表达？在实际使用中，我们需要明确统筹图的目的和应用场景，并根据需要合理选择统筹图的表现形式。

统筹图的画法技巧基础技巧在绘制统筹图时，我们需要掌握一些基础的技巧：1.绘制网格线：将画布按照比例分割为网格，可以更好地保证绘制出来的统筹图规范、美观；2.统一节点样式：对于同一类节点，保持节点样式的一致性，可以有助于读者更好地理解图中的信息；3.使用节点图标：在节点上使用图标，可以更好地突出节点的特征；4.绘制节点标签：节点标签通常需要简明扼要地描述该节点的含义，帮助读者更好地理解图中的信息；5.使用节点颜色：不同颜色的节点可以用来表示不同的属性和状态，比如红色可以表示问题或风险，绿色可以表示良好状态等。

进阶技巧在掌握了基础技巧之后，我们可以尝试一些进阶技巧：1.绘制鱼骨图：鱼骨图是统筹图的一种，它可以用来表示一个问题的各个方面、各个环节，有助于深入分析问题；2.使用不同的连线：不同类型的连线可以用来表示不同类型的关系，比如实线表示顺序性、虚线表示可选性等；3.绘制分支结构：在一个节点下方绘制多个子节点，可以用来表示该节点的具体细节，也可以用来表示该节点的分支结构；4.使用动画和交互：在一些复杂的统筹图中，通过动画和交互可以更好地展示系统的运作过程和各个节点的关系。

3.染色-湘教版选修4-8统筹法与图论初步教案一、教学目标1.掌握图论中染色的概念和基本思路。

2.掌握树的最大独立集和最小顶点覆盖的概念、性质，以及它们与染色的关系。

3.能够应用染色理论、独立集和顶点覆盖的知识解决实际问题。

4.培养学生的逻辑思维和分析问题的能力。

二、教学内容及方法1. 染色1.概念：给定一个无向图G=(V, E)，用颜色对点集V进行染色，使得相邻的点颜色不同。

2.理论基础：颜色数，最小染色数等。

3.具体操作：四色定理。

4.解决实际问题：地图染色问题。

教学方法：讲授理论知识，进行实例讲解。

2. 树的最大独立集和最小顶点覆盖1.概念：最大独立集是指在图中任意两个顶点之间没有边相连的顶点集合中，包含顶点数最多的集合。

最小顶点覆盖则是指选取最少的顶点，使得每一条边都至少与其中一个顶点相关联。

2.性质：最大独立集和最小顶点覆盖互为补集关系。

3.应用：结合染色理论解决实际问题。

教学方法：讲授理论知识，进行实例讲解。

3. 统筹法1.概念：又称为“想象得出法”，通过一定的统筹思想来解决问题。

2.与染色的关系：可以用统筹法求解染色问题。

教学方法：通过例题讲解来引导学生理解统筹法。

4. 课堂练习1.实例分析：分析染色问题，并通过统筹法给出解决方法。

2.计算练习：计算树的最大独立集和最小顶点覆盖，以及染色问题。

教学方法：讲解实例，引导学生独立思考，通过计算练习检验学生掌握程度和解决问题的能力。

三、教学重点和难点教学重点1.染色理论和相关概念。

2.树的最大独立集和最小顶点覆盖的应用。

教学难点1.树的最大独立集和最小顶点覆盖的概念和性质。

2.如何将统筹法应用于解决染色问题。

四、教学反思本课主要讲授了染色、树的最大独立集和最小顶点覆盖的概念、性质和应用，以及统筹法在染色问题中的应用。

通过理论知识的讲解，结合实例分析和计算练习，能够使学生更好地掌握这些知识点，同时也能够培养学生的逻辑思维和分析问题的能力。

在教学实践中，需要注意引导学生进行思考和讨论，激发学生的学习兴趣和积极性。