顶点 (图论)

✍ dations ◷ 2025-11-30 03:11:05 #图论

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

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

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

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

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

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

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

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

相关

  • 巯嘌呤巯嘌呤(英语:Mercaptopurine,简称6-MP,又名6-巯基嘌呤、巯基嘌呤或巯唑嘌呤)是一种硫嘌呤类化疗药物和免疫抑制剂。1951年,格特鲁德·B·埃利恩和乔治·H·希钦斯用干酪乳杆菌试验
  • 文献学文献学可以指:
  • abbr class=abbr title=R25: 吞食有毒R25/abbr警示性质标准词(英语:Risk Phrases,简写:R-phrases)是于《欧联指导标准67/548/EEC 附录III: 有关危险物品与其储备的特殊风险性质》里定义。该列表被集中并再出版于指导标准2001/
  • 分离板块边缘分离板块边缘(divergent boundary)又称张裂型板块边界,是地壳由于张力作用向两侧扩张延伸,地幔上部经熔融作用冒出产生新的岩石圈。这个地区成为大陆的末端,最终形成大洋盆地。大
  • 油葱酥油葱酥或(炝)炒葱头是台湾菜中最常使用的调味料之一。常见的做法是先将红葱头切丁(也有人切片),再将红葱丁放入滚烫的猪油炸至金黄色(通常最后几分钟,开大火把油逼出来红葱丁才会酥
  • 置入性行销产品 · 定价 · 分销 服务 · 零售 · 宣传 品牌管理 · 大客户营销 营销道德 · 营销效果 营销调查 · 市场调查 市场划分 · 营销战略 市场优势 · 操
  • 独立学院语言 - 文化 - 体育 - 节日 政府 - 政治 - 法律 - 经济 艺术 - 文学 - 舞蹈 - 戏曲独立学院是中国大陆现存的一种高等学校。根据中华人民共和国教育部2008年颁布的《独
  • 国防委员会朝鲜民主主义人民共和国主题朝鲜民主主义人民共和国国务委员会,前身为朝鲜民主主义人民共和国国防委员会,原来与朝鲜劳动党中央军事委员会同为朝鲜军事上的最高统帅机关。在朝
  • 美国领土变迁美国领土变迁(英语:Territorial evolution of the United States)列出美国领土内外边界的变更,以及地位和名称的变化。领土地图上也包括最终成为美国一部分的周边地区。并附有地
  • 图 (数学)在数学的分支图论中,图(Graph)用于表示物件与物件之间的关系,是图论的基本研究对象。一张图由一些小圆点(称为顶点或结点)和连结这些圆点的直线或曲线(称为边)组成。西尔维斯特在187