图兰定理

维基百科,自由的百科全书
跳转至: 导航搜索

图兰定理是一個图论中的定理,關於Kr+1免除圖的邊數。

圖蘭定理於1941年首次由匈牙利數學家帕尔·图蘭(Paul Turán)發現。

设G为Kn的子图,而G不含完全图Kr+1。则G最多有条边

圖蘭圖[编辑]

圖蘭圖 的定義為一個特殊的具有 n 點的完全r-分圖,其中各部份的頂點數的差不超過1,或者說,r 個部份分別有個頂點。