完全圖

完全圖，所有完全圖都是它本身的團。若一個圖的每一對不同頂點恰有一條邊相連，則稱為完全圖。完全圖是每對頂點之間都恰連有一條邊的簡單圖。n個端點的完全圖有n個端點及n（n−1）/2條邊，以Kn表示。它是（k−1）-正則圖。所有完全圖都是它本身的團（clique）。

基本信息

• 中文名：完全圖
• 英文名：complete graph

• 分類：有向完全圖，無向完全圖
• 概念：每對頂點之間都恰連有一條邊的圖

簡介

完全圖

完全圖，是每對頂點之間都恰連有一條邊的簡單圖。平面圖不會包含K5或K3,3（完全二部圖）。所以，當n>=5時，Kn不會是平面圖。任意兩個結點之間都有一個邊相連,也就是結點兩兩相連；連通圖是指任意兩個結點之間都有一個路徑相連.
當然不一樣了,n個頂點的完全圖有n(n-1)/2條邊；而連通圖則不一定,但至少有n-1條邊.舉個例子,四個頂點的完全圖有6條邊,也就是四條邊加上2條對角線；而連通圖可以只包含周圍四條邊就可以了。

無向完全圖

任意一個具有n個結點的無向簡單圖，其邊數小於等於n*(n-1)/2;我們把邊數恰好等於n*(n-1)/2的n個結點的無向圖稱為完全圖。

有向完全圖

在一個n個結點的有向圖中，最大邊數為n*(n-1)。