奥数系列讲座——
温馨提示
为了设计教学场景互动效果的需要，课件中采用了大量“播放后隐藏”的文本，从而导致预览模式下出现诸多文本重叠，影响阅读。但在放映模式下，这些现象都不会出现。
另外，课件中的图像均不是一次性形成，而是展现了“尝试-修改-成形”等发生过程，这可能导致预览模式下出现诸多乱码，但在放映模式下，图形则非常生动、美观。
【百度文库】跃峰奥数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(边分析)
