顶点 (图论)

✍ dations ◷ 2025-09-17 05:41:40 #图论

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

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

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

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

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

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

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

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

相关

  • 版面费版面费,是指学术期刊向文章发表者收取的一种费用。收取版面费的现象,在世界各国的学术界普遍存在。多数理论型学术刊物,较难走入市场,版面费的收取目的是为了弥补办刊经费的不足
  • 异特龙可疑物种异特龙属(属名:Allosaurus)又称异龙或跃龙,是兽脚亚目肉食龙下目恐龙的一属。异特龙是种大型的二足、掠食性恐龙,平均身长为8.5米,最长可达12到13米。它们生存于晚侏罗纪
  • 自然村落自然村落(自然村),指的是自然形成的聚落,而不是国家以政治力量划分的区划(此种被称为行政村)。中国南方的湖南小的地名常冠以“冲”如“韶山冲”即指“自然村落”,这与南方地区多丘
  • 杉树杉木(学名:Cunninghamia lanceolata)又称福州杉、刺杉,为柏科杉木属植物。原产于中国及越南,并有一变种峦大杉,分布在台湾,模式标本采自浙江舟山。常绿乔木,高可达30米以上;树冠常呈
  • 南极-艾特肯盆地南极-艾特肯盆地(英语:South Pole–Aitken basin)是月球背面一座巨大的撞击陨石坑,直径大约2500公里,深13公里,最大落差(从坑底最深处到最高壁顶处)16.1公里,它是太阳系中已知最大的
  • 储物症囤积症或储物症(英文: Compulsive hoarding,或强迫性囤积症、病态性囤积症、弃置恐惧症),一种强迫行为,过度性地收购或收集物件,即使是不值钱、有危险性或不卫生的物品。强迫性囤积
  • MG149案柯文哲系列柯P新政柯P新政建设柯文哲现象争议政党歌曲其它相关MG149案,是2014年台北市长选举期间的争议事件。无党籍市长候选人柯文哲为国立台湾大学医学院附设医院加护病房
  • 米尔福德峡湾米尔福德峡湾或称米佛峡湾(英语:Milford Sound、毛利语:Piopiotahi)是位于新西兰南岛的西南部峡湾国家公园内的一处冰河地形,在1990年被列入世界遗产蒂瓦希波乌纳穆,在毛利语的意
  • 戚雅仙戚雅仙(1928年2月-2003年1月27日),原名戚爱英,浙江余姚人,生于上海,中国越剧表演艺术家。越剧中“戚派”的创立者。1928年2月,出生于上海,家境清贫。1941年,入上海陶叶剧团科班,学习越
  • 丁香鱼日本银带鲱(学名:),俗名丁香鱼、魩仔,为辐鳍鱼纲鲱形目鲱科的其中一种。本鱼分布于印度西太平洋海域,包括东非、红海、马尔代夫、塞舌尔群岛、斯里兰卡、印度、马来西亚、印尼、泰