顶点 (图论)

✍ dations ◷ 2025-11-22 17:59:40 #图论

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

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

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

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

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

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

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

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

相关

  • 中医药学中医药学(英文:traditional Chinese medicine and pharmacy),是中医学与中药学的合称,侧重反映中医与中药两者共同发展,密不可分。而中医药是中医与中药的合称。
  • 科学方法科学方法(英语:scientific method)指的是检查自然现象、获取新知识或修正与整合先前已得的知识,所使用的一整套技术。为了合乎科学精神,这方法必须建立于收集可观察、可经验(empir
  • g区元素g区元素包括扩展元素周期表中第八周期的第121号元素-138号元素,其中所有元素均尚未被发现,包括:Ubu、Ubb、Ubt、Ubq、Ubp、Ubh、Ubs、Ubo、Ube、Utn、Utu、Utb、Utt、Utq、Utp
  • 瑞利散射瑞利散射(Rayleigh scattering),由英国物理学家约翰·斯特拉特,第三代瑞利男爵(John Strutt, 3rd Baron Rayleigh)的名字命名。它是半径比光或其他电磁辐射的波长小很多的微小颗粒
  • 戈德里奇第一代里彭伯爵弗雷德里克·约翰·罗宾逊,PC(Frederick John Robinson, 1st Earl of Ripon,1782年11月1日-1859年1月28日),英国政治家,曾任英国首相,出生后至1827年,称为F·J·罗宾逊
  • 汽车业汽车产业,或称汽车工业。是生产汽车有关的工业,包括研发、制造同销售等范畴,是世界上一种比较常见的重工业,是目前世界主要经济支柱之一。
  • 露点温度大气物理学 大气力学(英语:Synoptic scale meteorology)天气 (分类) · (主题)气候 (分类) 气候变迁 (分类)露点(英语:Dew point)或露点温度(英语:Dew point temperature)是在固定气
  • 四逆汤四逆汤属于中医方剂的温里剂,出自《伤寒论》,由三味中药组成,其功用为回阳救逆,是用以治疗少阴病的主要方剂之一,症状可见四肢厥冷,恶寒不渴,身痛腹痛,下利清谷,或反不恶寒,面赤烦躁,里
  • 美国小儿科学会美国儿科学会(英语:American Academy of Pediatrics,簡稱AAP)是美国的儿科研究学会,总部位于伊利诺伊州埃尔克格罗夫村(英语:Elk Grove Village),并在华盛顿特区设有办公室。该学会由
  • 荆门市荆门市是中华人民共和国湖北省下辖的地级市,位于湖北省中部。市境南临荆州市、潜江市、天门市,东接孝感市,东北界随州市,西北毗襄阳市,西达宜昌市。地处江汉平原西北部,西北部为荆