“集智百科精选”是一个长期专栏，持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目，集智百科希望打造复杂性科学领域最全面的百科全书，欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入！


本文是对集智百科中“顶点”词条的摘录，参考资料及相关词条请参阅百科词条原文。


本词条由集智俱乐部众包生产，难免存在纰漏和问题，欢迎大家留言反馈或者前往对应的百科词条页面进行修改，一经修改，可以获得对应的积分奖励噢！


目录


一、什么是顶点？
二、顶点类型
三、相关资源推荐
四、集智百科词条志愿者招募
顶点_Vertex：https://wiki.swarma.org/index.php?title=顶点_Vertex





1. 什么是顶点？




在数学上，更具体地说在图论中，图这一抽象对象的基本组成单元是顶点或节点：无向图由一组顶点和一组边（每条边由一对顶点组成，不区分这俩顶点的顺序）组成，而有向图由一组顶点和一组弧（每条弧由一对顶点组成，区分这俩顶点的顺序）组成。在抽象图的图示中，一般而言，带标注的圆圈表示顶点，两个顶点之间的直线或箭头表示边。直线用于表示无向图的边，箭头表示有向图的边。

从图论的观点来看，顶点被视为没有属性且不可分割的对象。无论这些顶点所组成的图来自什么样的应用场景，无论在这些应用场景中，顶点所表示的对象又有什么额外的结构。例如: 计算机科学领域中的语义网络，就可以抽象为图，其顶点表示概念或对象的类。

若图包含由顶点和组成的边，则称顶点邻接于adjacent to顶点;由所有邻接于的顶点而组成 的图，被称为这些顶点的导出”’子图induced subgraph”’，它也被称为顶点的”’邻域 neighborhood”’。

2. 顶点类型

在抽象图中，顶点的度 degree，记作，是所有关联于的边的数量。度为0的顶点被称作孤立顶点 isolated vertex，这样的顶点不是任何边的端点(如图2所示，这一抽象图中含有一个孤立顶点)
度为1的顶点被称为叶顶点 leaf vertex，也称叶子顶点、叶节点、悬挂顶点 pendant vertex。
在有向图中，我们可以根据边的方向，把顶点的度分为出度 outdegree(也称出次数)，记作和入度 indegree(也称入次数)，记作。一个顶点的出度指的是，所有从这个顶点出发，连接其他顶点的箭头的数量。与此相反，一个顶点的入度指的是，所有从其他顶点出发，连接到这个顶点的箭头的数量。在有向图中，有可能出现两种顶点：源顶点 source vertex 和汇顶点 sink vertex。前者指入度为0的顶点，后者指出度为0的顶点。
若一个顶点的邻域恰好能构成团 clique，即这个顶点邻域中的任意两个顶点都是相邻的，那么这个顶点被称为单纯形顶点 simplicial vertex，也译为单纯顶点。与所有其他顶点相邻的顶点，被称为泛顶点 universal vertex。
若移除某一顶点（和所有以这个顶点为端点的边）后，图被分离为若干个彼此互不相连的子图，那么这 一顶点就被称为割顶点 cut vertex;由割顶点构成的集合被称为顶点分离集。若一个连通图被移除少于K个顶点后，总能保持连通，那么这个图被称为K-顶点连通图。由两两不相邻的顶点所构成的集合，被称为独立集。由图中每条边的一个或两个端点所构成的集合，被称为顶点覆盖。图的顶点空间是向量空间，它的基向量与图的顶点相对应。
如果一个图具有将任何顶点映射到任何其他顶点的对称性，则该图是顶点传递的。
如果一个图上存在某种自同构映射automorphism，能把图中任意一个顶点映射为图中的某个其他顶点 ，同时保持边不变，即若顶点相邻，那么顶点和也相邻，那么我们认为这个图是顶点传递的，这样的图具有某种相应的对称性质。
在图计数或者图同构的语境中，若图中的顶点都是无标注的顶点，则可以不用考虑上面那样额外信息的影响。只要两个图之间存在顶点之间的映射，使得原来连通的顶点，在映射之后依然连通，就可以说这两个图是同构的。
图的顶点类似于但不等同于(高维)多面体的顶点。但多面体的顶点有额外的结构(几何位置)，在图论中未能被假定存在。换句话说，作为概念，图的顶点比多面体的顶点，要更抽象。多面体的骨架构成一个图，其顶点是多面体的顶点，但多面体的顶点有无法在图论中假定存在的其他结构(几何位置) 。多面体中顶点的顶点图形类似于图中顶点的邻域。





3. 相关资源推荐

课程推荐
漫谈图论的起源、发展与应用
本课程中，介绍了图论中的基本概念和网络科学使用的工具，可以帮助认识真实网络的关键性质。





课程推荐：漫谈图论的起源、发展与应用https://campus.swarma.org/course/1745





4. 百科项目志愿者招募




作为集智百科项目团队的成员，本文内容由思无涯咿呀咿呀参与贡献。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页，更多信息可以访问其集智百科个人主页。






以上内容都是我们做这项目的起点，作为来自不同学科和领域的志愿者，我们建立起一个有效的百科团队，分配有审校、翻译、编辑、宣传等工作。我们秉持：知识从我而来，问题到我为止的信念，认真负责编撰每一个词条。






在这里从复杂性知识出发与伙伴同行，同时我们希望有更多志愿者加入这个团队，使百科词条内容得到扩充，并为每位志愿者提供相应奖励与资源，建立个人主页与贡献记录，使其能够继续探索复杂世界。


如果你有意参与更加系统精细的分工，扫描二维码填写报名表，我们期待你的加入！




集智百科报名表


来源：集智百科编辑：曾祥轩



推荐阅读什么是人工社会？| 集智百科

什么是自组织 | 集智百科

什么是元胞自动机？| 集智百科
什么是图（抽象数据类型）| 集智百科
什么是非线性系统 | 集智百科

加入集智，一起复杂！



点击“阅读原文”，阅读顶点相关内容与文献