完全圖

在圖論的數學領域，完全圖是一個簡單的無向圖，其中每對不同的頂點之間都恰連有一條邊相連。完整的有向圖又是一個有向圖，其中每對不同的頂點通過一對唯一的邊緣（每個方向一個）連線。n個端點的完全圖有n個端點以及n(n − 1) / 2條邊，以Kn表示。它是(k − 1)-正則圖。所有完全圖都是它本身的團（clique）。

圖形理論本身以萊昂哈德歐拉於1736年在Königsberg七橋的工作開始。 然而，完全圖的繪圖，其頂點放置在正多邊形的點上，已經在13世紀中出現。這樣的繪畫有時被稱為神秘玫瑰。

基本介紹

• 中文名：完全圖
• 外文名：complete graph
• 領域：數學
• 概念：每對頂點之間都恰連有一條邊的圖
• 分類：有向完全圖，無向完全圖
• 相關名詞：無向圖

簡介

在圖論的數學領域，完全圖是一個簡單的無向圖，其中每對不同的頂點之間都恰連有一條邊相連。完整的有向圖又是一個有向圖，其中每對不同的頂點通過一對唯一的邊緣（每個方向一個）連線。n個端點的完全圖有n個端點以及n(n − 1) / 2條邊，以Kn表示。它是(k − 1)-正則圖。所有完全圖都是它本身的團（clique）。

圖形理論本身以萊昂哈德歐拉於1736年在Königsberg七橋的工作開始。 然而，完全圖的繪圖，其頂點放置在正多邊形的點上，已經在13世紀中出現。這樣的繪畫有時被稱為神秘玫瑰。

屬性

n個頂點的完全圖表示為 。 一些訊息來源稱，這個符號中的字母K代表德語單詞komplett，但完全圖的德文名稱vollständigerGraph不包含字母K，其他來源則表示符號表示 Kazimierz Kuratowski圖論。

具有 個邊（三角數），並且是維度為n-1的常規圖。所有完全圖都是它們自己的最大組。 它們是最大化連線的，因為斷開圖形的唯一頂點是所有的頂點集。完全圖的補碼圖是一個空圖。

如果一個完全圖的邊緣都被賦予一個方向，那么所得的有向圖就被稱為比賽。

完全圖的匹配數由電話號碼給出：

1，1，2，4，10，26，76，232，764，2620，9496，35696，140152，568504，2390480，10349536，46206736，...（OEIS中的序列A000085）。

這些數字給出了n頂點圖的Hosoya索引的最大可能值。完全圖 （n均勻）完美匹配的數量由雙因子 給出。

的交叉號碼是已知的， 需要7233或7234個交叉口。 進一步的值是由直線交叉號碼項目收集的。 的交叉數字是：

0,0,0,0,1,3,9,29,36,62,102,153,229,324,447,603,798,1029,1318,1657,2055,2528,3077,3699,4430,5250,6180，...（OEIS中的序列A014540）。

幾何和拓撲

具有n個節點的完全圖表示（n-1） - 複雜的邊緣。 幾何 形成三角形的邊緣集合， 是四面體等。具有圓環拓撲的非凸多面體Császár多面體具有完整的圖形 作為其骨架。 四個或更多維度的每個多面體也具有完整的框架。

至 均為平面圖。 然而，具有五個或更多個頂點的完整圖形的每個平面圖都必須包含交叉點，並且非平面完全圖 在平面圖的表征中起關鍵作用：通過庫拉托斯基定理，若且唯若它既不包含 也不是包含 作為細分，圖才能成為平面圖，通過華格納定理，圖形代替細分也是一樣的結果。 康威和戈登證明， 在三維空間中的每一次嵌入是內在聯繫的，至少有一對連線的是三角形。 康威和戈登還表明， 的任何三維嵌入包含一個嵌入在空間中的哈密爾頓循環。

舉例

n頂點的完全圖，在n從1到12之間，與邊緣數量一起顯示如下：

無向完全圖

無向完全圖是用n表示圖中頂點數目的一種圖，一張圖中每條邊都是無方向的。

定義

用n表示圖中頂點數目，用e表示邊或弧的數目。若<vi,vj>∈VR，則vi≠vj，那么，對於無向圖，e的取值範圍是0到，有條邊的無向圖稱為完全圖。

解釋

直觀來說，若一個圖中每條邊都是無方向的，則稱為無向圖。

（1）無向邊的表示

無向圖中的邊均是頂點的無序對，無序對通常用圓括弧表示。

【例】無序對(vi，vj)和(vj，vi)表示同一條邊。

（2）無向圖的表示

【例】下面(b)圖中的G2和(c)圖中的G3均是無向圖，它們的頂點集和邊集分別為：

V(G2)={v1，v2，v3，v4}

E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)}

V(G3)={v1，v2，v3，v4，v5，v6，v7}

E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)}

注意

在以下討論中，不考慮頂點到其自身的邊。即若(v1，v2)或<vl，v2>是E(G)中的一條邊，則要求v1≠v2。此外，不允許一條邊在圖中重複出現，即只討論簡單的圖。

3．圖G的頂點數n和邊數e的關係

（1）若G是無向圖，則0≤e≤n(n-1)/2

恰有n(n-1)/2條邊的無向圖稱無向完全圖(Undirected Complete Graph)

（2）若G是有向圖，則0≤e≤n(n-1)。

恰有n(n-1)條邊的有向圖稱為有向完全圖(Directed Complete Graph)。

注意：

完全圖具有最多的邊數。任意一對頂點間均有邊相連。

【例】上面(b)圖的G2就是具有4個頂點的無向完全圖。

有向完全圖

用n表示圖中頂點數目，用e表示邊或弧的數目。若<vi,vj>∈VR，則≠，那么，對於有向圖，e的取值範圍是0到 ，有 條邊的有向圖稱為有向完全圖。