The other basic operator, the removal of an edge (either link or arc) is much simpler than the addition of an edge, since only one neighboring configuration is obtained when we delete an edge. Moreover, it is not necessary to perform any test for detecting directed or undirected cycles. However, in this case we need to preserve condition 4 in the definition of RPDAG (if
exists in
or
), that could be violated after an arc is deleted. This situation may appear only when we are going to remove an arc
and either
or
: in the first case, all the children of
that do not have other parents than
must be converted into neighbors of
, and this process is repeated starting from each of these children; in the second case, if
then in addition to the previous process, the arc
must be converted into the link
. Figure 13 illustrates these situations. This procedure of transforming arcs into links is exactly the same as the one described in the proof of Proposition 2.
![]() |