数学竞赛中的图论问题-6（p.doc

2-6数学竞赛中的图论问题（P．221） 一、基本思想 引例欧拉7桥问题 把所考察的对象作为顶点（v），把对象之间是否具有我们所关心的某种关系作为了连线的的条件（e），这样，就可以把一个具体问题抽象为图的研究． 在解数学竞赛题中的好处： （1）把抽象的问题转化为直观的问题； （2）把复杂的逻辑关系转化为简明的数量关系． 二、基本内容 有图、顶点、边、简单图、完全图、连通图、树、二分图、竞赛图等14个定义，12条定理： 定义１ 设集合，是中某些元素对的无序集合，则称为图，又称为图的顶点集合，其元素叫做顶点；称图的边集合，其元素叫做边．若，边是无序顶点对，则记，且称与是边的端点，与顶点关联，也说顶点与邻接（或相邻）．有公共端点的边称为邻边，也说邻接． 例如 顶点：=｛小王，小李，小张，小赵，小陈，小刘｝， 边：=｛小王，小李｝，=｛小李，小赵｝，=｛小陈，小刘｝ ， 相邻. 定义2 图中所含顶点的数目称为图的阶数，记为（也用来表示）；又用表示图的边数（也用来表示）．通常用表示个顶点，条边的图；若都是有限数的图称为有限图，否则称为无限图．如果对于图与，有，则称是的子图． 定义3 两顶点间至多连一条边且每边的两个端点相异的图称为简单图；图中任何两个顶点都邻接的简单图称为完全图，阶完全图记为 定理1 的边数为． 定义４ 图中与顶点关联的边数称为顶点的度，记为．如果的度数是奇数，则称为奇顶点；如果的度数是偶数，则称为偶顶点． 定理２ 任何一个图的总度数等于边数的2倍， ． 推论 任何图中奇顶点的个数是偶数． 定义５ 图中点边交错的非空有限序列叫做以为端点的途径．若途径中所有的都不相同，则叫做链；若链中所有的都不相同则叫做通路，称为通路的长；若重合，则叫做回路或圈．为奇（偶）数的回路称为奇（偶）回路． 定义６ 经过图中每条边的链称为欧拉链，两端重合的欧拉链称为欧拉环游图（欧拉回路），有欧拉环游的图称为欧拉图（简称图） 直观的说，欧拉图就是从一个顶点出发而每边通过一次又能回到出发顶点的图（一笔画）． 定理3 连通图为欧拉图的充要条件是中没有奇顶点． 推论 如果连通图有2个奇顶点，那么图可以用笔画成． 定义７ 包含图每一个顶点的通路称为哈密尔顿通路，有哈密尔顿通路的图称为哈密尔顿图． 定理4 设是一个阶简单图，若中任意两个顶点的度数满足，则是哈密尔顿图． 定义８ 连通而无回路的图称为树，树上度数为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阶完全图，图中