Loop (graph theory)

from Wikipedia, the free encyclopedia
Graph with a loop in knot 1.

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 .

Node degree

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.