顶点 (图论)

✍ dations ◷ 2025-12-01 21:26:48 #图论

在数学中,更确切地说,在图论中,一个顶点(vertex,或多个顶点,vertices)或节点(node)是构成图的基本单位:一个无向图包括一个顶点的集合和一个边(顶点的无序对)的集合,而一个有向图包括一个顶点的集合和一个弧(顶点的有序对)的集合。在一个图的示意图中,一个顶点通常表示为一个带标号的圆形,而一条边表示为连接两个顶点的一条直线或一个箭头。

站在图论的角度上,顶点被视为无特征且不可分割的对象,虽然因为该图的用途不同,他们可能有额外的结构;例如,一个语义网络是一个图,其顶点表示的是概念或对象的类别。

两个被一条边所连接的顶点称作该边的端点,且可以说该边从一个点入射向另一个点。如果一个图包含一条边,则可以说顶点相邻顶点。顶点的邻域是该图的一个导出子图,由所有与相邻的顶点组成。

一个顶点的度,表示为�(v),指的是在图中与这个顶点相连的边的数量。 一个孤立顶点是一个度为0的顶点:即不是任何一条边的端点的顶点(样例图像描述了一个孤立顶点)。 一个叶子顶点(亦称终端顶点)是一个度为1的顶点。在一个有向图中,可以分清某个节点的出度(从该节点指向其他节点的边的数量),表示为� +(v),入度(从其他节点指向该节点的边的数量),表示�−(v);源点是一个入度为0的顶点,而汇点则是一个出度为0的顶点。简单点是其邻接点形成一个团的点,团中任意两个点均相连。 完全点是一个连接了其余顶点的顶点。

分割点是一个删去后会导致剩余图不再连通的顶点;顶点分割集是一个删去后会导致剩余图不再连通的顶点集合。 K-顶点连通图是指一个删去少于个点总会使剩余图保持连通的图。独立集是一个没有任意一对顶点相连的集合,而覆盖是一个顶点的集合,图中任意一条边都至少有一个端点在此集合中。

如果图的对称性能使得任何顶点映射到任何其他顶点,则该图是顶点传递图。在图枚举和图同构的讨论中,区分已标记顶点和未标记顶点是很重要的。已标记顶点是一个带有额外信息的顶点,使其能够区别于其他标记的顶点;只有当两个图的顶点能有相同的标记节点时,两个图才认为是同构的。仅当基于其于图中的邻接点而不基于任何额外信息时,一个未标记的顶点才可以替代任何其他的顶点。

图的顶点和多边形的顶点有需多的相似之处,因此容易被混淆。多边形的顶点和边可以合起来被视为是一个图,但是多边形还额外描述了顶点的几何位置,事实上,多边形定义出来的图一定是平面图。多边形的点的顶点图则类似于图的顶点的邻居。

图论中的顶点类似于多面体中的顶点,但还是有区别:多面体的网络骨架形成的图形其顶点为多面体的顶点,但多面体顶点具有图理论中不存在的附加结构(其几何位置)。多面体的顶点图类似于图论中的顶点邻域。

相关

  • 氯喹氯喹(Chloroquine),是一种用于治疗及预防疟疾的药物,该药以磷酸盐的形式(即磷酸氯喹)应用于临床。若需治疗特定几种抗药病原株或复杂症状,则需配合其他抗疟药物。偶尔也会用于治疗
  • 支架支架(Stent)是一种应用于植入型外科手术的管状器具,以治疗体内病变的管道例如血管、食道或输尿管等,恢复管道的正常运输功能。支架一般是永久或半永久植入于患者体内,但亦可以意
  • 金帐汗国钦察汗国(英语:Golden Horde;蒙古语:Алтан Орд,Altan Ord)(1242年-1502年)又称金帐汗国或大帐汗国,是蒙古四大汗国之一,元朝称之为大元钦察术赤兀鲁思,对金帐汗庭称为金斡耳朵,称
  • 俄勒冈州立大学俄勒冈州立大学(Oregon State University,OSU)是美国俄勒冈州科瓦利斯的一所公立研究型大学,创立于1868年,创始之初与共济会有很大的联系。该大学共13个学院,林业和农业学科尤为出
  • 纽约上州纽约上州(英语:Upstate New York),美国口语中泛指纽约州除了纽约市及长岛地区以外的所有纽约州,并无官方或正式的行政界线;该区主要以家庭居住的市郊(Suburb)为主,间有几座城市(水牛城
  • Oblast州(Oblast)是一种斯拉夫国家,包括一些苏联国家的行政区划单位。Oblast在中文是一个外来语 ,常被译为“州”。Oblast是白俄罗斯、保加利亚、哈萨克、吉尔吉斯、俄罗斯、乌克兰和
  • J·迈尔·H于尔根·赫曼·迈尔 (德语:Jürgen Hermann Mayer,1965年10月30日-),是一位德国建筑师及艺术家,生于斯图加特,他的建筑事务所J. MAYER H位于德国柏林。迈尔于德国斯图加特大学、美国
  • 国籍国籍是指一个人属于一个国家国民的法律资格,也是国家实行外交保护的依据。各国将国籍作为立法的重要内容,是从十八世纪末,十九世纪初开始的。《世界人权宣言》第十五条规定:“人
  • 1498年重要事件重要人物
  • 泰国农业泰国农业以其竞争激烈、多元化和专业化的特色见称,农产品成功销往世界各地。作为世界稻米市场的其中一个主要出口国,水稻是泰国最重要的农作物,其他主要农产品有鱼类、木薯、橡