完全圖

完全圖
K7，含有7個頂點的完全圖
頂點	n
邊	$\textstyle {\frac {n(n-1)}{2}}$
自同構群	n!（Sn）
色數	n n，若n為奇數 n − 1，若n為偶數
屬性	(n-1)-正則 頂點傳遞 邊傳遞 單位距離 強正則

在圖論中，完全圖是一個簡單的無向圖，其中每一對不同的頂點都只有一條邊相連。完全有向圖是一個有向圖，其中每一對不同的頂點都只有一對邊相連（每個方向各一個）。

圖論起源於歐拉在1736年解決七橋問題上做的工作，但是通過將頂點放在正多邊形上來繪製完全圖的嘗試，早在13世紀拉蒙·柳利 的工作中就出現了。這種畫法有時被稱作神秘玫瑰。

性質

在$n$個頂點上的完全圖被記作$K_{n}$，有些文獻認為這個記號中的字母$K$代表德文 komplett, 但是完全圖的德文vollständiger Graph,並沒有字母$K$，其他文獻認為這個記號是為了紀念卡齊米日·庫拉托夫斯基對圖論的貢獻。

$K_{n}$有$n(n-1)/2$條邊，並且是$n-1$正則圖。所有的完全圖都是它們本身的極大團。它們是極大連通的，因為唯一的割點集(vertex cut)是所有頂點的集合。完全圖的補圖是空圖(empty graph)。

完全圖的每一條邊都被附上了定向之後形成的有向圖被稱作輪轉(tournament)。

$K_{n}$可以被分解成$n$個樹$T_{i}$，且$T_{i}$有$i$個頂點。 Ringel猜想可以被表述為：完全圖$K_{2n+1}$能否被分解成一些完全相同的$n$階樹。 對於足夠大的$n$，這個結論是成立的。

完全圖的匹配數按照它們的階數排列，由telephone numbers給出： 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... （OEIS數列A000085）。這些數字給出了在$n$階圖上Hosoya指數的最大可能值。 在$K_{n}$上的完美匹配(perfect matching)的個數為$(n-1)$!!。 對於階數小於等於27階的完全圖來說，它們的交叉數是已知的，$K_{28}$的交叉數是7233或者7234。階數更大的交叉數由Rectilinear Crossing Number project在收集。$K_{n}$的Rectilinear交叉數為：0, 0, 0, 0, 1, 3, 9, 19, 36, 62, 102, 153, 229, 324, 447, 603, 798, 1029, 1318, 1657, 2055, 2528, 3077, 3699, 4430, 5250, 6180, ... （OEIS數列A014540）。

幾何和拓撲

$n$階完全圖可以代表$(n-1)$-單純形。幾何上，$K_{3}$構成了三角形，$K_{4}$構成了四面體，依次類推。Császár polyhedron, 一個非凸的和環面同胚的多邊形，可以由$K_{7}$作為它的骨架skeleton。

$K_{1}$到$K_{4}$都是平面圖，然而當$n\geqslant 5$時，在平面上繪製$K_{n}$時總是會有交叉，另外，非平面圖$K_{5}$在刻畫平面圖的性質時起着重要的作用：根據Kuratowski's theorem，當且僅當一個圖不包含$K_{5}$,以及完全二分圖$K_{3,3}$作為它的一部分時，這個圖是平面圖。根據Wagner's theorem，當且僅當一個圖不包含$K_{5}$,以及完全二分圖$K_{3,3}$作為它的圖子式時，這個圖是平面圖。 作為Petersen family的一部分, $K_{6}$起到了一個了類似的作用，為了保證一個圖的linkless embedding,它不能作為這個圖的圖子式出現。 更精確地說，Conway和Gordon 證明了每一個$K_{6}$在3維空間中的嵌入都是intrinsically linked 的，且至少有一對linked的三角形。Conway和Gordon還證明了 任意$K_{7}$在3維空間中的嵌入都包含了一個作為一個非平凡的扭結嵌入在空間裡的哈密頓環。

例子

K1: 0	K2: 1	K3: 3	K4: 6
K5: 10	K6: 15	K7: 21	K8: 28
K9: 36	K10: 45	K11: 55	K12: 66

另見

• Fully connected network：全連接網絡
• 完全二分圖，一種特殊的二分圖，其中每個節點都和另一個部分的所有節點相連。

外部連結

• 埃里克·韋斯坦因. Complete Graph. MathWorld.