- 1、本文档共11页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数学竞赛中的图论问题-6(p
2-6数学竞赛中的图论问题(P.221)
一、基本思想
引例欧拉7桥问题
把所考察的对象作为顶点(v),把对象之间是否具有我们所关心的某种关系作为了连线的的条件(e),这样,就可以把一个具体问题抽象为图的研究.
在解数学竞赛题中的好处:
(1)把抽象的问题转化为直观的问题;
(2)把复杂的逻辑关系转化为简明的数量关系.
二、基本内容
有图、顶点、边、简单图、完全图、连通图、树、二分图、竞赛图等14个定义,12条定理:
定义1 设集合,是中某些元素对的无序集合,则称为图,又称为图的顶点集合,其元素叫做顶点;称图的边集合,其元素叫做边.若,边是无序顶点对,则记,且称与是边的端点,与顶点关联,也说顶点与邻接(或相邻).有公共端点的边称为邻边,也说邻接.
例如
顶点:={小王,小李,小张,小赵,小陈,小刘},
边:={小王,小李},={小李,小赵},={小陈,小刘} ,
相邻.
定义2 图中所含顶点的数目称为图的阶数,记为(也用来表示);又用表示图的边数(也用来表示).通常用表示个顶点,条边的图;若都是有限数的图称为有限图,否则称为无限图.如果对于图与,有,则称是的子图.
定义3 两顶点间至多连一条边且每边的两个端点相异的图称为简单图;图中任何两个顶点都邻接的简单图称为完全图,阶完全图记为
定理1 的边数为.
定义4 图中与顶点关联的边数称为顶点的度,记为.如果的度数是奇数,则称为奇顶点;如果的度数是偶数,则称为偶顶点.
定理2 任何一个图的总度数等于边数的2倍,
.
推论 任何图中奇顶点的个数是偶数.
定义5 图中点边交错的非空有限序列叫做以为端点的途径.若途径中所有的都不相同,则叫做链;若链中所有的都不相同则叫做通路,称为通路的长;若重合,则叫做回路或圈.为奇(偶)数的回路称为奇(偶)回路.
定义6 经过图中每条边的链称为欧拉链,两端重合的欧拉链称为欧拉环游图(欧拉回路),有欧拉环游的图称为欧拉图(简称图)
直观的说,欧拉图就是从一个顶点出发而每边通过一次又能回到出发顶点的图(一笔画).
定理3 连通图为欧拉图的充要条件是中没有奇顶点.
推论 如果连通图有2个奇顶点,那么图可以用笔画成.
定义7 包含图每一个顶点的通路称为哈密尔顿通路,有哈密尔顿通路的图称为哈密尔顿图.
定理4 设是一个阶简单图,若中任意两个顶点的度数满足,则是哈密尔顿图.
定义8 连通而无回路的图称为树,树上度数为1的顶点称为叶(悬挂点).
定理5 如果树的顶点数不小于2,那么树上至少有两个叶.
定理6 设图有个顶点,条边,则下列说法彼此等价:
(1)是树;
(2)的任意两个顶点间有且仅有一条通路;
(3)连通,且;
(4)无回路,且;
(5)无回路,但连接任何两个非邻接顶点所得新图,有且仅有一个回路;
(6)连通,但舍弃任何一条边后便不连通.
定义9 图的顶点集若能分成两个非空子集,使得任何边的一个端点属于,另一个端点属于,则为二分图.
定理7 图为二分图的充要条件是不含奇回路.
定义10 设图为简单图,是的一个非空子集,若中任何两边都不相邻,则称为图的一个匹配(又称对集).若边之端点包括中一切顶点,则称为的一个完备匹配.中每一边的两个端点称为相配.
定义11 在图的边上用箭头标注出方向就得到一个有向图,称为定向.完全图的一个定向称为竞赛图.
定理8 每个竞赛图都有单向哈密尔顿通路.
定义12 若一个图可以画在平面上,使得任何两条边都不在非顶点处相交,则称图为平面图.图的边所包围的一个区域,其内部既不包含图的顶点,也不包含图的边,这样的区域为图的一个面.为了方便,把平面图的外部无限区域也作为一个面,称为外部面,其他面则称为图的内部面.
定理9 设是一个简单连通平面图,,面数为(包括外部面),则.
定理10 一个连通的平面简单图,若有个顶点条边,则.
定义13 用红蓝两种颜色对完全图的边任意染色,使每条边都染上某一种颜色,若总会出现红色边或蓝色边时,则记的最小值为,称为关于的拉姆赛数.
定理11
定义14 用种颜色对完全图的边任意染色,使每条边都染上某一种颜色,若总会出现同色三角时,则记的最小值为,简记为,称为拉塞姆数.
定理12 设是集合的任意分划,则存在一个,使中有方程的根.
三、主要方法
不是图论知识的直接套用,而是图论基本思想的常识应用.
构造法、
反证法
数学归纳法
抽屉原理
染色方法
极端原理
四、例题选讲
例1-1 有5个课外活动小组,每2个小组里有一个相同的同学,每个同学恰好在两个小组里出现,问这5个小组里共有多少个同学?
解 把小组对应为点,“每2个小组里有一个相同的同学”就连一条线,每两点都有连线;又由于“每个同学恰好在两个小组里出现”,故每两点都连且只连一条线,得5阶完全图,图中
文档评论(0)