完全图

每对顶点之间都恰连有一条边的图

在图论的数学领域，完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。而一个完全图是这样的一个图，即该图里的每两个顶点之间都有连线。而给一个完全图的每条线段都加上一个方向，那么这个图就成了完全有向图。n个端点的完全图有n个端点以及n(n − 1) / 2条边，以Kn表示。它是(k − 1)-正则图。所有完全图都是它本身的团（clique）。

简介

图论是一个古老的数学分支，它的创始人是18世纪的数学家欧拉(Euler).1736年，欧拉解决了著名的哥尼斯堡七桥问题，图论就是在他解决这一难题的过程中建立。然而，完全图的绘图，其顶点放置在正多边形的点上，已经在13世纪中出现。这样的绘画有时被称为神秘玫瑰。

属性

n个顶点的完全图表示为。一些消息来源称，这个符号中的字母K代表德语单词komplett，但完全图的德文名称vollständigerGraph不包含字母K，其他来源则表示符号表示 Kazimierz Kuratowski图论。

具有个边（三角数），并且是维度为n-1的常规图。所有完全图都是它们自己的最大组。它们是最大化连接的，因为断开图形的唯一顶点是所有的顶点集。完全图的补码图是一个空图。

如果一个完全图的边缘都被赋予一个方向，那么所得的有向图就被称为比赛。

完全图的匹配数由电话号码给出：

1，1，2，4，10，26，76，232，764，2620，9496，35696，140152，568504，2390480，10349536，46206736，...（OEIS中的序列A000085）。

这些数字给出了n顶点图的Hosoya索引的最大可能值。完全图（n均匀）完美匹配的数量由双因子给出。

的交叉号码是已知的，需要7233或7234个交叉口。进一步的值是由直线交叉号码项目收集的。的交叉数字是：

0,0,0,0,1,3,9,29,36,62,102,153,229,324,447,603,798,1029,1318,1657,2055,2528,3077,3699,4430,5250,6180，...（OEIS中的序列A014540）。

几何和拓扑

具有n个节点的完全图表示（n-1） - 复杂的边缘。几何形成三角形的边缘集合，是四面体等。具有圆环拓扑的非凸多面体Császár多面体具有完整的图形作为其骨架。四个或更多维度的每个多面体也具有完整的框架。

至均为平面图。然而，具有五个或更多个顶点的完整图形的每个平面图都必须包含交叉点，并且非平面完全图在平面图的表征中起关键作用：通过库拉托斯基定理，当且仅当它既不包含也不是包含作为细分，图才能成为平面图，通过瓦格纳定理，图形代替细分也是一样的结果。康威和戈登证明，在三维空间中的每一次嵌入是内在联系的，至少有一对连接的是三角形。康威和戈登还表明，的任何三维嵌入包含一个嵌入在空间中的哈密尔顿循环。

举例

n顶点的完全图，在n从1到12之间，与边缘数量一起显示如下：

无向完全图

无向完全图是用n表示图中顶点数目的一种图，一张图中每条边都是无方向的。

定义

用n表示图中顶点数目，用e表示边或弧的数目。若∈VR，则vi≠vj，那么，对于无向图，e的取值范围是0到，有条边的无向图称为完全图。

解释

直观来说，若一个图中每条边都是无方向的，则称为无向图。

（1）无向边的表示

无向图中的边均是顶点的无序对，无序对通常用圆括号表示。

【例】无序对(vi，vj)和(vj，vi)表示同一条边。

（2）无向图的表示