5.76. correspondence

DESCRIPTIONLINKSGRAPH
Origin

Derived from πšœπš˜πš›πš_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš— by removing the sorting condition.

Constraint

πšŒπš˜πš›πš›πšŽπšœπš™πš˜πš—πšπšŽπš—πšŒπšŽ(π™΅πšπ™Ύπ™Ό,π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½,πšƒπ™Ύ)

Arguments
π™΅πšπ™Ύπ™ΌπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπš›πš˜πš–-πšπšŸπšŠπš›)
π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πšƒπ™ΎπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
|π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½|=|π™΅πšπ™Ύπ™Ό|
|π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½|=|πšƒπ™Ύ|
π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½.πšŸπšŠπš›β‰₯1
π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½.πšŸπšŠπš›β‰€|π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½|
πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½)
πš›πšŽπššπšžπš’πš›πšŽπš(π™΅πšπ™Ύπ™Ό,πšπš›πš˜πš–)
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπ™Ύ,πšπšŸπšŠπš›)
Purpose

The variables of collection π™΅πšπ™Ύπ™Ό correspond to the variables of collection πšƒπ™Ύ according to the permutation π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½ (i.e.,Β π™΅πšπ™Ύπ™Ό[i].πšπš›πš˜πš–=πšƒπ™Ύ[π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½[i].πšŸπšŠπš›].πšπšŸπšŠπš›).

Example
πšπš›πš˜πš–-1,πšπš›πš˜πš–-9,πšπš›πš˜πš–-1,πšπš›πš˜πš–-5,πšπš›πš˜πš–-2,πšπš›πš˜πš–-1,πšŸπšŠπš›-6,πšŸπšŠπš›-1,πšŸπšŠπš›-3,πšŸπšŠπš›-5,πšŸπšŠπš›-4,πšŸπšŠπš›-2,πšπšŸπšŠπš›-9,πšπšŸπšŠπš›-1,πšπšŸπšŠπš›-1,πšπšŸπšŠπš›-2,πšπšŸπšŠπš›-5,πšπšŸπšŠπš›-1

As illustrated by FigureΒ 5.76.1, the πšŒπš˜πš›πš›πšŽπšœπš™πš˜πš—πšπšŽπš—πšŒπšŽ constraint holds since:

  • The first item π™΅πšπ™Ύπ™Ό[1].πšπš›πš˜πš–=1 of collection π™΅πšπ™Ύπ™Ό corresponds to the π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½[1].πšŸπšŠπš›=6 th item of collection πšƒπ™Ύ.

  • The second item π™΅πšπ™Ύπ™Ό[2].πšπš›πš˜πš–=9 of collection π™΅πšπ™Ύπ™Ό corresponds to the π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½[2].πšŸπšŠπš›=1 th item of collection πšƒπ™Ύ.

  • The third item π™΅πšπ™Ύπ™Ό[3].πšπš›πš˜πš–=1 of collection π™΅πšπ™Ύπ™Ό corresponds to the π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½[3].πšŸπšŠπš›=3 th item of collection πšƒπ™Ύ.

  • The fourth item π™΅πšπ™Ύπ™Ό[4].πšπš›πš˜πš–=5 of collection π™΅πšπ™Ύπ™Ό corresponds to the π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½[4].πšŸπšŠπš›=5 th item of collection πšƒπ™Ύ.

  • The fifth item π™΅πšπ™Ύπ™Ό[5].πšπš›πš˜πš–=2 of collection π™΅πšπ™Ύπ™Ό corresponds to the π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½[5].πšŸπšŠπš›=4 th item of collection πšƒπ™Ύ.

  • The sixth item π™΅πšπ™Ύπ™Ό[6].πšπš›πš˜πš–=1 of collection π™΅πšπ™Ύπ™Ό corresponds to the π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½[6].πšŸπšŠπš›=2 th item of collection πšƒπ™Ύ.

Figure 5.76.1. Illustration of the correspondence between the items of the π™΅πšπ™Ύπ™Ό and the πšƒπ™Ύ collections according to the permutation defined by the items of the π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½ collection
ctrs/correspondence1
Typical
|π™΅πšπ™Ύπ™Ό|>1
πš›πšŠπš—πšπšŽ(π™΅πšπ™Ύπ™Ό.πšπš›πš˜πš–)>1
Symmetry

All occurrences of two distinct values in π™΅πšπ™Ύπ™Ό.πšπš›πš˜πš– or πšƒπ™Ύ.πšπšŸπšŠπš› can be swapped; all occurrences of a value in π™΅πšπ™Ύπ™Ό.πšπš›πš˜πš– or πšƒπ™Ύ.πšπšŸπšŠπš› can be renamed to any unused value.

Remark

Similar to the πšœπšŠπš–πšŽ constraint except that we also provide the permutation that allows to go from the items of collection π™΅πšπ™Ύπ™Ό to the items of collection πšƒπ™Ύ.

See also

implied by: πšœπš˜πš›πš_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš—.

specialisation: πšœπšŠπš–πšŽΒ (π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½ parameter removed).

Keywords

characteristic of a constraint: derived collection.

combinatorial object: permutation.

constraint arguments: constraint between three collections of variables.

final graph structure: acyclic, bipartite, no loop.

Derived Collection
πšŒπš˜πš•π™΅πšπ™Ύπ™Ό_π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπš›πš˜πš–-πšπšŸπšŠπš›,πšŸπšŠπš›-πšπšŸπšŠπš›),πš’πšπšŽπš–(πšπš›πš˜πš–-π™΅πšπ™Ύπ™Ό.πšπš›πš˜πš–,πšŸπšŠπš›-π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½.πšŸπšŠπš›)]
Arc input(s)

π™΅πšπ™Ύπ™Ό_π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½ πšƒπ™Ύ

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπš›πš˜πš–_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš—,𝚝𝚘)

Arc arity
Arc constraint(s)
β€’ πšπš›πš˜πš–_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš—.πšπš›πš˜πš–=𝚝𝚘.πšπšŸπšŠπš›
β€’ πšπš›πš˜πš–_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš—.πšŸπšŠπš›=𝚝𝚘.πš”πšŽπš’
Graph property(ies)
𝐍𝐀𝐑𝐂=|π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½|

Graph class
β€’ π™°π™²πšˆπ™²π™»π™Έπ™²
β€’ π™±π™Έπ™Ώπ™°πšπšƒπ™Έπšƒπ™΄
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿

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 π™΅πšπ™Ύπ™Ό_π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½, while the sink vertices correspond to the collection πšƒπ™Ύ. Since the final graph contains exactly |π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½| arcs the πšŒπš˜πš›πš›πšŽπšœπš™πš˜πš—πšπšŽπš—πšŒπšŽ constraint holds. As we use the 𝐍𝐀𝐑𝐂 graph property, the arcs of the final graph are stressed in bold.

Figure 5.76.2. Initial and final graph of the πšŒπš˜πš›πš›πšŽπšœπš™πš˜πš—πšπšŽπš—πšŒπšŽ constraint
ctrs/correspondenceA
(a)
ctrs/correspondenceB
(b)
Signature

Because of the second condition πšπš›πš˜πš–_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš—.πšŸπšŠπš›=𝚝𝚘.πš”πšŽπš’ of the arc constraint and since both, the πšŸπšŠπš› attributes of the collection π™΅πšπ™Ύπ™Ό_π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½ and the πš”πšŽπš’ attributes of the collection πšƒπ™Ύ are all -distinct, the final graph contains at most |π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½| arcs. Therefore we can rewrite the graph property 𝐍𝐀𝐑𝐂 = |π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½| to 𝐍𝐀𝐑𝐂 β‰₯ |π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½|. This leads to simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.