Multiple edges
Encyclopedia
In graph theory
, multiple edges (also called parallel edges or a multi-edge), are two or more edges that are incident to the same two vertices
. A simple graph has no multiple edges.
Depending on the context, a graph
may be defined so as to either allow or disallow the presence of multiple edges (often in concert with allowing or disallowing loops
):
Multiple edges are, for example, useful in the consideration of electrical network
s, from a graph theoretical point of view.
A planar graph
remains planar if an edge is added between two vertices already joined by an edge, thus adding multiple edges preserves planarity.
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...
, multiple edges (also called parallel edges or a multi-edge), are two or more edges that are incident to the same two vertices
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...
. A simple graph has no multiple edges.
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...
may be defined so as to either allow or disallow the presence of multiple edges (often in concert with allowing or disallowing loops
Loop (graph theory)
In graph theory, a loop is an edge that connects a vertex to itself. A simple graph contains no loops....
):
- Where graphs are defined so as to allow multiple edges and loops, a graph without loops is often called a multigraphMultigraphIn 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 multiple edges and loops, a multigraph or a pseudograph is often defined to mean a "graph" which can have loops and multiple edges.
Multiple edges are, for example, useful in the consideration of electrical network
Electrical network
An electrical network is an interconnection of electrical elements such as resistors, inductors, capacitors, transmission lines, voltage sources, current sources and switches. An electrical circuit is a special type of network, one that has a closed loop giving a return path for the current...
s, from a graph theoretical point of view.
A planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
remains planar if an edge is added between two vertices already joined by an edge, thus adding multiple edges preserves planarity.