顶点 (图论)

✍ dations ◷ 2025-11-30 19:16:45 #图论

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

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

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

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

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

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

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

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

相关

  • 异位妊娠异位妊娠(Ectopic pregnancy),又称为子宫外孕(eccyesis),是指胚胎在子宫以外部位着床的妊娠并发症。典型症状和体征包含腹痛及阴道出血(英语:vaginal bleeding),上述二种症状都有的女
  • 立体专一性立体专一性(stereospecificity)是一个立体化学术语。当一个反应中,反应物可能生成多种(一般即两种:R构型和S构型)立体异构体产物、但实际只生成其中一种产物时,此反应具有立体专一
  • 人工生命体人造生命,又称合成生命,是近期出现的生物技术术语,指利用生物技术干预、改变遗传密码从而产生新的生命个体的研究。创造人造生命是于合成生物学或探索生命的起源领域工作的科学
  • 乔治·勃兰特乔治·勃兰特(瑞典语:Georg Brandt,1694年6月26日-1768年4月29日)瑞典化学家和矿物学家,钴元素的发现者。勃兰特出生于瑞典西曼兰省欣斯卡特贝里教区的里达尔许坦。母亲是Katarina
  • 湿壁画湿壁画(Fresco),原意是“新鲜”,是一种十分耐久的壁饰绘画,泛指在铺上灰泥的墙壁及天花板上绘画的画作,14-16世纪时所形成于意大利。通常是先在墙壁上抹上几层灰泥,有时多达四层。在
  • 杰尼亚杰尼亚 (Ermenegildo Zegna,常缩写为Zegna) 是意大利的一家家族式公司,主要经营高档男士服饰和配饰服装.杰尼亚由Ermenegildo Zegna于1910年在意大利北部皮埃蒙特大区比耶拉省
  • 里夏德·冯·魏茨泽克里夏德·卡尔·冯·魏茨泽克男爵(德语:Dr. Richard Karl Freiherr von Weizsäcker,1920年4月15日-2015年1月31日),是德国的政治家。德国基督教民主联盟成员,曾于1981年任西柏林市
  • 中央博物馆韩国国立中央博物馆位于韩国首尔龙山家族公园,是韩国国立博物馆的中心馆。馆藏旧石器时期到20世纪初的22万余件文物,2013年参观人数在世界艺术博物馆中排名第14位。国立中央博
  • 面部刺青纹面、刺面,又名刺乌鸦喙(台湾话:.mw-parser-output .sans-serif{font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Roboto,Lato,"Helvetica Neue",Helvetica,Arial,s
  • 臧霸臧霸(164年-231年),字宣高,兖州泰山郡华县(今山东费县方城镇)人,汉末三国时期曹魏名将。父亲臧戒为县狱掾,因据守律法不听从太守凭欲私杀狱犯。太守大怒,令人收押戒诣府备罪。时年十八