顶点 (图论)

✍ dations ◷ 2025-11-09 15:01:44 #图论

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

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

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

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

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

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

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

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

相关

  • 细胞素风暴细胞素风暴、细胞因子风暴(英语:Cytokine storm),又称高细胞因子症(英语:Hypercytokinemia),一种不适当的免疫反应,因为细胞因子与免疫细胞间的正回馈回路而产生。这也被认为是1918年
  • 谷部,为汉字索引中的部首之一,康熙字典214个部首中的第一百五十个(七划的则为第四个)。就繁体和简体中文中,谷部归于七划部首。谷部通常从左方、右方为部字。且无其他部首可用者
  • 密度制约在种群生态学中,密度制约是描述种群密度对种群增长的影响的一种假说。一般认为密度制约效应主要发生在物种的种子和幼苗阶段。
  • 拉斯考克山洞拉斯科洞窟(法语:Grotte de Lascaux)壁画,位于法国多尔多涅省蒙特涅克村的韦泽尔峡谷,是著名的石器时代洞穴壁画。1979年,拉斯科洞窟同韦泽尔峡谷内的许多洞穴壁画一起被选为世界
  • 法国电视台法国电视台(法语:France Télévisions)为法国国营电视台,其资金来源主要为电视授权费用及电视广告收入。旗下频道有法国海外领地广播电视第一台(Réseau Outre-Mer 1ère)、法国
  • 艾利森詹姆斯·帕特里克·艾利森(英语:James Patrick Allison,1948年8月7日-),美国免疫学家,德州大学安德森癌症中心免疫学部主任暨免疫治疗平台行政主任,2018年与本庶佑一同获得诺贝尔生
  • 格雷德卡罗琳·维德尼·卡罗尔·格雷德(英语:Carolyn Widney "Carol" Greider,1961年4月15日-),美国分子生物学家,现任约翰·霍普金斯大学分子生物学与遗传学系教授。她因为“发现端粒和
  • 考试前恐惧症考试焦虑是测试前或测试期间产生害怕心理,引起身心一系列不良反应,往往表现得紧张焦虑、头晕出汗、思维紊乱、记忆模糊、反应迟钝、精神不集中。在中国的高考前易患此病。考试
  • 宝安体育馆中国广东省深圳市宝安区罗田路宝安体育馆,位于中国广东省深圳市宝安区罗田路宝安体育中心。于2002年9月开馆,占地面积8万平方米,建筑面积4.74万平方米。宝安体育馆曾承办第26届
  • 桑戈尔利奥波德·塞达尔·桑戈尔(Léopold Sédar Senghor,1906年10月9日-2001年12月20日),塞内加尔诗人、政治家、文化理论家,1960年至1980年任塞内加尔首任总统,被广泛认为是20世纪最重