Let \(D(V,E,\alpha,\beta)\) be a digraph. A digraph \(S(V',E',\alpha',\beta')\) is called a subdigraph of \(D\), written as \(S\subseteq D\), if it fulfills the following properties:
If \(S\) is a subdigraph of \(D\), then \(D\) is called the superdigraph of \(S\).
If \(S\) contains all the edges \(e\) with \(\alpha(e),\omega(e)\in V'\), then \(S\) is an induced subdigraph of \(D\); we say that the vertices \(V'\) induce or span \(S\) in \(D\) and write \(S:=D[V']\). Thus, if \(V'\subseteq V\) is any set of vertices, \(V'=\{v_1,v_2,\ldots,v_n\}\), then the induced subdigraph \(D[V']=D[v_1,v_2,\ldots,v_n]\) denotes the digraph whose edges are precisely the edges of \(D\) with initial and terminal vertices in \(V'\).
In the above figure, the digraphs \(D_2, D_3\) and \(D_4\) are all subdigraphs of the digraph \(D_1\). However, only \(D_2\) and and \(D_4\) are induced subdigraphs of \(D_1\), since
\[D_2=D_1[a,b,c],\quad D_4=D_1[a,c,d],\]
but
\[D_3\neq D_1[c,d].\]
Algorithms: 1
Proofs: 2
Propositions: 3