In
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, multiple edges (also called parallel edges or a multi-edge), are, in an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
, two or more
edges that are
incident
Incident may refer to:
* A property of a graph in graph theory
* ''Incident'' (film), a 1948 film noir
* Incident (festival), a cultural festival of The National Institute of Technology in Surathkal, Karnataka, India
* Incident (Scientology), a ...
to the same two
vertices, or in a
directed graph, two or more edges with both the same tail vertex and the same head vertex. A
simple graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
has no multiple edges and no
loops.
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):
*Where graphs are defined so as to ''allow'' multiple edges and loops, a graph without loops or multiple edges is often distinguished from other graphs by calling it a ''simple graph.''
*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
An electrical network is an interconnection of electrical components (e.g., batteries, resistors, inductors, capacitors, switches, transistors) or a model of such an interconnection, consisting of electrical elements (e.g., voltage sources ...
s, from a graph theoretical point of view. Additionally, they constitute the core differentiating feature of
multidimensional networks.
A
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. In other words, it can be drawn in such a way that no edges cro ...
remains planar if an edge is added between two vertices already joined by an edge; thus, adding multiple edges preserves planarity.
[Gross (1998)]
p. 308
A
dipole graph is a graph with two vertices, in which all edges are parallel to each other.
Notes
References
* Balakrishnan, V. K.; ''Graph Theory'', McGraw-Hill; 1 edition (February 1, 1997). .
* Bollobás, Béla; ''Modern Graph Theory'', Springer; 1st edition (August 12, 2002). .
* Diestel, Reinhard; ''Graph Theory'', Springer; 2nd edition (February 18, 2000). .
* Gross, Jonathon L, and Yellen, Jay; ''Graph Theory and Its Applications'', CRC Press (December 30, 1998). .
* Gross, Jonathon L, and Yellen, Jay; (eds); ''Handbook of Graph Theory''. CRC (December 29, 2003). .
* Zwillinger, Daniel; ''CRC Standard Mathematical Tables and Formulae'', Chapman & Hall/CRC; 31st edition (November 27, 2002). {{isbn, 1-58488-291-3.
Graph theory objects