Multi Graphs

Multi Graphs


A multigraph (in contrast to a simple graph) is a graph which is permitted to have multiple edges (also called parallel edges), that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge. The term multigraph refers to a graph in which multiple edges between nodes are either permitted or required.

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

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.

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 , 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, while others call these pseudo graphs, reserving the term multigraph for the case with no loops.

Directed multigraph (edges without own identity)

A multidigraph is a directed graph which is permitted to have multiple arcs, i.e., arcswith 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.

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,

Assigning to each edge its source node,

Assigning to each edge its target node.

Multigraph u0026amp; underlying digraph

In category theory a small category can be defined as a multigraph (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 graphs standardly taken to mean “multigraph”, and the underlying multigraph of a category is called its underlying digraph.

Graph Labeling

Multigraphs and multidigraphs also support the notion of graph labeling, in a similar way. 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.

Determine whether the graph shown has directed or undirected edges, whether it has multiple edges, and whether it has one or more loops.

Graph (7) has multiple edges (“A Directed graph may have multiple directed edges from a vertex to a second (possibly the same) vertex, are called as directed multigraphs”) and it also has loops at vertex c and e.Similar is the case with Graph (9).

One thing to notice here is that the multiple directed edges have the same origin and destination. Thus, in first graph there is only one directed edge from vertex c to vertex d (and also only one directed edge from d to c). So, this graph is just a directed graph. On the other hand in the second graph , there are two edges from e to d and two edges from b to c , So this graph is a directed multigraph.