顶点 (图论)

✍ dations ◷ 2025-11-25 02:12:29 #图论

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

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

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

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

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

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

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

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

相关

  • 斜睾目见内文斜睾目(学名:Plagiorchiida)是吸虫纲复殖亚纲之下两个目之一。本目原来只是复殖亚纲之下五个目之一,但后来这些目现时大多成为了斜睾目之下的亚目。以下为部分本目的科:引
  • 流泪泪或称泪液、泪水,是眼睛外部的泪腺所分泌的液体。泪的原料是血液中的水分,它经由泪腺分泌出来后、通过并润湿眼球表面,之后进入鼻泪管,流入鼻腔内而进入喉咙。 它不只可湿润眼
  • 健康素养健康素养(Health literacy)也称为健康识读,是有能力获得医疗卫生资讯,并且阅读、理解,进而应用此资讯来进行健康相关的决定,也可以依照指示接受治疗。有许多有关健康素养的定义。
  • 达姆亨利克·达姆(Henrik Dam,全名Carl Peter Henrik Dam,1895年2月21日-1976年4月17日,生卒于哥本哈根)是一位丹麦生物化学家与生理学家。由于发现维生素K与此分子在人类生理上的角色
  • 磁阻效应磁阻效应(英语:Magnetoresistance,简称MR)是指材料之电阻随着外加磁场的变化而改变的效应,其物理量的定义,是在有无磁场下的电阻差除上原先电阻,用以代表电阻变化率。有多种可以称
  • Lambda Phi Epsilon(ΛΦΕ)Lambda Phi Epsilon(或称ΛΦΕ、LPhiE、LFE、Lambdas、人中王)是个国际性、以社交为主的亚裔兄弟会。该会被多数希腊组织及联盟承认。其主要活动据点在美国及加拿大。Lambda
  • FOIA《信息自由法》(Freedom of Information Act 简称FOIA,也译作情报自由法、美国信息自由法案)是美国关于联邦政府信息公开化的行政法规,颁布于1967年。《信息自由法》的主要内容
  • 杞梁杞梁(?-前550年),为春秋时期的齐国大夫,名植,一名殖,字梁。在伐莒的战争中殉国,其妻孟姜哭夫于城,城为之崩塌。齐后庄公四年(前550年),他与华周都是齐后庄公的部下将领。曾经讨伐过卫国、
  • 穆罕默德贾瓦德·巴霍纳尔穆罕默德贾瓦德·巴霍纳尔(波斯语:محمد جواد باهنر‎,1933年-1981年8月30日),曾任伊朗伊斯兰共和国第二任总理、伊斯兰共和党总书记。是伊朗执政党伊斯兰共和党创始
  • 亚彭岛亚彭岛是印度尼西亚的岛屿,位于西新畿内亚斯考滕群岛以南的极乐岛湾,西面是努姆岛,东南面是安拜群岛,西南面是库兰群岛,岛上最高点海拔高度1,496米。由亚彭群岛县负责管理,岛上主