## 5.86. connected

Origin
Constraint

$\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍}\left(\mathrm{𝙽𝙾𝙳𝙴𝚂}\right)$

Argument
 $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚒𝚗𝚍𝚎𝚡}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚜𝚞𝚌𝚌}-\mathrm{𝚜𝚟𝚊𝚛}\right)$
Restrictions
 $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙽𝙾𝙳𝙴𝚂},\left[\mathrm{𝚒𝚗𝚍𝚎𝚡},\mathrm{𝚜𝚞𝚌𝚌}\right]\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}.\mathrm{𝚒𝚗𝚍𝚎𝚡}\ge 1$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}.\mathrm{𝚒𝚗𝚍𝚎𝚡}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}|$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝙽𝙾𝙳𝙴𝚂},\mathrm{𝚒𝚗𝚍𝚎𝚡}\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}.\mathrm{𝚜𝚞𝚌𝚌}\ge 1$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}.\mathrm{𝚜𝚞𝚌𝚌}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}|$
Purpose

Consider a digraph $G$ described by the $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ collection. Select a subset of arcs of $G$ so that the corresponding graph is symmetric (i.e., if there is an arc from $i$ to $j$, there is also an arc from $j$ to $i$) and connected (i.e., there is a path between any pair of vertices of $G$).

Example
$\left(\begin{array}{c}〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍𝚎𝚡}-1\hfill & \mathrm{𝚜𝚞𝚌𝚌}-\left\{1,2,3\right\},\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-2\hfill & \mathrm{𝚜𝚞𝚌𝚌}-\left\{1,3\right\},\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-3\hfill & \mathrm{𝚜𝚞𝚌𝚌}-\left\{1,2,4\right\},\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-4\hfill & \mathrm{𝚜𝚞𝚌𝚌}-\left\{3,5,6\right\},\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-5\hfill & \mathrm{𝚜𝚞𝚌𝚌}-\left\{4\right\},\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-6\hfill & \mathrm{𝚜𝚞𝚌𝚌}-\left\{4\right\}\hfill \end{array}〉\hfill \end{array}\right)$

The $\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍}$ constraint holds since the $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ collection depicts a symmetric graph involving a single connected component.

Typical
$|\mathrm{𝙽𝙾𝙳𝙴𝚂}|>1$
Symmetry

Items of $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ are permutable.

Algorithm

A filtering algorithm for the $\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍}$ constraint is sketched in [Dooms06]. Beside the pruning associated with the fact that the final graph is symmetric, it is based on the fact that all bridges and cut vertices on a path between two vertices that should for sure belong to the final graph should also belong to the final graph.

Keywords
Arc input(s)

$\mathrm{𝙽𝙾𝙳𝙴𝚂}$

Arc generator
$\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚗𝚘𝚍𝚎𝚜}\mathtt{1},\mathrm{𝚗𝚘𝚍𝚎𝚜}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{𝚒𝚗}_\mathrm{𝚜𝚎𝚝}$$\left(\mathrm{𝚗𝚘𝚍𝚎𝚜}\mathtt{2}.\mathrm{𝚒𝚗𝚍𝚎𝚡},\mathrm{𝚗𝚘𝚍𝚎𝚜}\mathtt{1}.\mathrm{𝚜𝚞𝚌𝚌}\right)$
Graph property(ies)
$\mathrm{𝐍𝐂𝐂}$$=1$

Graph class
$\mathrm{𝚂𝚈𝙼𝙼𝙴𝚃𝚁𝙸𝙲}$

Graph model

Part (A) of Figure 5.86.1 shows the initial graph from which we start. It is derived from the set associated with each vertex. Each set describes the potential values of the $\mathrm{𝚜𝚞𝚌𝚌}$ attribute of a given vertex. Part (B) of Figure 5.86.1 gives the final graph associated with the Example slot.