顶点 (图论)

✍ dations ◷ 2025-11-21 21:51:58 #图论

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

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

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

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

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

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

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

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

相关

  • 图尔奈图尔奈(或译土奈,法语:Tournai,法语发音:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000","Gen
  • 声调声调(英语:Tone)的完整意义是一种附着于音节的高低抑扬(音调,或称音高)。语言学家赵元任从音阶获得灵感,设计了五度调值标记法,以数字1表示最低音,到数字5表示最高音。赵氏五度标记法
  • 性选择性选择或性择是一个进化生物学的理论。此理论解释同一性别的个体(通常是雄性)对交配机会的竞争如何促进性状的演化。同一物种的两个性别之间,通常有至少一个性别必须竞争取得有
  • 北欧十字北欧十字,或斯堪的纳维亚十字是源自北欧地区的旗帜图案;现时北欧国家的国旗上全都有北欧十字图案,但也有其他地区的旗帜上有此图案。图案中的十字是基督教的象征。它可以被视为
  • Ultrasound超声波(英语:Ultrasound),是指任何声波或振动,其频率超过人类耳朵可以听到的最高阈值20kHz(千赫)。超声波由于其高频特性而被广泛应用于医学、工业、情报等众多领域。某些动物,如犬
  • ʎ硬颚边音是辅音的一种,用于一些语言口语中。国际音标中的符号是⟨ʎ⟩(倒置小写y),X-SAMPA符号则为⟨L⟩。硬颚边音的特点有:在很多语言中硬颚边音已经与其他音合并,转变为硬颚近
  • 孝德天皇孝德天皇(596年—654年11月24日),日本第36代天皇(在位:645年7月12日至654年11月24日)。敏达天皇曾孙(宝皇女之弟)。曾因不满苏我氏专权,以患足疾为名,不参与政治。与中臣镰足(藤原镰足)
  • 高句丽族高句丽人是1世纪-7世纪间居住于中国东北地区东部和朝鲜半岛北部的民族,也是高句丽的主体民族。高句丽族的族源是上古时期古老民族秽貊人东迁后的夫余、高夷、沃沮、小水貊、东
  • 鲫(学名:Carassius auratus),通称鲫鱼,俗名鲫瓜子、月鲫仔、土鲫、细头、鲋鱼、寒鲋,为鲤科鲫属的一种,在欧亚地区为常见淡水鱼。鲫鱼经过人工养殖和选育,可以产生许多新品种,例如金
  • 竹市雅俊竹市雅俊(日语:竹市 雅俊/たけいち まさとし Takeichi Masatoshi ?,1943年11月27日-),日本细胞生物学者、胚胎学者,美国国家科学院外籍院士,日本学士院会员。现任理化学研究所多细