顶点 (图论)

✍ dations ◷ 2024-12-23 06:00:19 #图论

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

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

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

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

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

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

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

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

相关

  • 辐射电离辐射(英语:ionizing radiation)是指波长短、频率高、能量高的射线(粒子或波的双重形式)。辐射可分为电离辐射和非电离辐射,电离辐射可以从原子或分子里面电离过程(Ionization)中
  • 小指小指,又称小拇指、尾指,是五指里的最后一只手指,长度与拇指相若,但粗细则是五指中最细的一只,有三个关节。在很多国家,“勾小指”有二人互相承诺、约定的意思。
  • 国会议事堂国会议事堂是日本国会所在地,位于东京都千代田区永田町一丁目,竣工于1936年(昭和11年),当时名为帝国议会议事堂。其左侧为众议院,右侧为参议院(旧贵族院)。建筑物呈左右对称,但是两院
  • 1943年孟加拉饥荒1943年孟加拉饥荒发生在1943年,未分开时的孟加拉(现在独立的孟加拉国和印度的西孟加拉邦)。估计有超过300万人死于饥饿、营养不良和饥荒期间有关的疾病。第一种说法是日本的粮
  • 布兰妮·斯皮尔斯布兰妮·简·斯皮尔斯(英语:Britney Jean Spears,1981年12月2日-),是一名美国歌手、词曲作家、舞者与演员。她出生在密西西比州麦库姆,于路易斯安那州的肯特伍德市长大,在童年时期就
  • 孢子植物隐花植物(英语:Cryptogams,命名时类名为Cryptogamae)是指繁殖阶段不形成显著花的植物,因其是通过孢子进行繁殖,故又称孢子植物。Cryptogamae这个类名来自于希腊语的kryptos(意为“
  • 扬州市扬州市(江淮官话扬州话:/iaŋ ʦɤɯ/),简称扬,古称江都、广陵,是中华人民共和国江苏省下辖的地级市,位于江苏省中部,长江北岸。市境北界淮安市,东北接盐城市,东达泰州市,南邻镇江市,西
  • 新竹市立图书馆新竹市文化局图书馆,由新竹市文化局图书资讯课管理。除新竹市文化局内的总馆外,尚设有“香山分馆”、“盐水分馆”、“动物园分馆”。由新竹市东区公所管理的金山图书馆、北区
  • 尼 满尼满(满语:ᠨᡳᠮᠠᠨ,穆麟德:niman,17世纪-1669年),富察氏,满洲镶黄旗人,清朝政治人物。清太宗时期出仕。崇德六年(1641年),考授笔帖式。顺治二年(1645年)特授内三院编修。九年(1652年)正月
  • 吞武里王朝泰国中部:泰国北部:泰国南部:吞武里王国(泰语:อาณาจักรธนบุรี,皇家转写:Anachak Thonburi,泰语发音:),一译统巫里王国,是泰国历史上于1767年至1782年存在的一个泰人王国。