Adjacent Vertices
Definition of Adjacent Vertices
Adjacent vertices have a common edge between, the opposite endpoints of this edge are the adjacent vertices.
Generalised As
Vertex.
Related Terms
Hypergraphs
Most definitions of adjacent vertices refer to two vertices. This is because in most graphs, edges connect two vertices in graph theory. But this is not always the case; in a so-called hypergraph, an edge can have several endpoints.
Multigraph
A multigraph adds two elements to the simple graph: multiple edges and edges from a vertex to itself, a so-called self-loop. Can a vertex be adjacent to itself? Yes, at a vertex with a loop, both endpoints are the same; the vertex 'sees' itself as an adjacent vertex.
Neighbourhood
The closed neighbourhood of a vertex in a graph is the subgraph induced by all the vertices adjacent to this vertex, including the vertex itself. The properties of a neighbourhood are used in many graph definitions and algorithms.
An example of the use of neighbour vertices is the vertex degree. In an undirected graph, the degree of a vertex is equal to the number of adjacent vertices, the neighbourhood of a vertex.
Other related terms
- Isolated vertex: when a vertex is not adjacent to other vertices.
- Complete graph: if all vertices are adjacent to each other, every possible edge is present.
- Adjacent edges: Not only vertices can be adjacent in a graph. Also, edges can be adjacent. These edges share a common vertex. More common is the synonym incident edges for these.
- Adjacency matrix.
- Adjacency list.
- Graph theory