顶点 (图论)

✍ dations ◷ 2025-11-26 03:19:15 #图论

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

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

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

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

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

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

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

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

相关

  • 原生生物超类群与门以及众多不同分类会包括的分类单元原生生物(学名:Protist,发音: /ˈproʊtᵻst/)统称真核生物域中,不属于植物、动物和真菌,一般个体微小、多数为单细胞、有细胞核和原生
  • 古典希腊时期古典希腊时期是古希腊的一个历史时期,大约为公元前五到四世纪(一般定义为雅典最后一位僭主被推翻的年份,即公元前510年,至亚历山大大帝去世时的公元前323年)。它前承古风时期,后启
  • 支气管扩张症支气管扩张(英语:Bronchiectasis)指的是肺脏中支气管永久性的扩张。患者的常见症状包括有痰的慢性咳嗽,其他还有呼吸困难、咳血与胸痛等,有些患者同时也有喘鸣与杵状指(英语:nail c
  • 钢铁铁素体(α-Fe) 针状铁素体(acicular α-Fe) 奥氏体(γ-Fe) 马氏体 珠光体(88%铁素体,12%碳化三铁) 贝氏体 粒滴斑铁(珠光体及渗碳体的共晶    混合物,含碳量4.3%) 碳化三铁(Fe3C) β铁
  • 神经纤维层视网膜神经纤维层(英文:Retinal nerve fiber layer, RNFL)由视神经纤维延伸而成,在视孔附近最厚,向锯齿缘方向渐渐变薄。视神经纤维穿过筛板后失去髓鞘,继续穿过脉络膜、视网膜,变
  • font color=white加拿大/font下面是加拿大各大学的列表:
  • SelfridgesSelfridges(官方不使用译名,亦称Selfridge & Co.)是一家英国的高档百货公司,由哈里·戈登·塞尔福里奇于1909年创立,其位于伦敦牛津街的旗舰店在1909年3月15日开业,是目前仅次于哈
  • 唐兰唐兰(1901年1月9日-1979年1月11日),原名张佩,曾用名佩兰、景兰,号立.mw-parser-output ruby>rt,.mw-parser-output ruby>rtc{font-feature-settings:"ruby"1}.mw-parser-output ru
  • 郭绍虞郭绍虞(1893年-1984年6月23日),原名希汾,字绍虞,江苏苏州人,中国语言文学家。郭绍虞出生于清光绪十九年(1893年),其父郭鲁卿世居苏州。早年师从陆尹甫、陆雨庵,1910年在苏州工业中学求
  • 客家文化本文属于客家系列的一部分客家文化,是指客家人共同所创造的文化,包括客家话、戏剧音乐、舞蹈、工艺、民俗等。客家文化源自中原汉人南迁时自身所保留的唐宋时期的华夏文化和中