图兰定理
图兰定理
图论中,图兰定理是 K_(r+1)-free 图中边数的结果。
通过将一组顶点集划分为大小相等或几乎相等的r个部分,并在两个顶点属于两个不同子集的情况下,通过边连接两个顶点,可以形成不包含任何(r+1)个点团的n点图部分。我们称产生的图为托兰图 T(n,r)。图兰定理指出,托兰图在所有K_(r+1)-free的n点图中具有最多的边数。
托兰图是由匈牙利数学家帕尔托兰(PálTurán)于1941年首次描述和研究的,尽管曼特尔(Mantel)早在1907年就指出了该定理的一个特例。
基本定理
令G为具有n个顶点的任何图,使得G为K_(r+1)-free。
等效表达如下:
在没有(r+1)点团的n个顶点的简单图中,T(n,r)的边数最大。
参考资料

Warning: Invalid argument supplied for foreach() in /www/wwwroot/newbaike1.com/id.php on line 362
目录
概述
基本定理
参考资料