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\)
