Two digraphs \(D_1(V_1,E_1,\alpha_1,\omega_1)\) and \(D_2(V_2,E_2,\alpha_2,\omega_2)\) are **isomorphic**, written as \(D_1\equiv D_2\), if \(D_2\) can be transformed to \(G_1\) (and vice versa) by relabelling the vertices, without changing adjacent vertices and edges. This is equivalent to a transformation, in which the number of vertices outgoing from or incoming to each vertex in \(D_1\) is equal to the number of edges outgoing from or incoming to the corresponding vertex in \(G_2\).

Formally, \(D_1\equiv D_2\) if and only if there exist two bijective functions, a relabelling function \(\rho : V_1 \to V_2\) and an edge transformation function \(\epsilon : E_1 \to E_2\) and such that

\((i)\) \(\rho(\alpha_1(e))=\alpha_2(\epsilon(e))\) for all \(e\in E_1.\)

\((ii)\) \(\rho(\omega_1(e))=\omega_2(\epsilon(e))\) for all \(e\in E_1.\)

Note: In the left side of the two equations \((i)\) and \((ii)\), \(\rho(\alpha_1(e))\) and \(\rho(\omega_1(e))\) mean that we relabel the initial and terminal vertices \(\alpha_1(e)\) and \(\omega_1(e)\) of given edge \(e\) in the first digraph \(D_1\), obtaining (in the right side of the two equations) the corresponding initial and terminal vertices \(\alpha_2(\epsilon(e))\) and \(\omega_2(\epsilon(e))\) of an edge \(\epsilon(e)\) in the second digraph \(D_2\).

In the above figure, the digraphs \(D_1\) and \(D_2\) are not the same, but they are isomorphic, since we can find two bijective functions \(\rho : V_1 \to V_2\) and \(\epsilon : E_1 \to E_2\) defined by

Definition of \(\rho\):

\(v\in V_1\) | \(\rho(v)\in V_2\) |
---|---|

\(a\) | \(u\) |

\(b\) | \(x\) |

\(c\) | \(v\) |

\(d\) | \(w\) |

Definition of \(\epsilon\): \(e\in E_1\)|\(\epsilon(e)\in E_2\) \(e_1\)| \(f_1\) \(e_2\)| \(f_2\) \(e_3\)| \(f_3\) \(e_4\)| \(f_4\) \(e_5\)| \(f_5\) \(e_6\)| \(f_6\) \(e_7\)| \(f_7\)

such that all adjacencies in the digraphs are preserved, like demonstrated in the following table:

|\(e\)|\(\alpha_1(e)\)|\(\omega_1(e)\)|\(\rho(\alpha_1(e))\)|\(\rho(\omega_1(e))\)|\(\alpha_2(\epsilon(e))\)|\(\omega_2(\epsilon(e))\)|\(\epsilon(e)\)| \(e_1\)| \(a\)| \(b\)| \(u\)| \(x\)| \(u\)| \(x\)| \(f_1\) \(e_2\)| \(b\)| \(a\)| \(x\)| \(u\)| \(x\)| \(u\)| \(f_2\) \(e_3\)| \(a\)| \(b\)| \(u\)| \(x\)| \(u\)| \(x\)| \(f_3\) \(e_4\)| \(a\)| \(c\)| \(u\)| \(v\)| \(u\)| \(v\)| \(f_4\) \(e_5\)| \(b\)| \(d\)| \(x\)| \(w\)| \(x\)| \(w\)| \(f_5\) \(e_6\)| \(c\)| \(d\)| \(v\)| \(w\)| \(v\)| \(w\)| \(f_6\) \(e_7\)| \(d\)| \(d\)| \(w\)| \(w\)| \(w\)| \(w\)| \(f_7\)

**Aldous Joan M., Wilson Robin J.**: "Graphs and Applications - An Introductory Approach", Springer, 2000**Krumke S. O., Noltemeier H.**: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition