好文档 - 专业文书写作范文服务资料分享网站

跃峰奥数PPT4图论方法2-2(边分析)

天下 分享 时间: 加入收藏 我要投稿 点赞

奥数系列讲座——

温馨提示

为了设计教学场景互动效果的需要,课件中采用了大量“播放后隐藏”的文本,从而导致预览模式下出现诸多文本重叠,影响阅读。但在放映模式下,这些现象都不会出现。

另外,课件中的图像均不是一次性形成,而是展现了“尝试-修改-成形”等发生过程,这可能导致预览模式下出现诸多乱码,但在放映模式下,图形则非常生动、美观。

【百度文库】跃峰奥数PPT经典原创

奥数系列讲座——

图论方法2-2(边分析)

●冯跃峰

本讲内容

本节为第4板块(图论方法)第2专题(边分析)的第2小节,包含如下3个部分内容:

第一部分,概述问题涉及的知识方法体系;

第二部分,思维过程剖析。这是课件的核心部分,重在发掘问题特征,分析如何找到解题方法。按照教师场景授课互动效果设计,立足于启发思维;

第三部分,详细解答展示。提供笔者重新书写的解答(简称“新写”),力求严谨、流畅、简练。

【百度文库】跃峰奥数PPT经典原创

图论方法2(边分析)

通过分析图中的一些边的性质,找到解题的突破口,我们称之为“边分析”。包括如下3个方面:估计边的总数||G||,包括整体估计、邻域分块等添加边(饱和图)去掉边(稀疏等)压缩边(减容图)讨论某些点之间连边还是不连边(实边、虚边),沿边前进等■。【百度文库】跃峰奥数PPT经典原创

边数三种分析方法

边操作边性态【图论2-2】将2015阶完全图G的每条边染红蓝两色之一,对于G的顶点集V的任意一个二元子集{u,v},定义L(u,v)={u,v}∪{w∈V|△uvw中恰有两条红边}。试证:当{u,v}遍取V的所有二元子集时,至少可以得到120个不同的集合L(u,v)。(2015中国国家队选拔考试第5题)

从目标看,本质上属于构造问题【1】。这常可采用“以简驭繁”的策略:取形式最简单的120个数对(u,v)产生120个点集L(u,v)。但可能有重复,需要适当优化,使各【题感】从条件看,先要理解LL集互异。(u,v)的定义:——L(u,v)是一个点集,它包括两部分。一部分是u、v两点;另一部分是那样一些点w【1】:△uvw恰有两条红边。为叙述问题方便,可引入定义:称恰有2条红边的三角形为好三角形。这样,L(u,v)就是所有与u、v构成好三角形的点和u、v组成的点集。由此可见,应从反面验证L集的互异性。基本思路是:【百度文库】跃峰奥数PPT

【以简驭繁】形式最简单的互异数对是:(u,vi)(固定一个分量,另一分量vi跑遍其它点),然后优化,使之满足:L(u,vi)≠L(u,vj)。

【反面思考】反设L(u,vi)=L(u,vj)(vi≠vj),由vi∈L(u,vi),得vi∈L(u,vj),所以△uvivj是好的(有用信息)。如前述,L集的互异性采用“反面思考”的推【充分条件】“△uvivj不是好的”的一个充分条件是:它有两条蓝边。往前追索:理模式。这只需图中有120条蓝边uvi(1≤i≤120)。u【邻域分块】取定一个点u【1】,令:我们只需适当选择点v1,v2,…,v120,使其能破坏上述P={p|pu为蓝边}【1】,优化Q={q|qu为红边}【1】。性质:即任何△uvivj不是好的,这找一个充分条件即可。p1【充分条件分类】如果|P|≥120【1】,则qtp2L(u,v)≠L(由此可见,当所有边uv(1≤i≤120)都是蓝色时,u,v)。…iij…取P中120个点pi(1≤i≤120),由上面的q2psq1讨论可知,L(u,pi)互不相同,结论成P≥120<120由此想到图论中“邻域分块”技巧。Q≥…立。【百度文库】下设|P|<120【1】,此时|Q|较大【1】,自然想到让第二分量v跑遍Q中元素【1】:即跃峰奥数PPT考察所有L(u,qi)。经典原创■。期望有120个L是互异的,又以此为标准进行分类

跃峰奥数PPT4图论方法2-2(边分析)

奥数系列讲座——温馨提示为了设计教学场景互动效果的需要,课件中采用了大量“播放后隐藏”的文本,从而导致预览模式下出现诸多文本重叠,影响阅读。但在放映模式下,这些现象都不会出现。另外,课件中的图像均不是一次性形成,而是展现了“尝试-修改-成形”等发生过程,这可能导致预览模式下出现诸多乱码,但在放映模式下,图形则非常生动、美观。【百度文库】
推荐度:
点击下载文档文档为doc格式
5xse68bh2j1xep036fj71ujtp7zr5k019ha
领取福利

微信扫码领取福利

微信扫码分享