SKEDSOFT

TYPES OF DIGRAPHS

Simple Digraphs: A digraphs that has no self-loop or parallel edges is called a simple digraph. The digraph shown in Fig. 8.3(a) is simple, but its underlying graph shown in Fig. 8.3(b) is not simple.

A Symmetric Digraphs: Digraphs that have atmost one directed edge between a pair of vertices, but are allowed to have self-loops, are called asymmetric or antisymmetric digraph.
For example, the digraph in Fig. 8.4(a), is asymmetric.
The digraph in Fig. 8.4(b) is neither symmetric nor asymmetric.
The digraph in Fig. 8.4(b) is simple and asymmetric.
The digraph in Fig. 8.4(b) is simple but not asymmetric.

Symmetric Digraph: Digraphs in which for every edge (a, b) (i.e., from vertex a to b) there is also an edge (b, a). For example, the digraph in Fig. 8.5 is a symmetric digraph. The digraph in Fig. 8.4(b) is not symmetric.
This digraph has (v4, v3) as an edge but does not have (v3, v4) as an edge.
The digraph in Fig. 8.5 is simple also. Such a digraph is called a symmetric simple digraph. The digraph in Fig. 8.4(b) is simple and non-symmetric.

Isomorphic Digraphs: Isomorphic graphs were defined such that they have identical behaviour in terms of graph properties. In otherwords, if their labels are removed, two isomorphic graphs are indistinguishable. For two digraphs to be isomorphic not only must their corresponding undirected graphs be isomorphic, but the directions of the corresponding edges must also agree.

For example, Fig. 8.6, shows two digraphs that are not isomorphic, although they are orientations of the same undirected graph.

In otherwords, two digraphs D1 and D2 are said to be isomorphic if both of the following conditions hold :
(i) The underlying graphs of D1 and D2 are either identical or isomorphic.
(ii) Under the one-to-one correspondence between the edges of D1 and D2 the directions of the corresponding edges are preserved.
The two digraphs in Fig. 8.7(a) and 8.7(b) are isomorphic, whereas the two digraphs in Fig.8.8(a) and 8.8(b) are not isomorphic.