# Definition: Isomorphic Digraphs

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

#### Example: 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$$

Github: ### References

#### Bibliography

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