顶点 (图论)
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/5/5b/6n-graf.svg/220px-6n-graf.svg.png)
在数学中,更确切地说,在图论中,一个顶点(vertex,或多个顶点,vertices)或节点(node)是构成图的基本单位:一个无向图包括一个顶点的集合和一个边(顶点的无序对)的集合,而一个有向图包括一个顶点的集合和一个弧(顶点的有序对)的集合。在一个图的示意图中,一个顶点通常表示为一个带标号的圆形,而一条边表示为连接两个顶点的一条直线或一个箭头。
站在图论的角度上,顶点被视为无特征且不可分割的对象,虽然因为该图的用途不同,他们可能有额外的结构;例如,一个语义网络是一个图,其顶点表示的是概念或对象的类别。
两个被一条边所连接的顶点称作该边的端点,且可以说该边从一个点入射向另一个点。如果一个图包含一条边(v,w),则可以说顶点w相邻顶点v。顶点v的邻域是该图的一个导出子图,由所有与v相邻的顶点组成。
顶点的类型
[编辑]![A small example network with 8 vertices and 10 edges.](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/2/2f/Small_Network.png)
一个顶点的度,表示为𝛿(v),指的是在图中与这个顶点相连的边的数量。 一个孤立顶点是一个度为0的顶点:即不是任何一条边的端点的顶点(样例图像描述了一个孤立顶点)。[1] 一个叶子顶点(亦称终端顶点)是一个度为1的顶点。在一个有向图中,可以分清某个节点的出度(从该节点指向其他节点的边的数量),表示为𝛿 +(v),入度(从其他节点指向该节点的边的数量),表示𝛿−(v);源点是一个入度为0的顶点,而汇点则是一个出度为0的顶点。简单点是其邻接点形成一个团的点,团中任意两个点均相连。 完全点是一个连接了其余顶点的顶点。
分割点是一个删去后会导致剩余图不再连通的顶点;顶点分割集是一个删去后会导致剩余图不再连通的顶点集合。 K-顶点连通图是指一个删去少于k个点总会使剩余图保持连通的图。独立集是一个没有任意一对顶点相连的集合,而覆盖是一个顶点的集合,图中任意一条边都至少有一个端点在此集合中。
如果图的对称性能使得任何顶点映射到任何其他顶点,则该图是顶点传递图。在图枚举和图同构的讨论中,区分已标记顶点和未标记顶点是很重要的。已标记顶点是一个带有额外信息的顶点,使其能够区别于其他标记的顶点;只有当两个图的顶点能有相同的标记节点时,两个图才认为是同构的。仅当基于其于图中的邻接点而不基于任何额外信息时,一个未标记的顶点才可以替代任何其他的顶点。
圖的頂點和多邊形的頂點有需多的相似之處,因此容易被混淆。多邊形的頂點和邊可以合起來被視為是一個圖,但是多邊形還額外描述了頂點的幾何位置,事實上,多邊形定義出來的圖一定是平面圖。多邊形的點的頂點圖則類似於圖的頂點的鄰居。
图论中的顶点类似于多面体中的顶点,但还是有区别:多面体的网络骨架形成的图形其顶点为多面体的顶点,但多面体顶点具有图理论中不存在的附加结构(其几何位置)。多面体的顶点图类似于图论中的顶点邻域。
参见
[编辑]参考文献
[编辑]- ^ 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.
外部链接
[编辑]
|