## 5.76. correspondence

 DESCRIPTION LINKS GRAPH
Origin

Derived from $\mathrm{𝚜𝚘𝚛𝚝}_\mathrm{𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗}$ by removing the sorting condition.

Constraint

$\mathrm{𝚌𝚘𝚛𝚛𝚎𝚜𝚙𝚘𝚗𝚍𝚎𝚗𝚌𝚎}\left(\mathrm{𝙵𝚁𝙾𝙼},\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽},\mathrm{𝚃𝙾}\right)$

Arguments
 $\mathrm{𝙵𝚁𝙾𝙼}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚏𝚛𝚘𝚖}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝚃𝙾}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚝𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $|\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|=|\mathrm{𝙵𝚁𝙾𝙼}|$ $|\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|=|\mathrm{𝚃𝙾}|$ $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}.\mathrm{𝚟𝚊𝚛}\ge 1$ $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}.\mathrm{𝚟𝚊𝚛}\le |\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|$ $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left(\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙵𝚁𝙾𝙼},\mathrm{𝚏𝚛𝚘𝚖}\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽},\mathrm{𝚟𝚊𝚛}\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚃𝙾},\mathrm{𝚝𝚟𝚊𝚛}\right)$
Purpose

The variables of collection $\mathrm{𝙵𝚁𝙾𝙼}$ correspond to the variables of collection $\mathrm{𝚃𝙾}$ according to the permutation $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}$ (i.e., $\mathrm{𝙵𝚁𝙾𝙼}\left[i\right].\mathrm{𝚏𝚛𝚘𝚖}=\mathrm{𝚃𝙾}\left[\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\left[i\right].\mathrm{𝚟𝚊𝚛}\right].\mathrm{𝚝𝚟𝚊𝚛}$).

Example
$\left(\begin{array}{c}〈\begin{array}{c}\mathrm{𝚏𝚛𝚘𝚖}-1,\hfill \\ \mathrm{𝚏𝚛𝚘𝚖}-9,\hfill \\ \mathrm{𝚏𝚛𝚘𝚖}-1,\hfill \\ \mathrm{𝚏𝚛𝚘𝚖}-5,\hfill \\ \mathrm{𝚏𝚛𝚘𝚖}-2,\hfill \\ \mathrm{𝚏𝚛𝚘𝚖}-1\hfill \end{array}〉,\hfill \\ 〈\begin{array}{c}\mathrm{𝚟𝚊𝚛}-6,\hfill \\ \mathrm{𝚟𝚊𝚛}-1,\hfill \\ \mathrm{𝚟𝚊𝚛}-3,\hfill \\ \mathrm{𝚟𝚊𝚛}-5,\hfill \\ \mathrm{𝚟𝚊𝚛}-4,\hfill \\ \mathrm{𝚟𝚊𝚛}-2\hfill \end{array}〉,\hfill \\ 〈\begin{array}{c}\mathrm{𝚝𝚟𝚊𝚛}-9,\hfill \\ \mathrm{𝚝𝚟𝚊𝚛}-1,\hfill \\ \mathrm{𝚝𝚟𝚊𝚛}-1,\hfill \\ \mathrm{𝚝𝚟𝚊𝚛}-2,\hfill \\ \mathrm{𝚝𝚟𝚊𝚛}-5,\hfill \\ \mathrm{𝚝𝚟𝚊𝚛}-1\hfill \end{array}〉\hfill \end{array}\right)$

As illustrated by Figure 5.76.1, the $\mathrm{𝚌𝚘𝚛𝚛𝚎𝚜𝚙𝚘𝚗𝚍𝚎𝚗𝚌𝚎}$ constraint holds since:

• The first item $\mathrm{𝙵𝚁𝙾𝙼}\left[1\right].\mathrm{𝚏𝚛𝚘𝚖}=1$ of collection $\mathrm{𝙵𝚁𝙾𝙼}$ corresponds to the $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\left[1\right].\mathrm{𝚟𝚊𝚛}={6}^{th}$ item of collection $\mathrm{𝚃𝙾}$.

• The second item $\mathrm{𝙵𝚁𝙾𝙼}\left[2\right].\mathrm{𝚏𝚛𝚘𝚖}=9$ of collection $\mathrm{𝙵𝚁𝙾𝙼}$ corresponds to the $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\left[2\right].\mathrm{𝚟𝚊𝚛}={1}^{th}$ item of collection $\mathrm{𝚃𝙾}$.

• The third item $\mathrm{𝙵𝚁𝙾𝙼}\left[3\right].\mathrm{𝚏𝚛𝚘𝚖}=1$ of collection $\mathrm{𝙵𝚁𝙾𝙼}$ corresponds to the $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\left[3\right].\mathrm{𝚟𝚊𝚛}={3}^{th}$ item of collection $\mathrm{𝚃𝙾}$.

• The fourth item $\mathrm{𝙵𝚁𝙾𝙼}\left[4\right].\mathrm{𝚏𝚛𝚘𝚖}=5$ of collection $\mathrm{𝙵𝚁𝙾𝙼}$ corresponds to the $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\left[4\right].\mathrm{𝚟𝚊𝚛}={5}^{th}$ item of collection $\mathrm{𝚃𝙾}$.

• The fifth item $\mathrm{𝙵𝚁𝙾𝙼}\left[5\right].\mathrm{𝚏𝚛𝚘𝚖}=2$ of collection $\mathrm{𝙵𝚁𝙾𝙼}$ corresponds to the $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\left[5\right].\mathrm{𝚟𝚊𝚛}={4}^{th}$ item of collection $\mathrm{𝚃𝙾}$.

• The sixth item $\mathrm{𝙵𝚁𝙾𝙼}\left[6\right].\mathrm{𝚏𝚛𝚘𝚖}=1$ of collection $\mathrm{𝙵𝚁𝙾𝙼}$ corresponds to the $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\left[6\right].\mathrm{𝚟𝚊𝚛}={2}^{th}$ item of collection $\mathrm{𝚃𝙾}$.

##### Figure 5.76.1. Illustration of the correspondence between the items of the $\mathrm{𝙵𝚁𝙾𝙼}$ and the $\mathrm{𝚃𝙾}$ collections according to the permutation defined by the items of the $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}$ collection Typical
 $|\mathrm{𝙵𝚁𝙾𝙼}|>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝙵𝚁𝙾𝙼}.\mathrm{𝚏𝚛𝚘𝚖}\right)>1$
Symmetry

All occurrences of two distinct values in $\mathrm{𝙵𝚁𝙾𝙼}.\mathrm{𝚏𝚛𝚘𝚖}$ or $\mathrm{𝚃𝙾}.\mathrm{𝚝𝚟𝚊𝚛}$ can be swapped; all occurrences of a value in $\mathrm{𝙵𝚁𝙾𝙼}.\mathrm{𝚏𝚛𝚘𝚖}$ or $\mathrm{𝚃𝙾}.\mathrm{𝚝𝚟𝚊𝚛}$ can be renamed to any unused value.

Remark

Similar to the $\mathrm{𝚜𝚊𝚖𝚎}$ constraint except that we also provide the permutation that allows to go from the items of collection $\mathrm{𝙵𝚁𝙾𝙼}$ to the items of collection $\mathrm{𝚃𝙾}$.

See also

specialisation: $\mathrm{𝚜𝚊𝚖𝚎}$ ($\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}$ parameter removed).

Keywords
Derived Collection
$\mathrm{𝚌𝚘𝚕}\left(\begin{array}{c}\mathrm{𝙵𝚁𝙾𝙼}_\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}-\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚏𝚛𝚘𝚖}-\mathrm{𝚍𝚟𝚊𝚛},\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right),\hfill \\ \mathrm{𝚒𝚝𝚎𝚖}\left(\mathrm{𝚏𝚛𝚘𝚖}-\mathrm{𝙵𝚁𝙾𝙼}.\mathrm{𝚏𝚛𝚘𝚖},\mathrm{𝚟𝚊𝚛}-\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}.\mathrm{𝚟𝚊𝚛}\right)\right]\hfill \end{array}\right)$
Arc input(s)

$\mathrm{𝙵𝚁𝙾𝙼}_\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}$ $\mathrm{𝚃𝙾}$

Arc generator
$\mathrm{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚏𝚛𝚘𝚖}_\mathrm{𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗},\mathrm{𝚝𝚘}\right)$

Arc arity
Arc constraint(s)
 $•\mathrm{𝚏𝚛𝚘𝚖}_\mathrm{𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗}.\mathrm{𝚏𝚛𝚘𝚖}=\mathrm{𝚝𝚘}.\mathrm{𝚝𝚟𝚊𝚛}$ $•\mathrm{𝚏𝚛𝚘𝚖}_\mathrm{𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗}.\mathrm{𝚟𝚊𝚛}=\mathrm{𝚝𝚘}.\mathrm{𝚔𝚎𝚢}$
Graph property(ies)
$\mathrm{𝐍𝐀𝐑𝐂}$$=|\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|$

Graph class
 $•$$\mathrm{𝙰𝙲𝚈𝙲𝙻𝙸𝙲}$ $•$$\mathrm{𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴}$ $•$$\mathrm{𝙽𝙾}_\mathrm{𝙻𝙾𝙾𝙿}$

Graph model

Parts (A) and (B) of Figure 5.76.2 respectively show the initial and final graph associated with the Example slot. In both graphs the source vertices correspond to the derived collection $\mathrm{𝙵𝚁𝙾𝙼}_\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}$, while the sink vertices correspond to the collection $\mathrm{𝚃𝙾}$. Since the final graph contains exactly $|\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|$ arcs the $\mathrm{𝚌𝚘𝚛𝚛𝚎𝚜𝚙𝚘𝚗𝚍𝚎𝚗𝚌𝚎}$ constraint holds. As we use the $\mathrm{𝐍𝐀𝐑𝐂}$ graph property, the arcs of the final graph are stressed in bold.

##### Figure 5.76.2. Initial and final graph of the $\mathrm{𝚌𝚘𝚛𝚛𝚎𝚜𝚙𝚘𝚗𝚍𝚎𝚗𝚌𝚎}$ constraint (a) (b)
Signature

Because of the second condition $\mathrm{𝚏𝚛𝚘𝚖}_\mathrm{𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗}.\mathrm{𝚟𝚊𝚛}=\mathrm{𝚝𝚘}.\mathrm{𝚔𝚎𝚢}$ of the arc constraint and since both, the $\mathrm{𝚟𝚊𝚛}$ attributes of the collection $\mathrm{𝙵𝚁𝙾𝙼}_\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}$ and the $\mathrm{𝚔𝚎𝚢}$ attributes of the collection $\mathrm{𝚃𝙾}$ are all -distinct, the final graph contains at most $|\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|$ arcs. Therefore we can rewrite the graph property $\mathrm{𝐍𝐀𝐑𝐂}$ $=$ $|\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|$ to $\mathrm{𝐍𝐀𝐑𝐂}$ $\ge$ $|\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|$. This leads to simplify $\underline{\overline{\mathrm{𝐍𝐀𝐑𝐂}}}$ to $\overline{\mathrm{𝐍𝐀𝐑𝐂}}$.