顶点 (图论)

✍ dations ◷ 2025-07-19 06:41:23 #图论

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

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

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

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

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

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

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

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

相关

  • 中指中指是人类手上的第三只手指,也是五只手指中最长的,位于食指与无名指之间。将中指举起在世界不同地方(最普遍为西方)也有粗口的不文象征,示意侮辱他人;详见举中指。
  • 家蚕家蚕(学名:Bombyx mori)是鳞翅目的昆虫,丝绸的主要原料来源,在人类经济生活及文化历史上占有重要地位。原产中国,华南地区俗称之蚕宝宝或娘仔。家蚕的英文名为“silkworm”(意为“
  • 与西班牙交战瑞典与神圣罗马帝国寻求赔款之后,法国首相黎塞留向西班牙宣战,因为法国领土被哈布斯堡王朝包围,成为法国称霸的最大障碍。这场冲突是法国对三十年战争的目标的延续,法军很快入侵
  • 谢尔盖·拉夫罗夫谢尔盖·维克托罗维奇·拉夫罗夫(俄语:Серге́й Ви́кторович Лавро́в;1950年3月21日-),苏联及俄罗斯职业外交官,现任俄罗斯联邦外交部部长。拉夫罗夫1972
  • 玉山玉山,泛指玉山主峰,位于台湾嘉义县阿里山乡中山村、南投县信义乡东埔村与高雄市桃源区梅山里交界处,海拔3,952.43±0.045米,为台湾最高峰,百岳之首。布农族称其为 Saviah/Savih、
  • 卡罗卢斯·克卢修斯卡罗卢斯·克卢修斯(Carolus Clusius)(又名夏尔·德莱克吕兹Charles de l'Écluse)(1526年2月19日阿拉斯 – 1609年4月4日莱顿)植物学家。曾为维也纳的哈布斯堡家族的御医,也是植物
  • [Ni(Nsub2/subHsub4/sub)sub3/sub]sup2+/su硝酸肼镍(NHN)是一种无机化合物,化学式为(NO3)2,是一种含能材料。将水合肼缓慢滴加至65℃的硝酸镍溶液中,滴加时搅拌。温度下降后分离产物并干燥。硝酸肼镍难溶于水、乙醇、丙酮,
  • 台北市立关渡医院台北市立关渡医院,院址在台北市北投区知行路225巷12号,为台北市政府于关渡地区所设立的一所市立医院,1999年馆舍竣工,2000年7月22日开幕启用,以慢性病医疗为医院发展重点。自启用
  • 商务专机商务喷气式飞机(business jet)为一种用于私人、企业人员和政府要员运输的喷气客机。在两岸有不同的名称,又称公务喷气式飞机或行政专机。和航空公司的客机出售机票给个别乘客不
  • 中日韩相容字元中日韩兼容字符(3300–33FF)包含电报符号中的几个小时,该月的天,各种拉丁文单位的片假名等简称,还有日本年号㍻、㍼、㍽、㍾(可是“㋿”因本区码位已满,而放在上一区中日韩带圈字符