完全圖

在${\displaystyle n}$个顶点上的完全图被记作${\displaystyle K_{n}}$，有些文献认为这个记号中的字母${\displaystyle K}$代表德文 komplett,[2] 但是完全图的德文vollständiger Graph,并没有字母${\displaystyle K}$，其他文献认为这个记号是为了纪念卡齐米日·库拉托夫斯基对图论的贡献。[3]

${\displaystyle K_{n}}$有${\displaystyle n(n-1)/2}$条边，并且是${\displaystyle n-1}$正则图。所有的完全图都是它们本身的极大团。它们是极大连通的，因为唯一的割点集(vertex cut)是所有顶点的集合。完全图的补图是空图(empty graph)。

完全图的每一条边都被附上了定向之后形成的有向图被称作轮转(tournament)。

${\displaystyle K_{n}}$可以被分解成${\displaystyle n}$个树${\displaystyle T_{i}}$，且${\displaystyle T_{i}}$有${\displaystyle i}$个顶点。[4] Ringel猜想可以被表述为：完全图${\displaystyle K_{2n+1}}$能否被分解成一些完全相同的${\displaystyle n}$阶树。[5] 对于足够大的${\displaystyle n}$，这个结论是成立的。[6][7]

完全图的匹配数按照它们的阶数排列，由telephone numbers给出： 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... （OEIS中的数列A000085）。这些数字给出了在${\displaystyle n}$阶图上Hosoya指数的最大可能值。[8] 在${\displaystyle K_{n}}$上的完美匹配(perfect matching)的个数为${\displaystyle (n-1)}$!!。 对于阶数小于等于27阶的完全图来说，它们的交叉数是已知的，${\displaystyle K_{28}}$的交叉数是7233或者7234。阶数更大的交叉数由Rectilinear Crossing Number project在收集。[9]${\displaystyle 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）。

${\displaystyle n}$阶完全图可以代表${\displaystyle (n-1)}$-单纯形。几何上，${\displaystyle K_{3}}$构成了三角形，${\displaystyle K_{4}}$构成了四面体，依次类推。Császár polyhedron, 一个非凸的和环面同胚的多边形，可以由${\displaystyle K_{7}}$作为它的骨架skeleton。

${\displaystyle K_{1}}$到${\displaystyle K_{4}}$都是平面图，然而当${\displaystyle n\geqslant 5}$时，在平面上绘制${\displaystyle K_{n}}$时总是会有交叉，另外，非平面图${\displaystyle K_{5}}$在刻画平面图的性质时起着重要的作用：根据Kuratowski's theorem，当且仅当一个图不包含${\displaystyle K_{5}}$,以及完全二分图${\displaystyle K_{3,3}}$作为它的一部分时，这个图是平面图。根据Wagner's theorem，当且仅当一个图不包含${\displaystyle K_{5}}$,以及完全二分图${\displaystyle K_{3,3}}$作为它的图子式时，这个图时平面图。 作为Petersen family的一部分, ${\displaystyle K_{6}}$起到了一个了类似的作用，为了保证一个图的linkless embedding,它不能作为这个图的图子式出现。[10] 更精确地说，Conway和Gordon[11] 证明了每一个${\displaystyle K_{6}}$在3维空间中的嵌入都是intrinsically linked 的，且至少有一对linked的三角形。Conway和Gordon还证明了 任意${\displaystyle K_{7}}$在3维空间中的嵌入都包含了一个作为一个非平凡的扭结嵌入在空间里的哈密顿环。

• Fully connected network
• 完全二分图，一种特殊的二分图，其中每个节点都和另一个部分的所有节点相连。

维基共享资源中相关的多媒体资源：完全圖

• 埃里克·韦斯坦因. . MathWorld.