PPT4
- 格式:ppt
- 大小:1.23 MB
- 文档页数:15
温馨提示为了设计教学场景互动效果的需要,课件中采用了大量“播放后隐藏”的文本,从而导致预览模式下出现诸多文本重叠,影响阅读。
但在放映模式下,这些现象都不会出现。
另外,课件中的图像均不是一次性形成,而是展现了“尝试-修改-成形”等发生过程,这可能导致预览模式下出现诸多乱码,但在放映模式下,图形则非常生动、美观。
图论方法4-1(完全图有向图之局部扩展)●冯跃峰本讲内容本节为第4板块(图论方法)第4专题(完全图有向图)的第1小节(局部扩展),包含如下3个部分内容:第一部分,概述问题涉及的知识方法体系;第二部分,思维过程剖析。
这是课件的核心部分,重在发掘问题特征,分析如何找到解题方法。
按照教师场景授课互动效果设计,立足于启发思维;第三部分,详细解答展示。
提供笔者重新书写的解答(简称“新写”),力求严谨、流畅、简练。
【图论方法(完全图、有向图)】所谓“完全图”,就是任何点都连边的图;所谓“有向图”,就是给每条边标注了一个方向。
特别地,一个图是完全图又是有向图,则称为“竞赛图”。
它们包括三种常见的思路:三种思路局部扩展从一点或边出发,逐步扩充为完全图反面剔除去掉若干引出虚边的点,使不再有虚边,得到完全图考察极端本节介绍“局部扩展”在特定范围内取某种容量最大的图或考察元素的极端分布。
【图论4-1】给定2016阶图G,若G中不含K6,求G中点的最小度的最大值。
【题感】从目标看【1】,属于双重最值问题,需要得到“最小度d”的上界估计:d≤c。
但无法由条件“不含K6” 建立算法【1】,只能先构造一个合乎要求的图G,使“最小度”尽可能大,进而猜出最大值。
从条件看,“不含K6”,等价于“G中任何6点必有2点不相连”。
它有明显的“抽屉影子”:任何6点必有2个点在同一抽屉(抽屉质量为虚边完全图),于是应构造5-部分图。
此外,为了使“最小度d”尽可能大,各部分容量应尽量接近,且尽可能多地连边,于是构造5部分完全图即可■。
【注】此为简要版,省略了第2部分:发掘解题方法的详细思维探索过程。