完全图

完全图，所有完全图都是它本身的团。若一个图的每一对不同顶点恰有一条边相连，则称为完全图。完全图是每对顶点之间都恰连有一条边的简单图。n个端点的完全图有n个端点及n（n−1）/2条边，以Kn表示。它是（k−1）-正则图。所有完全图都是它本身的团（clique）。

简介

任意两个结点之间都有一个边相连,也就是结点两两相连；连通图是指任意两个结点之间都有一个路径相连。

当然不一样了，n个顶点的完全图有n(n-1)/2条边；而连通图则不一定，但至少有n-1条边。举个例子，四个顶点的完全图有6条边,也就是四条边加上2条对角线；而连通图可以只包含周围四条边就可以了。

图形理论本身以莱昂哈德欧拉于1736年在Königsberg七桥的工作开始。然而，完全图的绘图，其顶点放置在正多边形的点上，已经在13世纪中出现。这样的绘画有时被称为神秘玫瑰。

具体

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

讨论了完全图Kn分解成五个顶点的星和圈的存在性,给出完全图Kn存在{S5,C5}-强制分解的充要条件是n≥9，以及完全图Kn存在{S5,C5}-分解的充要条件是n≥5(n≠6,7)。

分类

无向

任意一个具有n个结点的无向简单图，其边数小于等于n*(n-1)/2;我们把边数恰好等于n*(n-1)/2的n个结点的无向图称为完全图。

有向

在一个n个结点的有向图中，最大边数为n*(n-1)。