顶点 (图论)

✍ dations ◷ 2024-09-20 06:07:48 #图论

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

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

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

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

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

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

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

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

相关

  • 舒马曲坦舒马曲坦 (英语:Sumatriptan,或译为舒马普坦)是一种曲坦类药物,用于治疗偏头痛。在结构上,舒马曲坦和蟾毒色胺、5-甲氧基二甲基色胺一样是一种生物碱——二甲基色胺(DMT)的衍生物,其
  • 埃莱夫西纳埃莱夫西纳(希腊语:Ελευσίνα;现代希腊语:.mw-parser-output .Polytonic{font-family:"SBL BibLit","SBL Greek","EB Garamond","EB Garamond 12","Foulis Greek",Cardo,
  • 五险一金五险一金,指中国大陆地区劳动者所享有的社会保险福利的一种通俗化称呼,其中“五险”是指包括养老保险、医疗保险、工伤保险、失业保险、生育保险在内的五种社会保险,“一金”是
  • ISO 639-2ISO 639-2:1998 是国际标准化组织 ISO 639 语言编码标准的第二部分,为各语言和语系所订定的 3 字母语言代码。 ISO 639-2 的注册机构是美国国会图书馆。有 22 种语言同时在
  • 盛行风盛行风,是一个地区某一时段最常刮的风。其风向称为盛行风向。该风主要受大气环流和地貌的影响。观测和了解盛行风有助于预测当地天气,也有助于研究当地气候、土壤风化、沙丘移
  • 拉脱维亚共和国面积以下资讯是以2018年估计国家领袖国内生产总值(购买力平价) 以下资讯是以2016年估计国内生产总值(国际汇率) 以下资讯是以2016年估计人类发展指数 以下资讯是以2018年估计拉
  • 鸡尾酒鸡尾酒(英语:Cocktail)是一种混合饮料,一般含有一种或多种类型的蒸馏酒,通常亦会加入其他原料如利口酒、果汁、天然气泡水、苏打水、通宁水、赛尔脱兹气泡水(seltzer)、茶、咖啡、
  • 第2陆战旅越南战争第2海军陆战师(朝鲜语:제2해병사단/第二海兵師團),别称青龙部队(청룡부대),是大韩民国海军陆战队中的师级步兵单位,因曾参加越南战争而闻名(参战当时为旅级部队)。1965年6月1日
  • 多米尼克总统多米尼克总统是多米尼克1978年从英国独立后的国家元首,但日常权力由总理行使。阿根廷总统 · 巴拉圭总统 · 巴拿马总统 · 巴西总统(沿革:君主) · 加拿大君主(总督) · 秘鲁总
  • 用餐者困境在博弈论中,用餐者困境是一个多参与者的囚徒困境。设想的情景是有若干人出去吃饭,在点菜之前他们达成了一致:所有人平摊买单的钱。现在每个人要么点贵的菜肴,要么点便宜的菜肴。