顶点 (图论)

✍ dations ◷ 2025-12-08 12:02:03 #图论

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

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

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

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

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

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

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

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

相关

  • 分体法分体法(英文:Partonomy),又称为分体学或分体论,是一种基于部分-整体关系的分类系统。分体法不同于生物分类学之类的分类法(taxonomy;又称为分类学),因为后者乃是基于相似性的分类系统
  • 子宫切除手术子宫切除术(hysterectomy)指的通常是由妇产科医生进行的切除子宫的手术。它可分为整个(包括整个子宫和子宫颈)或部分切除。在普遍的情况下,切除卵巢需要与切除子宫手术同时进行。
  • 汉斯·奥斯特汉斯·克海斯提安·奥斯特(丹麦语:Hans Christian Ørsted,1777年8月14日-1851年3月9日),丹麦物理学家、化学家和文学家。在物理学领域,他首先发现载流导线的电流会产生作用力于磁
  • 太阳日太阳日(英语:solar day)是依据太阳运动,所定义的时间,可以分为视太阳日和平太阳日。一太阳日传统称为一“日”、一“天”或一“昼夜”。视太阳日(英语:apparent solar day)是依据真
  • 军事家军事家(英文:Strategist),为具有能对军事活动实施正确指引或者是擅长具体负责军事行动实施的人。依所擅长之不同,可以再细分为战略家和战术家及军事理论家。擅长于军事战略与统筹
  • 罗汉松科罗汉松科(学名:Podocarpaceae)又名竹柏科,松柏纲松柏目的一科,裸子植物,主要生长在热带、亚热带和南半球的温带地区,共有18-19属,约170-200余种,中国有2属14种,都生长在长江以南各地。
  • 苗栗丘陵苗栗丘陵是位于苗栗县后龙溪和大安溪中下游之间的小型丘陵。苗栗丘陵北临后龙溪,南临大安溪,西临台湾海峡,估计丘陵由南到北的总长约29公里,东至西的宽度约14公里,丘陵总共面积估
  • 圣罗伦斯海道圣劳伦斯海道(英语:St. Lawrence Seaway;法语:la Voie Maritime du Saint-Laurent)是一系列连接大西洋至北美五大湖的运河、船闸和航道,以圣劳伦斯河为名。海道全长3,700千米(2,300
  • 达山村屠杀达山村屠杀(Dak Son Massacre),是北越军于越南战争中犯下的屠杀平民罪行。1967年12月5日,一支越军开到南越多乐省达山村,进行“报复性”攻击,该村驻有2000名山民。有600名士兵开进
  • 砂拉越反让渡运动砂拉越人(大多数是马来人、伊班人,包括了阿邦阿迪拉(英语:Abang Haji Abdillah)、莉莉·埃贝魏因(英语:Lily Eberwein)、罗斯里(英语:Rosli Dhobi))砂拉越反让渡运动(马来语:Gerakan Anti-