## 5.109. dag

Origin
Constraint

$\mathrm{\pi \pi \pi }\left(\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\right)$

Argument
 $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi ‘}-\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$
Restrictions
 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi },\left[\mathrm{\pi \pi \pi \pi \pi ‘},\mathrm{\pi \pi \pi \pi }\right]\right)$ $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }.\mathrm{\pi \pi \pi \pi \pi ‘}\beta ₯1$ $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }.\mathrm{\pi \pi \pi \pi \pi ‘}\beta €|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi },\mathrm{\pi \pi \pi \pi \pi ‘}\right)$ $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }.\mathrm{\pi \pi \pi \pi }\beta ₯1$ $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }.\mathrm{\pi \pi \pi \pi }\beta €|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|$
Purpose

Consider a digraph $G$ described by the $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ collection. Select a subset of arcs of $G$ so that the corresponding graph does not contain any circuit.

Example
$\left(\begin{array}{c}β©\begin{array}{cc}\mathrm{\pi \pi \pi \pi \pi ‘}-1\hfill & \mathrm{\pi \pi \pi \pi }-\left\{2,4\right\},\hfill \\ \mathrm{\pi \pi \pi \pi \pi ‘}-2\hfill & \mathrm{\pi \pi \pi \pi }-\left\{3,4\right\},\hfill \\ \mathrm{\pi \pi \pi \pi \pi ‘}-3\hfill & \mathrm{\pi \pi \pi \pi }-\mathrm{\beta  },\hfill \\ \mathrm{\pi \pi \pi \pi \pi ‘}-4\hfill & \mathrm{\pi \pi \pi \pi }-\mathrm{\beta  },\hfill \\ \mathrm{\pi \pi \pi \pi \pi ‘}-5\hfill & \mathrm{\pi \pi \pi \pi }-\left\{6\right\},\hfill \\ \mathrm{\pi \pi \pi \pi \pi ‘}-6\hfill & \mathrm{\pi \pi \pi \pi }-\mathrm{\beta  }\hfill \end{array}βͺ\hfill \end{array}\right)$

The $\mathrm{\pi \pi \pi }$ constraint holds since the $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ collection depicts a graph without circuit.

Typical
$|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|>2$
Symmetry

Items of $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ are permutable.

Algorithm

A filtering algorithm for the $\mathrm{\pi \pi \pi }$ constraint is given inΒ [Dooms06]. It removes potential arcs that would create a circuit of mandatory arcs.

Keywords
Arc input(s)

$\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$

Arc generator
$\mathrm{\pi \pi Έ\pi Ώ\pi Ή}$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi }\right)$

Arc arity
Arc constraint(s)
$\mathrm{\pi \pi }_\mathrm{\pi \pi \pi }$$\left(\mathrm{\pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi ’},\mathrm{\pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi \pi }\right)$
Graph property(ies)
$\mathrm{\pi \pi \pi \pi }$$=0$

Arc input(s)

$\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$

Arc generator
$\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{\pi \pi }_\mathrm{\pi \pi \pi }$$\left(\mathrm{\pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi \pi \pi ‘},\mathrm{\pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi \pi }\right)$
Graph property(ies)
$\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$$\beta €1$

Graph model

The first graph constraint removes the loop of each vertex. The second graph constraint forbids the creation of circuits involving more than one vertex.

PartΒ (A) of FigureΒ 5.109.1 shows the initial graph associated with the second graph constraint of the Example slot. This initial graph from which we start is derived from the set associated with each vertex. Each set describes the potential values of the $\mathrm{\pi \pi \pi \pi }$ attribute of a given vertex. PartΒ (B) of FigureΒ 5.109.1 gives the final graph associated with the Example slot.