Katana VentraIP

Vertex (graph theory)

In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices). In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another.

For other uses, see Vertex (disambiguation).

From the point of view of graph theory, vertices are treated as featureless and indivisible objects, although they may have additional structure depending on the application from which the graph arises; for instance, a semantic network is a graph in which the vertices represent concepts or classes of objects.


The two vertices forming an edge are said to be the endpoints of this edge, and the edge is said to be incident to the vertices. A vertex w is said to be adjacent to another vertex v if the graph contains an edge (v,w). The neighborhood of a vertex v is an induced subgraph of the graph, formed by all vertices adjacent to v.

Node (computer science)

Graph theory

Glossary of graph theory

Gallo, Giorgio; Pallotino, Stefano (1988). "Shortest path algorithms". Annals of Operations Research. 13 (1): 1–79. :10.1007/BF02288320. S2CID 62752810.

doi

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)

Berge, Claude

(1985). Introductory graph theory. New York: Dover. ISBN 0-486-24775-9.

Chartrand, Gary

Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). . Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9.

Graph theory, 1736-1936

(1969). Graph theory. Reading, Mass.: Addison-Wesley Publishing. ISBN 0-201-41033-8.

Harary, Frank

Harary, Frank; Palmer, Edgar M. (1973). Graphical enumeration. New York, Academic Press.  0-12-324245-2.

ISBN

"Graph Vertex". MathWorld.

Weisstein, Eric W.