tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 学科竞赛 >>

江苏省数学竞赛提优教案:第67讲


第 67 讲 图论问题(一) 本节主要内容是: 把一个具体问题用图形表示出来, 利用图形的直观性可能更有利于问 题的解决. 有关的一些概念:由若干个不同的点及连接其中某些点对的线所组成的图形就称为 图.图中的点的集合称为图的点集,记为 V:V={v1,v2,?,vn,?};图中的线的集合称 为图的线集(边的集合),记为 E:E={vivj}(vi,vj∈V).故一个图由其点集 V 和线集 E 所决 定,若用 G 表示图,则记为 G=G(V;E).含有 n 个点的图称为 n 阶图. 在一个图中,如果某点 v 共连了 k 条线,则说此点的“次数”(或“度数”)为 k,记为 degv=k.如果一个 p 阶图的每两个顶点间都连且只连了 1 条线, 则称该图为 p 阶完全图, 记 为 Kp. 若对每条线确定一个方向(即确定了线的两个端点中一个为“起点”,另一个为“终 点”.这时,线是点的“有序对”),则得到“有向图”;对有向图的一个顶点 v,degv=k, 若 v 是其中 n 条边的起点,m 条边的终点(m+n=k),则称 v 的出次为 n,入次为 m. 链:若在一个图 G=(V;E)中取 n+1 个顶点 v1、v2、?、vn+1,每两个相邻的顶点 vi、vi+1 间连有一条边 li,则边 l1,l2,?,ln 就称为从 v1 到 vn+1 的一条链.n 称为链的长度. A 类例题 例 1 ⑴证明任意的六人中一定有三个人互相认识或互不认识(约定甲认识乙就意味着乙 认识甲). ⑵ K6 的边染成红蓝两色,求证:其中必有两个三角形,其三边同色. 分析 ⑴ 以点表示人,连红、蓝两色的线分别表示“认识”与“不认识” ,问题转化成 图的问题.要会把题目的语言转译成图的语言: “三人互相认识”就表示三点间都连红线, “三人互不认识”就表示三点间都连蓝线.⑵ 考虑每个异色三角形的三个角,其中两个角 是异色角,而同色三角形的三个角都是同色角. 证明 ⑴ 用 6 个点 v1,v2,?,v6 表示这 6 个人,如果某两人相互认识,则在表示此二 人的点间连一条红线, 否则连一条蓝线. 于是问题转化为证明此 6 点间一定连出了三边均为 红色或蓝色的三角形. 在点 v1 连出的 5 条线中,由抽屉原理知,必有某色线连有 3 条或 3 条以上.不妨设红 线连了至少 3 条.设 v1 与 v2、v3、v4 连的红线.现考虑点 v2、v3、v4 连线的情况,如果此三 点间有任两点连的红线,则出现红色三角形(例如 v2v3 连红线,则 v1v2v3 是红色三角形),如 果这三点间都不连红线,则出现蓝色三角形(v2v3v4 是蓝色三角形).故证. ⑵ 考虑 K6 共连了 C6=15 条线,共得到 C6=20 个三角形.设第 i 个顶点连了 ri(0≤i≤ 5)条红线,5-ri 条蓝线.由于 ri(5-ri)≤6.所以,连出的异色角个数≤6×6=36 个.由 于每个异色的三角形有 2 个异色角, 所以图中异色三角形个数≤18, 故图中同色三角形个数 ≥20-18=2. 说明 题⑴是早期匈牙利的一个图论竞赛题.解这类“实际问题”时,重要的是会用图 的语言解释题意,把实际问题改写为图的问题. ⑵ 用异色角来解相关问题是较好的方法. 2 3 例 2 由 5 人组成一个公司, 其中任意三人总有 2 人彼此认识, 也总有 2 人彼此不认识. 证 明:这五人可以围桌而坐,使每人两旁都是他认识的人.(1978 年保加利亚数学竞赛) 证明 用 5 个点表示这 5 个人,若两人互相认识,则在表示这 2


推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com