顶点 (图论)

✍ dations ◷ 2025-06-09 20:17:23 #图论

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

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

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

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

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

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

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

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

相关

  • 经济发展经济发展是种随资本主义发展出现的累积过程。其基本要素除了包括经济成长所带来的总量产出与收入结构变化外,经济结构的变迁、人民生活品质提高与福利改善、社会政治体制的变
  • 义肢装具师义肢装具师(英语:Prosthetist),指负责量制、评估、制作、校正义肢的专业人员。和“义肢师傅”最大差别在于义肢装具师需拥有相关学历及临床训练,并且在执业时亲自接触患者。义肢
  • 波特兰州立大学波特兰州立大学(英语:Portland State University,缩写:PSU)是一所位于美国俄勒冈州波特兰的公立研究型大学,成立于1946年,现是俄勒冈州本科及研究生人数最多的大学。2017年,其录取率
  • 延迟存储电子自动计算器电子延迟存储自动计算器(英文:Electronic Delay Storage Auto-matic Calculator、EDSAC)是英国的早期计算机。1946年,英国剑桥大学数学实验室的莫里斯·威尔克斯教授和他的团队
  • 座囊菌亚纲煤炱目 Capnodiales 座囊菌目 Dothideales 多腔菌目 Myriangiales座囊菌亚纲(学名:Dothideomycetidae)是子囊菌门座囊菌纲下的亚纲,共包含座囊菌目(Dothideales)、多腔菌目(Myriang
  • 正黄旗正黄旗(满语:ᡤᡠᠯᡠᡧᡠᠸᠠᠶᠠᠨᡤᡡᠰᠠ,穆麟德:gulu suwayan gūsa,太清:gulu suwayan gvsa),又作“整黄旗”,清代八旗之一,以旗色纯黄而得名。与镶黄旗、正白旗并列为“上三旗
  • 国家西班牙大学国家西班牙大学(National Hispanic University,缩写:NHU)是位于美国加利福尼亚州圣何塞的一所小型私立大学,1981年成立于奥克兰,1994年迁至圣何塞。它隶属于劳瑞德国际大学联盟, 20
  • 俄克拉荷马州立俄克拉何马州立大学静水市校区(Oklahoma State University-Stillwater,简称Oklahoma State、OK-State或OSU)是一所四年制公立大学,位于俄克拉何马州斯蒂尔沃特(Stillwater),是俄
  • 傅柯前苏格拉底 · 古代 中世纪 · 文艺复兴 17世纪 · 18世纪 · 19世纪 · 20世纪 后现代 · 当代米歇尔·福柯(法语:Michel Foucault,1926年10月15日-1984年6月25日),
  • 菲律宾经济$2570 亿美元(2012) $4243亿美元 PPP (2012)$2,614 (2012) (nominal 126th) $4,430 (2012)菲律宾是东南亚第四大规模的新兴工业