WikiMili The Free Encyclopedia

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.

- Undirected multigraph (edges without own identity)
- Undirected multigraph (edges with own identity)
- Directed multigraph (edges without own identity)
- Directed multigraph (edges with own identity)
- Labeling
- See also
- Notes
- References
- External links

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.

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

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:

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*,*y*∈*V*}, 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] }

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 multigraph***G* := (*V*,*E*,*A*) may be defined in the same way as a mixed graph.

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*,- , assigning to each edge its source node,
- , 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**.

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 where

- V is a set of vertices and A is a set of arcs.
- and are finite alphabets of the available vertex and arc labels,
- and are two maps indicating the
*source*and*target*vertex of an arc, - and 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).

**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 graphs***G* 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 graph***G* = is a mathematical object consisting of a set of vertices *V*, a set of (undirected) edges *E*, and a set of directed edges *A*.

- 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.

This article incorporates public domain material from the NIST document: Black, Paul E. "Multigraph". *Dictionary of Algorithms and Data Structures*.

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.