Multigraph

Last updated

In mathematics, and more specifically in graph theory, a multigraph (in contrast to a simple graph) is a graph which is permitted to have multiple edges (also called parallel edges [1] ), that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge.

Mathematics includes the study of such topics as quantity, structure, space, and change.

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 which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

In 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 vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

Contents

There are two distinct notions of multiple edges:

• Edges without own identity: The identity of an edge is defined solely by the two nodes it connects. In this case, the term "multiple edges" means that the same edge can occur several times between these two nodes.
• Edges with own identity: Edges are primitive entities just like nodes. When multiple edges connect two nodes, these are different edges.

A multigraph is different from a hypergraph, which is a graph in which an edge can connect any number of nodes, not just two.

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. Formally, a hypergraph is a pair where is a set of elements called nodes or vertices, and is a set of non-empty subsets of called hyperedges or edges. Therefore, is a subset of , where is the power set of .

For some authors, the terms pseudograph and multigraph are synonymous. For others, a pseudograph is a multigraph that is permitted to have loops.

In graph theory, a loop is an edge that connects a vertex to itself. A simple graph contains no loops.

Undirected multigraph (edges without own identity)

A multigraph G is an ordered pair G:=(V, E) with

• V a set of vertices or nodes,
• E a multiset of unordered pairs of vertices, called edges or lines.

In mathematics, a set is a collection of distinct objects, considered as an object in its own right. For example, the numbers 2, 4, and 6 are distinct objects when considered separately, but when they are considered collectively they form a single set of size three, written {2, 4, 6}. The concept of a set is one of the most fundamental in mathematics. Developed at the end of the 19th century, set theory is now a ubiquitous part of mathematics, and can be used as a foundation from which nearly all of mathematics can be derived. In mathematics education, elementary topics from set theory such as Venn diagrams are taught at a young age, while more advanced concepts are taught as part of a university degree.

In mathematics, a multiset is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The positive integer number of instances, given for each element is called the multiplicity of this element in the multiset. As a consequence, an infinite number of multisets exist, which contain only elements a and b, but vary by the multiplicity of their elements:

Undirected multigraph (edges with own identity)

A multigraph G is an ordered triple G:=(V, E, r) with

• V a set of vertices or nodes,
• E a set of edges or lines,
• r : E{{x,y} : x, yV}, assigning to each edge an unordered pair of endpoint nodes.

Some authors allow multigraphs to have loops, that is, an edge that connects a vertex to itself, [2] while others call these pseudographs, reserving the term multigraph for the case with no loops. [3]

Directed multigraph (edges without own identity)

A multidigraph is a directed graph which is permitted to have multiple arcs, i.e., arcs with the same source and target nodes. A multidigraph G is an ordered pair G:=(V,A) with

• V a set of vertices or nodes,
• A a multiset of ordered pairs of vertices called directed edges, arcs or arrows.

A mixed multigraphG := (V,E,A) may be defined in the same way as a mixed graph.

Directed multigraph (edges with own identity)

A multidigraph or quiver G is an ordered 4-tuple G := (V, A, s, t) with

• V a set of vertices or nodes,
• A a set of edges or lines,
• ${\displaystyle s:A\rightarrow V}$, assigning to each edge its source node,
• ${\displaystyle t:A\rightarrow V}$, assigning to each edge its target node.

This notion might be used to model the possible flight connections offered by an airline. In this case the multigraph would be a directed graph with pairs of directed parallel edges connecting cities to show that it is possible to fly both to and from these locations.

In category theory a small category can be defined as a multidigraph (with edges having their own identity) equipped with an associative composition law and a distinguished self-loop at each vertex serving as the left and right identity for composition. For this reason, in category theory the term graph is standardly taken to mean "multidigraph", and the underlying multidigraph of a category is called its underlying digraph.

Labeling

Multigraphs and multidigraphs also support the notion of graph labeling, in a similar way. However there is no unity in terminology in this case.

The definitions of labeled multigraphs and labeled multidigraphs are similar, and we define only the latter ones here.

Definition 1: A labeled multidigraph is a labeled graph with labeled arcs.

Formally: A labeled multidigraph G is a multigraph with labeled vertices and arcs. Formally it is an 8-tuple ${\displaystyle G=(\Sigma _{V},\Sigma _{A},V,A,s,t,\ell _{V},\ell _{A})}$ where

• V is a set of vertices and A is a set of arcs.
• ${\displaystyle \Sigma _{V}}$ and ${\displaystyle \Sigma _{A}}$ are finite alphabets of the available vertex and arc labels,
• ${\displaystyle s\colon A\rightarrow \ V}$ and ${\displaystyle t\colon A\rightarrow \ V}$ are two maps indicating the source and target vertex of an arc,
• ${\displaystyle \ell _{V}\colon V\rightarrow \Sigma _{V}}$ and ${\displaystyle \ell _{A}\colon A\rightarrow \Sigma _{A}}$ are two maps describing the labeling of the vertices and arcs.

Definition 2: A labeled multidigraph is a labeled graph with multiple labeled arcs, i.e. arcs with the same end vertices and the same arc label (note that this notion of a labeled graph is different from the notion given by the article graph labeling).

Notes

1. For example, see Balakrishnan 1997, p. 1 or Chartrand and Zhang 2012, p. 26.
2. For example, see Bollobás 2002, p. 7 or Diestel 2010, p. 28.
3. For example, see Wilson 2002, p. 6 or Chartrand and Zhang 2012, pp. 26-27.

Related Research Articles

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root, and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.

In graph theory, an isomorphism of graphsG and H is a bijection between the vertex sets of G and H

This is a glossary of graph theory terms. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by edges.

In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct from one another. In a directed graph, a directed path is again a sequence of edges which joins a sequence of vertices, but with the added restriction that the edges all be directed in the same direction.

In mathematics, and more specifically in graph theory, a vertex or node is the fundamental unit 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. In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another.

In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name line graph comes from a paper by Harary & Norman (1960) although both Whitney (1932) and Krausz (1943) used the construction before this. Other terms used for the line graph include the covering graph, the derivative, the edge-to-vertex dual, the conjugate, the representative graph, and the ϑ-obrazom, as well as the edge graph, the interchange graph, the adjoint graph, and the derived graph.

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, and in a multigraph, loops are counted twice. The degree of a vertex is denoted or . The maximum degree of a graph G, denoted by Δ(G), and the minimum degree of a graph, denoted by δ(G), are the maximum and minimum degree of its vertices. In the multigraph on the right, the maximum degree is 5 and the minimum degree is 0. In a regular graph, all degrees are the same, and so we can speak of the degree of the graph. A complete graph is a special kind of regular graph where all vertices,p ,have the maximum degree, p-1. A complete graph is denoted with the form Kp where p is the number of vertices in the graph.

In graph theory, an edge-graceful graph labeling is a type of graph labeling. This is a labeling for simple graphs in which no two distinct edges connect the same two distinct vertices, no edge connects a vertex to itself, and the graph is connected. Edge-graceful labelings were first introduced by S. Lo in his seminal paper.

In combinatorial mathematics, rotation systems encode embeddings of graphs onto orientable surfaces, by describing the circular ordering of a graph's edges around each vertex. A more formal definition of a rotation system involves pairs of permutations; such a pair is sufficient to determine a multigraph, a surface, and a 2-cell embedding of the multigraph onto the surface.

In graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges, under an isomorphism that is an involution without any fixed points. Skew-symmetric graphs are identical to the double covering graphs of bidirected graphs.

In mathematics, and more specifically in graph theory, a directed graph is a graph that is made up of a set of vertices connected by edges, where the edges have a direction associated with them.

In graph theory, betweenness centrality is a measure of centrality in a graph based on shortest paths. For every pair of vertices in a connected graph, there exists at least one shortest path between the vertices such that either the number of edges that the path passes through or the sum of the weights of the edges is minimized. The betweenness centrality for each vertex is the number of these shortest paths that pass through the vertex.

In mathematics, for example in the study of statistical properties of graphs, a null model is type of random object that matches one specific object in some of its features, or more generally satisfies a collection of constraints, but which is otherwise taken to be an unbiasedly random structure. The null model is used as a term of comparison, to verify whether the object in question displays some non-trivial features, such as community structure in graphs. An appropriate null model behaves in accordance with a reasonable null hypothesis for the behavior of the system under investigation.

A mixed graphG = is a mathematical object consisting of a set of vertices V, a set of (undirected) edges E, and a set of directed edges A.

References

• Balakrishnan, V. K. (1997). Graph Theory. McGraw-Hill. ISBN   0-07-005489-4.
• Bollobás, Béla (2002). Modern Graph Theory. Graduate Texts in Mathematics. 184. Springer. ISBN   0-387-98488-7.
• Chartrand, Gary; Zhang, Ping (2012). A First Course in Graph Theory. Dover. ISBN   978-0-486-48368-9.
• Diestel, Reinhard (2010). Graph Theory. Graduate Texts in Mathematics. 173 (4th ed.). Springer. ISBN   978-3-642-14278-9.
• Gross, Jonathan L.; Yellen, Jay (1998). Graph Theory and Its Applications. CRC Press. ISBN   0-8493-3982-0.
• Gross, Jonathan L.; Yellen, Jay, eds. (2003). Handbook of Graph Theory. CRC. ISBN   1-58488-090-2.
• Harary, Frank (1995). Graph Theory. Addison Wesley. ISBN   0-201-41033-8.
• Janson, Svante; Knuth, Donald E.; Luczak, Tomasz; Pittel, Boris (1993). "The birth of the giant component". Random Structures and Algorithms. 4 (3): 231–358. doi:10.1002/rsa.3240040303. ISSN   1042-9832. MR   1220220.
• Wilson, Robert A. (2002). Graphs, Colourings and the Four-Colour Theorem. Oxford Science Publ. ISBN   0-19-851062-4.
• Zwillinger, Daniel (2002). CRC Standard Mathematical Tables and Formulae (31st ed.). Chapman & Hall/CRC. ISBN   1-58488-291-3.