Home Discussion Topics Dictionary Almanac

Signup Login

Loop (graph theory)

Overview

In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a loop (also called a self-loop) is an edge that connects a vertex

Vertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...

to itself. A simple graph contains no loops.

Depending on the context, a graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

or a multigraph

Multigraph

In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge...

may be defined so as to either allow or disallow the presence of loops (often in concert with allowing or disallowing multiple edges

Multiple edges

In graph theory, multiple edges , are two or more edges that are incident to the same two vertices...

between the same vertices):

Where graphs are defined so as to allow loops and multiple edges, a graph without loops is often called a multigraph
Multigraph
In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge...

.
Where graphs are defined so as to disallow loops and multiple edges, a multigraph or a pseudograph is often defined to mean a "graph" which can have loops and multiple edges.

For an undirected graph, the degree

Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex is denoted The maximum degree of a graph G, denoted by Δ, is the maximum degree of its vertices, and the minimum degree of a graph, denoted by δ, is...

of a vertex is equal to the number of adjacent vertices.

A special case is a loop, which adds two to the degree.

Discussion

Ask a question about 'Loop (graph theory)'

Start a new discussion about 'Loop (graph theory)'

Answer questions from other users

Full Discussion Forum

Encyclopedia

In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a loop (also called a self-loop) is an edge that connects a vertex

Vertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...

to itself. A simple graph contains no loops.

Depending on the context, a graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

or a multigraph

Multigraph

In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge...

may be defined so as to either allow or disallow the presence of loops (often in concert with allowing or disallowing multiple edges

Multiple edges

In graph theory, multiple edges , are two or more edges that are incident to the same two vertices...

between the same vertices):

Where graphs are defined so as to allow loops and multiple edges, a graph without loops is often called a multigraph
Multigraph
In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge...

.
Where graphs are defined so as to disallow loops and multiple edges, a multigraph or a pseudograph is often defined to mean a "graph" which can have loops and multiple edges.

Degree

For an undirected graph, the degree

Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex is denoted The maximum degree of a graph G, denoted by Δ, is the maximum degree of its vertices, and the minimum degree of a graph, denoted by δ, is...

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

Directed graph

A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,* a set A of ordered pairs of vertices, called arcs, directed edges, or arrows .It differs from an ordinary or undirected graph, in that the latter is defined in terms of unordered pairs of...

, a loop adds one to the in degree and one to the out degree

Loop (graph theory)

Degree

See also