Vertex (graph theory)
In 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.
A graph with 6 vertices and 7 edges
From the point of view of graph theory, vertices are treated as
where the vertex number 6 on the
featureless and indivisible objects, although they may have additional
far-left is a leaf vertex or a pendant
structure depending on the application from which the graph arises; vertex
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.
Contents
Types of vertices
See also
References
External links
Types of vertices
The degree of a vertex, denoted 𝛿(v) in a graph is the number of
edges incident to it. An isolated vertex is a vertex with degree zero;
that is, a vertex that is not an endpoint of any edge (the example image
illustrates one isolated vertex).[1] A leaf vertex (also pendant vertex)
is a vertex with degree one. In a directed graph, one can distinguish
the outdegree (number of outgoing edges), denoted 𝛿 +(v), from the
indegree (number of incoming edges), denoted 𝛿−(v); a source vertex
is a vertex with indegree zero, while a sink vertex is a vertex with Example network with 8 vertices (of
outdegree zero. A simplicial vertex is one whose neighbors form a which one is isolated) and 10 edges.
clique: every two neighbors are adjacent. A universal vertex is a
vertex that is adjacent to every other vertex in the graph.
A cut vertex is a vertex the removal of which would disconnect the remaining graph; a vertex separator is a
collection of vertices the removal of which would disconnect the remaining graph into small pieces. A k-
vertex-connected graph is a graph in which removing fewer than k vertices always leaves the remaining graph
connected. An independent set is a set of vertices no two of which are adjacent, and a vertex cover is a set of
vertices that includes at least one endpoint of each edge in the graph. The vertex space of a graph is a vector
space having a set of basis vectors corresponding with the graph's vertices.
A graph is vertex-transitive if it has symmetries that map any vertex to any other vertex. In the context of graph
enumeration and graph isomorphism it is important to distinguish between labeled vertices and unlabeled
vertices. A labeled vertex is a vertex that is associated with extra information that enables it to be distinguished
from other labeled vertices; two graphs can be considered isomorphic only if the correspondence between their
vertices pairs up vertices with equal labels. An unlabeled vertex is one that can be substituted for any other
vertex based only on its adjacencies in the graph and not based on any additional information.
Vertices in graphs are analogous to, but not the same as, 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.
See also
Node (computer science)
Graph theory
Glossary of graph theory
References
1. File:Small Network.png; example image of a network with 8 vertices and 10 edges
Gallo, Giorgio; Pallotino, Stefano (1988). "Shortest path algorithms". Annals of Operations
Research. 13 (1): 1–79. doi:10.1007/BF02288320 (https://doi.org/10.1007%2FBF02288320).
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 (1985). Introductory graph theory (https://archive.org/details/introductorygrap00
00char). New York: Dover. ISBN 0-486-24775-9.
Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). Graph theory, 1736-1936. Oxford
[Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9.
Harary, Frank (1969). Graph theory. Reading, Mass.: Addison-Wesley Publishing. ISBN 0-201-
41033-8.
Harary, Frank; Palmer, Edgar M. (1973). Graphical enumeration. New York, Academic Press.
ISBN 0-12-324245-2.
External links
Weisstein, Eric W. "Graph Vertex" (https://mathworld.wolfram.com/GraphVertex.html).
MathWorld.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Vertex_(graph_theory)&oldid=971258227"
This page was last edited on 5 August 2020, at 01:22 (UTC).
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this
site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia
Foundation, Inc., a non-profit organization.
