完全图 - 中文维基百科镜像

易经学习

天地变化的道理

分类目录

使用率很高网站

文章列表

生活要常常分享

维基百科

您身边百科全书

完全图

点击查看词条快照

在图论中，完全图是一个简单的无向图，其中每一对不同的顶点都只有一条边相连。完全有向图是一个有向图，其中每一对不同的顶点都只有一对边相连（每个方向各一个）。图论起源于欧拉在1736年解决七桥问题上做的工作，但是通过将顶点放在正多边形上来绘制完全图的尝试，早在13世纪拉蒙·柳利的工作中就出现了。这种画法有时被称作神秘玫瑰。性质. 在formula_1个顶点上的完全图被记作formula_2，有些文献认为这个记号中的字母formula_3代表德文 "komplett", 但是完全图的德文"vollständiger Graph",并没有字母formula_3，其他文献认为这个记号是为了纪念卡齐米日·库拉托夫斯基对图论的贡献。 formula_2有formula_6条边，并且是formula_7正则图。所有的完全图都是它们本身的极大团。它们是极大连通的，因为唯一的割点集(vertex cut)是所有顶点的集合。完全图的补图是空图(empty graph)。完全图的每一条边都被附上了定向之后形成的有向图被称作轮转(tournament)。 formula_2可以被分解成formula_1个树formula_10，且formula_10有formula_12个顶点。 Ringel猜想可以被表述为：完全图formula_13能否被分解成一些完全相同的formula_1阶树。对于足够大的formula_1，这个结论是成立的。完全图的匹配数按照它们的阶数排列，由telephone numbers给出： 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... （OEIS数列）。这些数字给出了在formula_1阶图上的最大可能值。在formula_2上的完美匹配(perfect matching)的个数为formula_18!!。对于阶数小于等于27阶的完全图来说，它们的交叉数是已知的，formula_19的交叉数是7233或者7234。阶数更大的交叉数由Rectilinear Crossing Number project在收集。formula_2的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数列）。几何和拓扑. formula_1阶完全图可以代表formula_18-单纯形。几何上，formula_23构成了三角形，formula_24构成了四面体，依次类推。Császár polyhedron, 一个非凸的和环面同胚的多边形，可以由formula_25作为它的骨架skeleton。 formula_26到formula_24都是平面图，然而当formula_28时，在平面上绘制formula_2时总是会有交叉，另外，非平面图formula_30在刻画平面图的性质时起着重要的作用：根据Kuratowski's theorem，当且仅当一个图不包含formula_30,以及完全二分图formula_32作为它的一部分时，这个图是平面图。根据Wagner's theorem，当且仅当一个图不包含formula_30,以及完全二分图formula_32作为它的图子式时，这个图是平面图。作为Petersen family的一部分, formula_35起到了一个了类似的作用，为了保证一个图的linkless embedding,它不能作为这个图的图子式出现。更精确地说，Conway和Gordon 证明了每一个formula_35在3维空间中的嵌入都是intrinsically linked 的，且至少有一对linked的三角形。Conway和Gordon还证明了任意formula_25在3维空间中的嵌入都包含了一个作为一个非平凡的扭结嵌入在空间里的哈密顿环。

安那瑞安

热脱硫杆菌门

无孔亚纲

远日点

平面图 (图论)

岳阳楼记

中国人民解放军建军纪念日

异常球菌-栖热菌门

亨利二世 (士瓦本)

三国史记

普陀山多宝塔

常绿植物