Mixed Graphs

A graph is a mathematical representation of a network of nodes and edges. The graph’s edges connect any two nodes, also known as vertices.

A mixed graph G=(V.E) is a graph with the vertex set v={V1, V2, V3,…, Vn } and the edges set E={e1,e2,e3,….en}, in which some are undirected edges, and some are directed edges. The concept of any mixed graph is based on the traditional approach of orienting either all edges or none. 

An undirected edge between two vertices is a Vi and Vj in G by ViVj or VjVi and a directed edge from Vi to Vj by (Vi, Vj). 

For example,

Below examples have a graph G1, with three vertices V1, V2 and V3 and three edges are e1, e2 and e3 then G1= ((V1,V2,V3), (e1,e2,e3))

Let us see this example in which we have a graph with four vertices and four edges  G=((V1,V2,V3,V4),(e1,e2,e3,e4)).

Degree of vertex and number of edges in a mixed graph

The vertex v degree in the undirected graph G (V, E) u = , represented by deg (v), is the total number of edges incident along with vertex v. However, the loop at the vertex contributes twice the number to that vertex degree.

In the directed graph:

( , ) → Gd = V E with directed edges → E 

Here, the in-degree of a vertex v is denoted by deg (v) −. It is the total number of edges with v as the terminal vertex. The out degree of v is represented by deg (v) +. It is known as the number of edges with v as the initial vertex [2]. 

Example:

 Use the augmented adjacency matrix to represent the mixed graph below.

Solution. Let a, b, c, d be an arbitrary ordering of the vertices. Again let = (AGu / AGd) AGm be the augmented adjacency matrix, where AGu and AGd respectively are 4 by 4 adjacency matrices of G (V, E) u = and (, ) → Gd = V E. Then, the 4 by 8 augmented adjacency matrix AGm is given by

Example: Draw a graph represented by the below-mentioned augmented adjacency matrix.

Solution. Let a, b, c, d be the ordering of the vertices with the given adjacency matrix. Then the graph is given by

The vertices’ ordering determines the graph’s adjacency matrix. Because there are n different adjacency matrices for the given graph, we have ordered the n vertices differently. As a result, there are n vertices in a graph with n vertices.

Mixed graph isomorphism 

We have to determine whether the structure of two or more graph models is the same. Isomorphic graphs have the same structure. For example, two cities may have the same road network but distinct buildings or the same road network because their squares/intersections correspond one to one, preserving roads.

Theory: Isomorphism of mixed graphs is an equivalence relation. To show isomorphism of mixed graphs is an equivalence relation, we need to show that mixed graph isomorphism is reflexive, symmetric and transitive. 

Let f: Gm→ Gm be a mapping; clearly, f is an identity function, so isomorphism is reflexive. 

For isomorphic mixed graphs Gm and Hm, there exists a one to one correspondence f: Gm→ Hm that preserves adjacency. Since f is one to one correspondence from Gm to Hm, there is one to one correspondence f -1 from Hm to Gm that preserves adjacency. 

Thus, the isomorphism of mixed graphs is symmetric. Suppose Gm is isomorphic to Hm and Hm is isomorphic to Km. Then there are one to one correspondences f and h from Gm to Hm, and from Hm to Km, respectively, that preserve adjacency. 

Hence, a one-to-one correspondence from Gm to Km preserves adjacency. Therefore, isomorphism is transitive. Thus, the isomorphism of mixed graphs is an equivalence relation.

Example: Determine whether the graphs in the below figures are isomorphic or not?

Solution: The invariants of the graphs Gm and Hm are the number of edges, the degree of vertices provided by directed edges (in and out-degree), and undirected edges (degree). The two mixed graphs, Gm and Hm, agree on the invariants, as shown in the table below. The isomorphism between them must be found by us.

Let f: V1 →V2 be a function that determines whether or not it is an isomorphism, with V1 and V2 being the vertices sets of the mixed graphs Gm and Hm.

We have f (a) = v1, f (b) = v5, f(c) = v4, f(d) = v2, f(e) = v6, and f(f) = v3 using the above table as a reference and the adjacency of the vertices of graph Gm and the degree, in-degree, and out degrees. We again examine Gm’s augmented adjacency matrix in the ordering a, b, c, d, e, and f to determine whether f preserves edges.

The augmented adjacency matrix of Hm, labelled by the images of the corresponding vertices in Gm, we can give in the order: v1, v5, v4, v2, v6, v3.

AGm= AHm: it follows that f preserves edges. Thus, f is an isomorphism, and the mixed graphs Gm and Hm are isomorphic.

Conclusion 

We sometimes need to employ mixed graphs to tackle physical problems with various origins. On the other hand, prior graph studies have paid greater attention to directed and undirected graphs. As a result, this post aims to explain the relationship between the degree of vertices and the number of edges in mixed graphs. It also shows the adjacency matrix form of mixed graphs using an augmented matrix and mixed graph isomorphism.

Finally, this post suggests that we should concentrate on learning the ideas and properties of mixed graphs because studying the attributes of a mixed graph from its underlying completely oriented or completely un-oriented graph may result in the removal of many crucial aspects in the physical interpretation of the mixed graph.