导图创作分享
本文概述了图兰定理及其在图论中的应用，包括定理的定义、数学表达、图兰图的概念、定理的应用和进一步结论，以及特殊情况下的Mantel定理和三角形的包含性。
大纲
- 图兰定理概述
- 图兰定理定义
- 图兰定理由P.图兰在1941年提出，是极值图论的基础。
- 定理描述了不包含特定团的简单图的最大边数。
- 图兰定理的数学表达
- 定理具体叙述：设有个顶点的简单图，若不包含完全图，则其边数有最大值。
- 等号成立的条件：当图是具有个顶点的完全部图时，每一部的顶点数尽可能相等。
- 图兰图
- 完全部图，每一部的顶点数尽可能相等，称为图兰图。
- 图兰定理的应用
- 定理证明：具有个顶点、条边的简单图总包含由个顶点构成的完全子图。
- 爱尔特希结论：若简单图不包含，则度弱于某个完全部图。
- 图兰定理的进一步结论
- 若图的顶点数为，边数为，则一定包含完全图。
- 狄拉克定理：若，设是完全图去掉任意一条边后得到的子图，则包含子图。
- 特殊情形：Mantel定理
- 当顶点数为且不包含三角形的简单图至多有条边，此时的图兰图为完全二部图。
- 三角形的包含性
- 当一个具有个顶点的图的边数为时，至少含有个三角形。
- 图兰定理定义
教程推荐
- ●
- ●
- ●
版权声明：本模板仅供个人学习、学术研究及商用复用（需保留平台标识），禁止未经授权的转载、售卖、二次分发，侵权必究。
