高中数学联赛之历年真题汇编(1981-2020)专题30图论与对策(解析版)_第1页
高中数学联赛之历年真题汇编(1981-2020)专题30图论与对策(解析版)_第2页
高中数学联赛之历年真题汇编(1981-2020)专题30图论与对策(解析版)_第3页
高中数学联赛之历年真题汇编(1981-2020)专题30图论与对策(解析版)_第4页
高中数学联赛之历年真题汇编(1981-2020)专题30图论与对策(解析版)_第5页
已阅读5页，还剩38页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、第第 页共42 25(14+6四(病+27。22+ 22 575(14 + 6V5)(V5 + 2)455=(70 行 + 150)(9 + 45)20115 300 x 17=011S20.在次数学竞赛中，某些选手是朋友关系.记所有选手的集合为X,对集合X的夕集Y,若可以将这些人两 两分组，且每组中两名选手均是朋友关系，则称集Y ”可两两分组”.已知集合X不可两两分组，且对于任意 选手力、BWX,若A、B不是朋友关系，则XAB可两两分组，且X中没有个人与其他所有人均为朋友关系 证明：对任意选手* b、CSX，若a、b为朋友关系，b、c为朋友关系，则a、c也为朋友关系【答案】见解析【解析】考虑

2、个图G,顶点由集合X组成，若X中两人认识，则将这两人相连，否则不相连若个图中的点可以两两分 组，且每组中两个点均相连，则称这种分组为图G的个“完美匹配”(可以看成是图G的个子图).于是， 题目的条件变成了图G不存在完美匹配，且若x、y不相连，则G+xy (表示把这个图G的xy也相连)存在个 完美匹配，且没有个点与所有点均相连.用反证法.若存在a、b、c使得a、b认识，b、c认识，但a、c不认识，由于没有人认识其他所有人，故存在dWx,使得 b、d不认识.由假设可得G+ac有个完美匹配，记为3；G+bd也有个完美匹配记为F厂 考虑巳与己的对称差5 = F/Fz = FUE F1AE:-则容易得到S是一些互不相交的圈，且每个圈均由偶数个点组成，设ac属于圈G，bd属于圈分两种情形讨论若如去心，则在圈G外的点按照A的分组方式分组，在圈G中按照F二的分组方式即可得到原图G的个完美匹 配，即得矛盾.若6 = ,则这个圈从b出发沿边bd开始，不妨设首先连到点a,即b到a的路径(首先经过边bd)为P,于 是，P+ab为个圈，其中，有半的边(间隔地)属于F二对P+ab这个圈外的点按F2的

人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论