顶点 (图论)

✍ dations ◷ 2025-12-03 09:53:34 #图论

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

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

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

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

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

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

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

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

相关

  • β-内酰胺β-内酰胺(英语:β-lactam)是一种四元内酰胺环,内酰胺(Lactam)指环状的酰胺。因氨基在酰胺结构第β个碳原子上组成四元环,故称β-内酰胺。同理,若氨基在酰胺结构第γ、δ个碳原子上
  • 胃及十二指肠溃疡消化性溃疡(英语:peptic ulcer disease,简称PUD),又称胃及十二指肠溃疡。这是指胃、小肠前段(十二指肠)或幽门,有时也包含了食道下端的黏膜损伤(溃疡)。在胃发生的溃疡称作胃溃疡(英语:s
  • 牙龈牙龈(又称龂;俗称牙床、牙花子;客家话称牙舷肉),牙龈由软组织构成。牙龈位于牙齿根部(称为牙根)周围。护理牙龈与护理牙齿一样重要。是人或动物口腔内的粘膜组织,下接牙槽骨的骨膜,向
  • 脱氧核糖核苷酸去氧核糖核苷酸(英语:deoxyribonucleotide)是DNA(脱氧核糖核酸,英语:deoxyribonucleic acid)的小分子单体。每个脱氧核糖核苷酸包括三个部分:一个碱基、一个脱氧核糖和一个磷酸基团
  • 流行性疾病流行病(Epidemic)指可以感染众多人口的疾病,但不一定为传染病。流行病可以只是在某地区发生,亦可以是全球大流行。欧洲语言中,辞源均来自希腊语,如英语的epidemic,法语的épidémie
  • 松下村塾坐标:34°24′43.8″N 131°25′02.4″E / 34.412167°N 131.417333°E / 34.412167; 131.417333松下村塾是日本在19世纪后半期位于长州藩萩城下松本村(位于现在的山口县萩市)
  • 李达李达可能指以下列人物:
  • 提取引发遗忘提取引发遗忘(英语:retrieval-induced forgetting或RIF)是一种因回想而遗忘其他记忆讯息的现象。这个现象最早在1994年获得演示,尽管RIF的概念已在提取抑制理论的背景下被讨论过
  • 肯特州立大学枪击事件肯特州立大学枪击案(也称五·四屠杀或肯特州立大学屠杀)于1970年5月4日(星期一)发生在美国俄亥俄州肯特城肯特州立大学。当时国民警卫队向骚乱学生在13秒内射出67发子弹,造成4名
  • 法国国家图书馆法国国家图书馆(法语:Bibliothèque nationale de France,BnF)是法国的国家图书馆,也是法国最重要的图书馆之一。它的前身是查理五世在1368年建立的国王图书馆,在路易十四治下取得