完全圖

在图论中，完全图（）是一个简单的无向图，其中每一对相異的顶点都有且只有一条边相连。若為簡單有向圖且每一對相異頂點皆有一個有向邊相連（其方向方向擇一），則稱為競賽圖。其中，如果每對相異頂點之間相連的有向邊為雙向，則稱為完全有向圖或完全競賽圖。

图论起源于欧拉在1736年解决七桥问题上做的工作，但是通过将顶点放在正多边形上来绘制完全图的尝试，早在13世纪拉蒙·柳利的工作中就出现了.。这种画法有时被称作神秘玫瑰。

性质
在个顶点上的完全图被记作，有些文献认为这个记号中的字母代表德文 komplett，.但是完全图的德文vollständiger Graph并没有字母，其他文献认为这个记号是为了纪念卡齐米日·库拉托夫斯基对图论的贡献。.

有条边，并且是正则图。所有的完全图都是它们本身的极大团。它们是极大连通的，因为唯一的割点集(vertex cut)是所有顶点的集合。完全图的补图是空图。

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

可以被分解成个树，且有个顶点。 Ringel猜想可以被表述为：完全图能否被分解成一些完全相同的阶树。 对于足够大的，这个结论是成立的。

完全图的匹配数按照它们的阶数排列，由telephone numbers给出： 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... 。这些数字给出了在阶图上的最大可能值。. 在上的完美匹配的个数为!!。
对于阶数小于等于27阶的完全图来说，它们的交叉数是已知的，的交叉数是7233或者7234。阶数更大的交叉数由Rectilinear Crossing Number project在收集。的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, ... 。

几何和拓扑
阶完全图可以代表-单纯形。几何上，构成了三角形，构成了四面体，依次类推。恰薩爾十四面體，一个非凸的和环面同胚的多边形，可以由作为它的。

到都是平面图，然而当时，在平面上绘制时总是会有交叉。另外，非平面图在刻画平面图的性质时起着重要的作用：根据庫拉托夫斯基定理，当且仅当一个图不包含或完全二分图作为它的細分时，这个图是平面图。根据瓦格纳定理，当且仅当一个图不包含,以及完全二分图作为它的图子式时，这个图是平面图。作为Petersen family的一部分，起到了一个了类似的作用，为了保证一个图的linkless embedding，它不能作为这个图的图子式出现。. 更精确地说，Conway和Gordon 证明了每一个在3维空间中的嵌入都是intrinsically linked 的，且至少有一对linked的三角形。Conway和Gordon还证明了任意在3维空间中的嵌入都包含了一个作为一个非平凡的扭结嵌入在空间里的哈密顿环。

例子
當  時，阶完全图以及它們的邊數：
     140px 140px 140px 140px     140px 140px 140px 140px     140px 140px 140px 140px

另见
Fully connected network：全连接网络
完全二分图，一种特殊的二分图，其中每个节点都和另一个部分的所有节点相连。
参考文献

外部链接



Category:图
Category:正則圖