顶点 (图论)

✍ dations ◷ 2025-12-10 21:37:04 #图论

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

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

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

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

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

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

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

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

相关

  • 四国联盟四国联盟(英语:G4 Nations)是指由印度、巴西、德国及日本四国组成的联盟,希望通过相互支持加入联合国安全理事会,并成为联合国安理会常任理事国。联合国安理会目前有五个常任理事
  • 伍荣生伍荣生(1934年1月17日-),浙江瑞安人,中国气象学家。生于浙江瑞安。早年就读于云峰中心小学,1952年从瑞安中学考入南京大学。1956年南京大学气象系毕业,毕业后留校任教。曾任南京大
  • 海军教育训练暨准则发展指挥部海军教育训练暨准则发展指挥部,简称海军教准部,为中华民国海军最高教育训练机关,为国防部海军司令部下辖机关,成立于1948年(民国37年)。使命为落实“训练基础、精练组合、验证联合
  • 姐妹群旁系群在支序分类学是指一个演化支上某个单系群最亲近的分类群,又称为姐妹群。如下图所示: .mw-parser-output table.clade{border-spacing:0;margin:0;font-size:100%;line-h
  • 龙纹身的女孩《龙纹身的女孩》(Män som hatar kvinnor,原意为“憎恨女人的男人”〔Men Who Hate women〕)是一部2009年瑞典惊悚电影,改编自瑞典作者/记者史迪格·拉森的同名小说。这是千禧
  • 可展曲面可展曲面是在其上每一点处高斯曲率为零的曲面。有一个一般性的定理表明:一片具有常数高斯曲率的曲面能够经弯曲(非拉伸、收缩、皱褶或撕裂)而变为任何一片具有相同常数高斯曲率
  • 锡戈内拉海军航空基地锡戈内拉基地(NATO Base Sigonella,IATA代码:NSY;ICAO代码:LICZ),或译西哥奈拉基地,是一座位于意大利西西里岛的北约军用机场及大型后勤基地,由美国海军和意大利空军共用,美方称作锡戈
  • 卡罗莱纳语加罗林语是一种南岛语言,起源于加罗林群岛,但主要为北马里亚纳群岛居民所使用。加罗林人将该语言与英语一起作为常用语言。世界上约有3,100名母语人士。
  • 卡加延河谷区卡加延河谷是菲律宾第二大区,位于吕宋岛东部,包括5个省和3个市:巴丹群岛省、卡加延省、伊莎贝拉省、新比斯开省和季里诺省以及卡加延市、土格加劳市和圣地牙哥市。大区首府设在
  • 浏洪高速公路浏洪高速公路(湖南地方高速公路,湖南高速公路编号S19,原编号S30),整个高速路段位于湖南省长沙市辖域境内,起点在湘赣二省洪口界,终点为长永高速公路永安互通。全线自湘赣界洪口界对