完全圖

完全圖（英文：complete graph）係圖論中嘅一個術語攞來表示一個簡單圖嘅，其中每粒綟都透過一條檠連接到其他每一粒綟。完整嘅$n$綟圖係唯一確定嘅（除開同構），得由$K_{n}$指定。

完全圖$K_{1}$到$K_{5}$

若果$V=\{v_{1},\dotsc ,v_{n}\}$係隻綟集畀成幅圖$K_{n}$，係噉隻檠集$E$ 即係隻集畀啲檠啲喺成孖嘅嘸同頂點之間嘅：$E=\{\{v_{i},v_{j}\}:1\leq i<j\leq n\}$

一隻完全圖同時亦都係佢嘅最大團。

特徵

完全圖$K_{1}$到$K_{4}$係平面嘅（即可以轉成檠冇交叉嘅形式）。根據 Kuratowski定理，所有其他完全圖都嘸係平面圖，因為佢哋包含有$K_{5}$作為子圖。

完全圖裏頭嘅檠數$K_{n}$對應三角形數：

$\Delta _{n-1}={n \choose 2}={\frac {n(n-1)}{2}}$ .

完全圖$K_{n}$係一隻$(n-1)$ 正則圖：每粒綟都有$n-1$鄰舍。因此，每隻上色畀啲圖都有$n$隻色。另外，完全圖帶奇數$n$嘅係畫得一筆畫嘅而帶偶數$n$嘅嘸係。

完全圖帶$n>2$嘅係Hamiltonian圖（睇Hamiltonian路徑問題）。完全圖$K_{n}$包括${\tfrac {1}{2}}(n-1)!$條嘸同嘅Hamiltonian迴路。

推廣

惗法畀完全圖可以推廣到$k$-分圖上。如果一柵分柵嘅每粒綟都連接到所有其他分柵嘅所有綟，係噉啲圖就係完全嘅。完全嘅多分圖帶$p$柵集、啲集裏頭包含有$n_{1},\dotsc ,n_{p}$ 粒綟嘅，着表示為$K_{n_{1},\dotsc ,n_{p}}$。

有方向嘅完全圖，就變成競賽圖。

軟件

可以創建完全圖喺免費嘅Python庫NetworkX嘅幫助下。例子：

import networkx as nx
import matplotlib.pyplot as plt

G = nx.complete_graph(15)

nx.draw_circular(G, with_labels=True, font_weight='bold')
plt.show()

文獻

• Lutz Volkmann: Fundamente der Graphentheorie. Springer, Wien 1996, ISBN 3-211-82774-9; neuere Version: Graphen an allen Ecken und Kanten (PDF; 3,5 MB)

連出去

• Weisstein, Eric W., "Complete Graph" - MathWorld.（英文）