顶点 (图论)

维基百科,自由的百科全书
跳到导航 跳到搜索
一个有6个顶点和7条边的图,其中最左边标号为6的顶点是一个叶子顶点,或称终端顶点

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

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

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

顶点的类型[编辑]

A small example network with 8 vertices and 10 edges.
有8个点(其中一个点被孤立)和10条边的样例网络。

一个顶点的英语Degree_(graph_theory),表示为𝛿(v),指的是在图中与这个顶点相连的边的数量。 一个孤立顶点是一个度为0的顶点;即不是任何一条边的端点的顶点(样例图像描述了一个孤立顶点)。[1] 一个叶子顶点(亦称终端顶点)是一个度为1的顶点。在一个有向图中,可以分清出度(出边的数量),表示为𝛿 +(v),入度(入边的数量),表示𝛿(v);一个起源点是一个入度为0的顶点,而超汇点则是一个出度为0的顶点。一个简单点之一是其邻接点形成一个:任意邻接点两两相连。 一个通用点是一个顶点,其连接了图中所有其余的顶点。

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

如果一个图能令任何顶点到任何其他顶点都对称,则它是顶点可传递的。例如,地图上的任何顶点的任何其它的顶点。 在图的计数图的同构问题中,区分已标记的顶点未标记的顶点是很重要的。一个已标记的顶点是一个带有额外信息的顶点,使其能够区别于其他标记的顶点;只有当两个图的顶点能有相同的标记节点时,两个图才认为是同构的。仅当基于其于图中的邻接点而不基于任何额外信息时,一个未标记的顶点才可以替代任何其他的顶点。

圖的頂點和多邊形的頂點有需多的相似之處,因此容易被混淆。多邊形的頂點和邊可以合起來被視為是一個圖,但是多邊形還額外描述了頂點的幾何位置,事實上,多邊形定義出來的圖一定是平面圖。多邊形的點的頂點圖則類似於圖的頂點的鄰居。

参见[编辑]

参考文献[编辑]

  1. ^ File:Small Network.png; example image of a network with 8 vertices and 10 edges
  • Gallo, Giorgio; Pallotino, Stefano. Shortest path algorithms. Annals of Operations Research. 1988, 13 (1): 1–79. doi:10.1007/BF02288320. 
  • Berge, Claude, Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001)
  • Chartrand, Gary. Introductory graph theory. New York: Dover. 1985. ISBN 0-486-24775-9. 
  • Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press. 1986. ISBN 0-19-853916-9. 
  • Harary, Frank. Graph theory. Reading, Mass.: Addison-Wesley Publishing. 1969. ISBN 0-201-41033-8. 
  • Harary, Frank; Palmer, Edgar M. Graphical enumeration. New York, Academic Press. 1973. ISBN 0-12-324245-2. 

外部链接[编辑]