顶点 (图论)

✍ dations ◷ 2025-04-26 12:52:40 #图论

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

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

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

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

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

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

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

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

相关

  • 玻璃体玻璃体又称玻璃状液、神膏(英文 Vitreous humor),是眼球内无色透明的胶状物质,表面覆盖着玻璃体膜。玻璃体填充于晶状体与视网膜之间,约占眼球内腔的4/5。玻璃体对视网膜起支撑作
  • 趋异演化趋异演化(英语:Divergent evolution)是指两个或多个生物学特征具有共同演化起源,但在演化历程中逐渐分化的现象,又称适应。可经由观察不同物种的型态或生物分子,如基因或一些生化
  • 欧阳予欧阳予(1927年7月26日-),中国核反应堆及核电工程专家。1927年生于四川乐山。1948年毕业于国立武汉大学工学院电机系。1957年获苏联莫斯科动力学院技术科学博士学位。2000年当选
  • 泻湖潟湖是一种因为海湾被沙洲所封闭而演变成的湖泊,所以一般都在海边。这些湖本来都是海湾,后来在海湾的出海口处由于泥沙沉积,使出海口形成了沙洲,继而将海湾与海洋分隔,因而成为湖
  • 岩溶地貌喀斯特地形(英语:karst topography),又称溶蚀地形、石灰岩地形,是具有溶蚀力的水对可溶性岩石进行溶蚀等作用所形成的地表和地下形态的总称。又称岩溶地貌。水对可溶性岩石所进行
  • 东京港东京港(日语:東京港/とうきょうこう Tōkyō Kō ?)是位于日本东京都的港口,濒临东京湾,为国土交通省指定的国际战略港湾(日语:国際戦略港湾)和日本三个超级中枢港湾(日语:スーパー中
  • 保罗·艾伦保罗·加德纳·艾伦(英语:Paul Gardner Allen,1953年1月21日-2018年10月15日),美国发明家、投资者、考古学家和慈善家,微软的两位创始人之一。2013年,艾伦在福布斯全球富豪榜排名第5
  • 九十九岛九十九岛(日语:九十九島/くじゅうくしま Kujūkushima */?)是日本的溺湾群岛,位于长崎县佐世保市和平户市一带的北松浦半岛(日语:北松浦半島)西侧沿岸。九十九岛全域皆属于西海国
  • 月球探险车阿波罗月球车(英语:Lunar Roving Vehicle)是1971至1972年期间,阿波罗计划中第十五、十六和十七次登月任务中,宇航员使用的月球车。外号为“Moon Buggy”,这个称呼源自于沙滩车的俗
  • 盾臂龟苏卡达象龟(学名:Centrochelys sulcata)又名非洲盾臂龟、盾臂龟及苏卡塔尔陆龟,原为象龟属,之后被分入Centrochelys属,目前是Centrochelys属下的唯一现存的物种。原产于非洲的撒哈