Loop (graph theory)

A graph with a loop on vertex 1

In graph theory, a loop (also called a self-loop or a "buckle") is an edge that connects a vertex to itself. A simple graph contains no loops.

Depending on the context, a graph or a multigraph may be defined so as to either allow or disallow the presence of loops (often in concert with allowing or disallowing multiple edges between the same vertices):

Degree

For an undirected graph, the degree of a vertex is equal to the number of adjacent vertices.

A special case is a loop, which adds two to the degree. This can be understood by letting each connection of the loop edge count as its own adjacent vertex. In other words, a vertex with a loop "sees" itself as an adjacent vertex from both ends of the edge thus adding two, not one, to the degree.

For a directed graph, a loop adds one to the in degree and one to the out degree.

Notes

    References

    External links

    See also

    Loops in Graph Theory

    Loops in Topology

    This article is issued from Wikipedia - version of the Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.