完全圖

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

若果 $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.（英文）