顶点 (图论)

✍ dations ◷ 2025-05-20 03:52:01 #图论

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

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

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

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

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

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

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

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

相关

  • 药物的副作用在医学中,副作用(英语:side effect)是指药品往往有多种作用,作用于不同身体部位受体,治疗时利用其一种或一部分受体作用,其他作用或是受体产生作用即变成为副作用。虽然副作用一词
  • 锉刀锉刀是一种用于从工件上去除微量材料的工具。在木工、金属加工和其他类似的贸易和爱好工作中很常见。锉刀大多数是手工工具,由矩形,正方形,三角形或圆形横截面的表面硬化钢筋制
  • 规则溶液在化学中,规则溶液(英语:Regular Solution) 为最接近理想溶液之真实溶液,满足准化学模式,溶液的混合焓不等于0(理想溶液混合焓=0),溶液混合时总体积等于所有溶液成分之体积加总(同
  • 蒙古大汗蒙古大汗(蒙古语:Монголын хаан),是蒙古汗国的最高首领的称号,即可汗或称大汗,类似于中国的皇帝称号。该称号从13世纪蒙古帝国时期开始,直到20世纪时结束。相对的,蒙古
  • 鲍林格林鲍林格林州立大学(Bowling Green State University,简称BGSU)是一所位于美国俄亥俄州鲍林格林的四年制公立大学。学生总人数超过两万人,有3000名研究生。这所大学提供200种大学
  • E-3E-3望楼式预警机(又译为哨兵式)是波音公司生产的全天候空中预警机(AWACS),主力提供管制、控制、通讯、侦搜等功能。美国、英国、沙特阿拉伯、法国、北约组织等国家或组织都有使用
  • CH-47支奴干直升机CH-47“支努幹”直升机(英语:CH-47 Chinook)是由美国波音公司制造的一款多功能、双发动机,双旋翼的中型运输直升机,得名于美洲原住民支努幹族。该机种的主要任务是部队运输、火炮
  • 利比里亚国旗利比里亚国旗为红白相间的条纹、左上角蓝底,象征利比里亚和美国的特殊关系,利比里亚的最早定居者是从美国获得自由归来的美国黑奴。国旗中红、白相间的11道条纹,表示利比里亚18
  • 玩具总动员《玩具总动员》(英语:Toy Story)是一部于1995年上映的美国计算机动画冒险伙伴(英语:Buddy film)喜剧片,由皮克斯动画工作室制作,华特迪士尼影业发行。该片是约翰·拉塞特的导演处女
  • 高岭石高岭土(英语:Kaolinite),又称观音土、白鳝泥、膨土岩、斑脱石、甘土、皂土、陶土、白泥,是一种含铝的硅酸盐矿物,呈白色软泥状,颗粒细腻,状似面粉。其化学成分相当稳定,被誉为“万能