顶点 (图论)

维基百科,自由的百科全书
跳到导航 跳到搜索
一个有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个点后总会使剩余图联通。 一个独立集是一个顶点的集合,其中没有任何两个顶点相连,而一个覆盖是一个顶点的集合,其中对于图中的任意一条边,都至少有一个该边的端点包含在此集合中。The vertex space of a graph is a vector space having a set of basis vectors corresponding with the graph's vertices.

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

在图中的顶点都是相似却不相同的,vertices of polyhedra: the skeleton of a polyhedron forms a graph, the vertices of which are the vertices of the polyhedron, but polyhedron vertices have additional structure (their geometric location) that is not assumed to be present in graph theory. The vertex figure of a vertex in a polyhedron is analogous to the neighborhood of a vertex in a graph.

参见[编辑]

参考文献[编辑]

  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. 

外部链接[编辑]