【图论】托兰定理【学生版】

课程类型课程类型 数学数学 “托兰定理”“托兰定理” 讲义编号： 学员： 讲师： 年级： 授课方式（在线或线下） ： 授课日期： （线下填）授课教学点： 知识定位知识定位 托兰定理在求极值的图论问题中具有重要作用，本讲主要介绍该定理及其相关方法。 知识梳理知识梳理 定理：定理：有 n 个顶点且不含三角形的简单图G 中最多有[n2/4]条边。 证明 1 例例 1 1 设 n≥2。 平面上已给 2n 个点，每三点不共线。在这些点之间连n2+1 条线段。证明至少形成n 个以已知 点为顶点的三角形。 例例 2 2 由 n 个点和这些点之间的 l 条连线段组成一个空间四边形， 其中 n=q2+q+1， l≥1/2q(q+1)2+1， q≥2， q∈ N N。 已知此图中任四点不共面，每点至少有一条连线段，存在一点至少有q+2 条连线段。证明：图中必存在一个空 间四边形（即由四点 A，B，C，D 和四条连线段 AB，BC，CD，DA 组成的图形） 例例 3 3 一次会议有 500 人参加， （i）如果每名代表认识的人数为400 人，是否一定能选出6 个人，每两人互相认 识？(ii）如果每人认识的人数大于400 人。证明：一定能找到6 个人，每两人互相认识。 托兰图托兰图 托兰图托兰图 Tn, r 是具有 n 个顶点的完全 r 部图且其中各部集的大小最多相差1。 引理引理 在具有 n 个顶点的 r 部简单图中，托兰图是唯一边数最多的图。 证明 2 定理定理 有n个顶点且不含Kr+1的图G 中最多有er(n)条边， 其中。 此时图G为Tn,r。 证明 例例 4 4 给定平面上 n 个点构成的集合且其中任意点对的距离不超过1，则距离超过的点对的最大数目为。 例例5 5 X是一个n元集， 指定它的m个k元子集A1， A2， ……， Am为红k子集。 求证： 若 一个 X 的 k+1 元子集，它的所有 k 元子集都是红 k 子集。 3 ， 则必存在 试题演练试题演练 1.图 G 有 n 个顶点，m 条边，则图中至少有 4m/3n(m-n2/4)个三角形。 2.在例 2 中只需令，该图中必有一个四边形。 3.设图 G 有 n 个顶点，且不包含 Kr（作为子图） ，其中 r 是一个固定的正整数，则G 的顶点的次数满足不等式 ∈ 。 4.证明：没有 Kr+1子图的任意 n 顶点简单图至多有(1—1/r)n2/2 条边。 5.a)证明：不含 Kr+ 1 子图的最大简单图必含有Kr子图。 b)证明：。 c)利用（a）和（b） ，对 n 作数学归纳来证明托兰定理。包括达到上界的图的特性。 4 6.在直径为 4 英里的圆盘状城市中布置 18 个便携式电话基站。每个基站可以与其他位于3 英里半径范围内的基 站传送信息。证明：无论将这些基站在城市中如何布置，至少有两个基站可以向另5 个基站传送信息。 讲师评价讲师评价 知识点知识点课后掌握情况课后掌握情况所需习题编号所需习题编号是否需要课时加强是否需要课时加强 课后掌握情况评分： 1 对本知识点毫无所知，闻所未闻。 2 了解该知识点，能完成简单的识记题。 3 理解该知识点，能运用其分析解答简单问题。 4 把握知识的意义，但缺乏练习与手感，解答稍难的题目速度慢。 5 深刻了解知识内核，能完成相应试题，但有一定的错误率。 6 能够较熟练利用该知识点解决相关试题，但题目稍加变形就难以入手。 7 熟悉该知识点各要素，能顺利解答该知识点范围内各种题目的变形。 8 能把该知识点与其他知识相关联，解答高考中的压轴题。 9 懂得出题规律，只对该知识点范围的难题有兴趣！ 10 已拿下该知识点，拥有金钟罩，刀枪不入。 5