Loop (graph theory)
In graph theory, a loop or loop is an edge that connects a node to itself. Each loop forms a circle of length one in the graph.
Depending on the context, graphs can be defined to allow or exclude loops (often in conjunction with the allowance of multiple edges ):
- If loops or multiple edges are allowed in the definition of graphs, a graph without loops and multiple edges for differentiation is referred to as a simple graph . A graph without loops is called a loopless, loop-free, or loop-free graph.
- If loops and multiple edges are excluded in the definition of graphs, a graph with loops or multiple edges is called a multigraph to distinguish it .
In an undirected graph , the degree of a node is equal to the number of its neighboring nodes . The loop is a special case in that it increases the degree of a knot by two. The (only) incident node of a loop is counted twice as its own neighbor.
In a directed graph , a loop increases the input and the output level of a node by one. So the incident node of a loop is both its start and end node.