顶点 (图论)

✍ dations ◷ 2025-12-01 02:37:28 #图论

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

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

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

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

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

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

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

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

相关

  • 阿尔泰语系阿尔泰语系(英语:Altaic languages),别译阿勒泰语系,是一个按照语言系属分类方法所划分的一组假说性语系,主要将突厥语族、蒙古语族和通古斯语族划为一个语系,有时朝鲜语、琉球语、
  • 高科技产业卫星导航系统高科技,或称高技术、高新,指的是最先进的尖端科技。对于高科技来说,并没有什么特别的分类法,到了1960年代,商家为了促销,把只要不是低科技(英语:Low technology)的产品都
  • 老红砂岩老红砂岩(Old Red Sandstone)主要指分布于欧洲西北部的泥盆纪陆相沉积物。在陆地上,苏格兰东北部沿海区域,奥克尼群岛(Orkney Island),设得兰群岛(Shetland Island),米德兰山谷(Midland
  • 白细胞计数全血细胞计数(英文:complete blood count,CBC; full blood count,FBC),又称为血常规、血象、血细胞分析、血液细胞分析、血细胞计数 或 血液细胞计数,是医生或其他医学专业人员常常
  • 定比定律即每一种化合物,不论是天然存在的,还是人工合成的,也不论它是用什么方法制备的,其组成元素的质量比一定,于1799年由普劳斯特提出。换句话说,就是每一种化合物都有一定的组成,又称定
  • 闫妮闫妮(1971年3月10日-),陕西省西安市人,原名闫凯艳。空军电视艺术中心女演员。曾获得过中国电视金鹰奖最佳表演艺术演员。闫妮是从舞台上开始她的演艺生涯,1999年初次登上银幕。她
  • 拉赫曼谢赫·穆吉布·拉赫曼(孟加拉语:শেখ মুজিবুর রহমান,英语:Sheikh Mujibur Rahman,1920年3月17日-1975年8月15日,生于汤基帕拉乌帕齐拉),东巴基斯坦政治领袖、孟加拉人
  • 朝鲜人民内务军朝鲜人民内务军(韩语:조선인민내무군)隶属于朝鲜民主主义人民共和国人民保安部的治安部队。人民保安部第一副部长李泰哲上将兼任人民内务军司令员。2010年初,人民保安省改称人民
  • 湘桂.mw-parser-output .RMbox{box-shadow:0 2px 2px 0 rgba(0,0,0,.14),0 1px 5px 0 rgba(0,0,0,.12),0 3px 1px -2px rgba(0,0,0,.2)}.mw-parser-output .RMinline{float:none
  • 灼伤灼伤是指皮肤或其他组织因热力、电力、化学物质、摩擦力或辐射所造成的创伤。大部分的灼伤是因接触滚烫液体、固体或火焰的高温。暴露在烹饪的火焰或不安全的煮食器具的危险