万维百科

完全图

完全图
Complete graph K7.svg
K7,含有7个顶点的完全图
顶点n
自同构群n!(Sn
色数n
  • n,若n为奇数
  • n − 1,若n为偶数
属性(n-1)-正则
顶点传递
边传递
单位距离
强正则

图论中,完全图是一个简单的无向图,其中每一对不同的顶点都只有一条边相连。完全有向图是一个有向图,其中每一对不同的顶点都只有一对边相连(每个方向各一个)。

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

性质

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

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

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

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

完全图的匹配数按照它们的阶数排列,由telephone numbers给出: 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... (OEIS中的数列A000085)。这些数字给出了在阶图上Hosoya指数英语Hosoya index的最大可能值。 在上的完美匹配(perfect matching)的个数为!!。 对于阶数小于等于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, ... (OEIS中的数列A014540)。

几何和拓扑

阶完全图可以代表-单纯形。几何上,构成了三角形构成了四面体,依次类推。Császár polyhedron, 一个非凸的和环面同胚的多边形,可以由作为它的骨架skeleton

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

例子

K1: 0 K2: 1 K3: 3 K4: 6
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg 3-simplex graph.svg
K5: 10 K6: 15 K7: 21 K8: 28
4-simplex graph.svg 5-simplex graph.svg 6-simplex graph.svg 7-simplex graph.svg
K9: 36 K10: 45 K11: 55 K12: 66
8-simplex graph.svg 9-simplex graph.svg 10-simplex graph.svg 11-simplex graph.svg

另见

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

外部链接


本页面最后更新于2021-06-29 11:05,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器