顶点 (图论)

✍ dations ◷ 2025-07-11 14:47:38 #图论

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

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

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

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

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

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

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

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

相关

  • 橡胶橡胶是一种有弹性的聚合物。橡胶可以从一些植物的树汁中取得,也可以是人造的,两者皆有相当多的应用及产品,例如轮胎、垫圈等,遂成为重要经济作物。橡胶的种植主要集中在东南亚地
  • Fesub2/sub(SOsub4/sub)sub3/sub硫酸铁是铁(III)的硫酸盐,化学式为Fe2(SO4)3。无水物存在单斜和菱方两种晶型。其水合物可溶于水。它被用作媒染剂以及工业废水的凝结剂,也用于颜料中。医药上用硫酸铁作收敛剂
  • 欧洲部分欧洲俄罗斯(俄语:Европейская часть России), 简称欧俄,是指俄罗斯位于欧洲的部分,为俄罗斯在历史与文化上主要的组成区块。面积约396万平方公里,占俄罗斯领
  • 伊尼亚士埃涅阿斯(希腊文:Αινείας,Aineías),也译作“伊尼亚斯”,特洛伊英雄,宙斯7世孙,达达诺斯6世孙,厄里克托尼俄斯2世5世孙,特洛斯玄孙,阿萨剌科斯曾孙,卡皮斯孙,安基塞斯王子与爱神
  • 福音教派福音主义(英语:evangelicalism),为新教神学影响层面最为广阔的神学主张之一,起源于1870年代的英国。在不同的时期中,福音神学一词经常会被立场更为开放的新神学主张作为比较的对象
  • 国家安全研究备忘录第200号国家安全研究备忘录第200号(即National Security Study Memorandum 200或简称NSSM200)是指在时任美国国务卿亨利·基辛格主导下,由美国国家安全委员会(The United States Nation
  • 大小金川之役大小金川之役,又称平定两金川,是清乾隆年间清军平定四川西北部大、小金川土司两次动乱的合称。第一次金川之役为乾隆十二年(1747年)大金川安抚司莎罗奔私自进攻明正土司,清廷调兵
  • 景宗朝鲜景宗(朝鲜语:조선 경종/朝鮮 景宗 Joseon Gyeongjong;1688年11月20日(十月二十八)-1724年10月11日(八月二十五)),名李昀(朝鲜语:이윤/李昀 Yi Yun),是朝鲜王朝的第20代君主,1720年至172
  • 罗淑蕾罗淑蕾(1952年11月28日-),中国国民党籍及亲民党中华民国台北市政治人物,会计师出身,曾连任三届立法委员、中华民国会计师公会全国联合会理事长、台北市会计师公会理事长。2018年9
  • 莒照小片莒照小片,是汉语官话方言胶辽官话青莱片的一个片区(原属冀鲁官话沧惠片),主要分布于山东省莒县、莒南县、日照市(东港区、岚山区)和江苏省赣榆县部分地区。 五莲县虽属日照市,但其