Global Constraint Catalog

4.3.4.2. two parameters/one final graph

$𝐌𝐀𝐗_𝐍𝐂𝐂$ , $𝐌𝐀𝐗_𝐍𝐒𝐂𝐂$

Proposition 14

𝐌𝐀𝐗_𝐍𝐂𝐂 = 0 \Leftrightarrow 𝐌𝐀𝐗_𝐍𝐒𝐂𝐂 = 0

Proof 14 By definition of $𝐌𝐀𝐗_𝐍𝐂𝐂$ and of $𝐌𝐀𝐗_𝐍𝐒𝐂𝐂$ .

Proposition 15

𝐌𝐀𝐗_𝐍𝐒𝐂𝐂 \leq 𝐌𝐀𝐗_𝐍𝐂𝐂

Proof 15 $𝐌𝐀𝐗_𝐍𝐒𝐂𝐂$ is a lower bound of the size of the largest connected component since the largest strongly connected component is for sure included within a connected component.

$𝐌𝐀𝐗_𝐍𝐂𝐂$ , $𝐌𝐈𝐍_𝐍𝐂𝐂$

Proposition 16

𝐌𝐀𝐗_𝐍𝐂𝐂 = 0 \Leftrightarrow 𝐌𝐈𝐍_𝐍𝐂𝐂 = 0

Proof 16 By definition of $𝐌𝐀𝐗_𝐍𝐂𝐂$ and of $𝐌𝐈𝐍_𝐍𝐂𝐂$ .

Proposition 17

𝐌𝐈𝐍_𝐍𝐂𝐂 \leq 𝐌𝐀𝐗_𝐍𝐂𝐂

Proof 17 By definition of $𝐌𝐈𝐍_𝐍𝐂𝐂$ and of $𝐌𝐀𝐗_𝐍𝐂𝐂$ .

$𝐌𝐀𝐗_𝐍𝐂𝐂$ , $𝐍𝐀𝐑𝐂$

Proposition 18

𝐌𝐀𝐗_𝐍𝐂𝐂 = 0 \Leftrightarrow 𝐍𝐀𝐑𝐂 = 0

Proof 18 By definition of $𝐌𝐀𝐗_𝐍𝐂𝐂$ and of $𝐍𝐀𝐑𝐂$ .

Proposition 19

𝐌𝐀𝐗_𝐍𝐂𝐂 > 0 \Rightarrow 𝐍𝐀𝐑𝐂 \geq max (1, 𝐌𝐀𝐗_𝐍𝐂𝐂 - 1)

𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌 : 𝐌𝐀𝐗_𝐍𝐂𝐂 > 0 \Rightarrow 𝐍𝐀𝐑𝐂 \geq max (1, 2 \cdot 𝐌𝐀𝐗_𝐍𝐂𝐂 - 2)

𝚎𝚚𝚞𝚒𝚟𝚊𝚕𝚎𝚗𝚌𝚎 : 𝐍𝐀𝐑𝐂 \geq 𝐌𝐀𝐗_{𝐍𝐂𝐂}^{2}

𝐚𝐫𝐜_𝐠𝐞𝐧 = 𝑃𝐴𝑇𝐻 : 𝐍𝐀𝐑𝐂 \geq 𝐌𝐀𝐗_𝐍𝐂𝐂 - 1

Proof 19

(19) $𝐌𝐀𝐗_𝐍𝐂𝐂 - 1$ arcs are needed to connect $𝐌𝐀𝐗_𝐍𝐂𝐂$ vertices that belong to a given connected component containing at least two vertices. And one arc is required for a connected component containing a single vertex.

(20) Similarly, when the graph is symmetric, $2 \cdot 𝐌𝐀𝐗_𝐍𝐂𝐂 - 2$ arcs are needed to connect $𝐌𝐀𝐗_𝐍𝐂𝐂$ vertices that belong to a given connected component containing at least two vertices.

(21) Finally, when the graph is reflexive, symmetric and transitive, $𝐌𝐀𝐗_{𝐍𝐂𝐂}^{2}$ arcs are needed to connect $𝐌𝐀𝐗_𝐍𝐂𝐂$ vertices that belong to a given connected component.

(22) When the initial graph corresponds to a path, the minimum number of arcs of a connected component involving $n$ vertices is equal to $n - 1$ .

$𝐌𝐀𝐗_𝐍𝐂𝐂$ , $𝐍𝐒𝐈𝐍𝐊$

Proposition 20

𝐌𝐀𝐗_𝐍𝐂𝐂 = 0 \Rightarrow 𝐍𝐒𝐈𝐍𝐊 = 0

Proof 20 By definition of $𝐌𝐀𝐗_𝐍𝐂𝐂$ and of $𝐍𝐒𝐈𝐍𝐊$ .

Proposition 21

𝐍𝐒𝐈𝐍𝐊 \geq 1 \Rightarrow 𝐌𝐀𝐗_𝐍𝐂𝐂 \geq 2

Proof 21 Since we do not have any isolated vertex a sink is connected to at least one other vertex. Therefore, if the graph has a sink, there exists at least one connected component with at least two vertices.

$𝐌𝐀𝐗_𝐍𝐂𝐂$ , $𝐍𝐒𝐎𝐔𝐑𝐂𝐄$

Proposition 22

𝐌𝐀𝐗_𝐍𝐂𝐂 = 0 \Rightarrow 𝐍𝐒𝐎𝐔𝐑𝐂𝐄 = 0

Proof 22 By definition of $𝐌𝐀𝐗_𝐍𝐂𝐂$ and of $𝐍𝐒𝐎𝐔𝐑𝐂𝐄$ .

Proposition 23

𝐍𝐒𝐎𝐔𝐑𝐂𝐄 \geq 1 \Rightarrow 𝐌𝐀𝐗_𝐍𝐂𝐂 \geq 2

Proof 23 Since we do not have any isolated vertex a source is connected to at least one other vertex. Therefore, if the graph has a source, there exists at least one connected component with at least two vertices.

$𝐌𝐀𝐗_𝐍𝐂𝐂$ , $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$

Proposition 24

𝐌𝐀𝐗_𝐍𝐂𝐂 = 0 \Leftrightarrow 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 = 0

Proof 24 By definition of $𝐌𝐀𝐗_𝐍𝐂𝐂$ and of $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$ .

Proposition 25

𝐍𝐕𝐄𝐑𝐓𝐄𝐗 \geq 𝐌𝐀𝐗_𝐍𝐂𝐂

Proof 25 By definition of $𝐌𝐀𝐗_𝐍𝐂𝐂$ .

$𝐌𝐀𝐗_𝐍𝐒𝐂𝐂$ , $𝐌𝐈𝐍_𝐍𝐒𝐂𝐂$

Proposition 26

𝐌𝐀𝐗_𝐍𝐒𝐂𝐂 = 0 \Leftrightarrow 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 = 0

Proof 26 By definition of $𝐌𝐀𝐗_𝐍𝐒𝐂𝐂$ and of $𝐌𝐈𝐍_𝐍𝐒𝐂𝐂$ .

Proposition 27

𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 \leq 𝐌𝐀𝐗_𝐍𝐒𝐂𝐂

Proof 27 By definition of $𝐌𝐈𝐍_𝐍𝐒𝐂𝐂$ and of $𝐌𝐀𝐗_𝐍𝐒𝐂𝐂$ .

$𝐌𝐀𝐗_𝐍𝐒𝐂𝐂$ , $𝐍𝐀𝐑𝐂$

Proposition 28

𝐌𝐀𝐗_𝐍𝐒𝐂𝐂 = 0 \Leftrightarrow 𝐍𝐀𝐑𝐂 = 0

Proof 28 By definition of $𝐌𝐀𝐗_𝐍𝐒𝐂𝐂$ and of $𝐍𝐀𝐑𝐂$ .

Proposition 29

𝐍𝐀𝐑𝐂 \geq 𝐌𝐀𝐗_𝐍𝐒𝐂𝐂

𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌 : 𝐍𝐀𝐑𝐂 \geq 2 \cdot 𝐌𝐀𝐗_𝐍𝐒𝐂𝐂

𝚎𝚚𝚞𝚒𝚟𝚊𝚕𝚎𝚗𝚌𝚎 : 𝐍𝐀𝐑𝐂 \geq 𝐌𝐀𝐗_{𝐍𝐒𝐂𝐂}^{2}

Proof 29 (32) In a strongly connected component at least one arc has to leave each vertex. Since we have at least one strongly connected component of $𝐌𝐀𝐗_𝐍𝐒𝐂𝐂$ vertices this leads to the previous inequality.

$𝐌𝐀𝐗_𝐍𝐒𝐂𝐂$ , $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$

Proposition 30

𝐌𝐀𝐗_𝐍𝐒𝐂𝐂 = 0 \Leftrightarrow 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 = 0

Proof 30 By definition of $𝐌𝐀𝐗_𝐍𝐒𝐂𝐂$ and of $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$ .

Proposition 31

𝐍𝐕𝐄𝐑𝐓𝐄𝐗 \geq 𝐌𝐀𝐗_𝐍𝐒𝐂𝐂

Proof 31 By definition of $𝐌𝐀𝐗_𝐍𝐒𝐂𝐂$ .

$𝐌𝐈𝐍_𝐍𝐂𝐂$ , $𝐌𝐈𝐍_𝐍𝐒𝐂𝐂$

Proposition 32

𝐌𝐈𝐍_𝐍𝐂𝐂 = 0 \Leftrightarrow 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 = 0

Proof 32 By definition of $𝐌𝐈𝐍_𝐍𝐂𝐂$ and of $𝐌𝐈𝐍_𝐍𝐒𝐂𝐂$ .

Proposition 33

𝐌𝐈𝐍_𝐍𝐂𝐂 \geq 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂

Proof 33 By construction $𝐌𝐈𝐍_𝐍𝐂𝐂$ is an upper bound of the number of vertices of the smallest strongly connected component.

$𝐌𝐈𝐍_𝐍𝐂𝐂$ , $𝐍𝐀𝐑𝐂$

Proposition 34

𝐌𝐈𝐍_𝐍𝐂𝐂 = 0 \Leftrightarrow 𝐍𝐀𝐑𝐂 = 0

Proof 34 By definition of $𝐌𝐈𝐍_𝐍𝐂𝐂$ and of $𝐍𝐀𝐑𝐂$ .

Proposition 35

𝐌𝐈𝐍_𝐍𝐂𝐂 > 0 \Rightarrow 𝐍𝐀𝐑𝐂 \geq max (1, 𝐌𝐈𝐍_𝐍𝐂𝐂 - 1)

𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌 : 𝐌𝐈𝐍_𝐍𝐂𝐂 > 0 \Rightarrow 𝐍𝐀𝐑𝐂 \geq max (1, 2 \cdot 𝐌𝐈𝐍_𝐍𝐂𝐂 - 2)

𝚎𝚚𝚞𝚒𝚟𝚊𝚕𝚎𝚗𝚌𝚎 : 𝐍𝐀𝐑𝐂 \geq 𝐌𝐈𝐍_{𝐍𝐂𝐂}^{2}

𝐚𝐫𝐜_𝐠𝐞𝐧 = 𝑃𝐴𝑇𝐻 : 𝐍𝐀𝐑𝐂 \geq 𝐌𝐈𝐍_𝐍𝐂𝐂 - 1

Proof 35 Similar to Proposition 19.

$𝐌𝐈𝐍_𝐍𝐂𝐂$ , $𝐍𝐂𝐂$

Proposition 36

𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎_𝚕𝚘𝚘𝚙𝚜_𝚊𝚛𝚎_𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍 : (𝐌𝐈𝐍_𝐍𝐂𝐂 + 1) \cdot 𝐍𝐂𝐂 \leq {𝐍𝐕𝐄𝐑𝐓𝐄𝐗}_{𝙸𝙽𝙸𝚃𝙸𝙰𝙻} + 1

Proof 36 By definition of $𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎_𝚕𝚘𝚘𝚙𝚜_𝚊𝚛𝚎_𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍$ .

$𝐌𝐈𝐍_𝐍𝐂𝐂$ , $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$

Proposition 37

𝐌𝐈𝐍_𝐍𝐂𝐂 = 0 \Leftrightarrow 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 = 0

Proof 37 By definition of $𝐌𝐈𝐍_𝐍𝐂𝐂$ and of $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$ .

Proposition 38

𝐍𝐕𝐄𝐑𝐓𝐄𝐗 \geq 𝐌𝐈𝐍_𝐍𝐂𝐂

Proof 38 By definition of $𝐌𝐈𝐍_𝐍𝐂𝐂$ .

Proposition 39

𝐌𝐈𝐍_𝐍𝐂𝐂 \notin [min (⌊\frac{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}{2}⌋, ⌊\frac{{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}_{𝙸𝙽𝙸𝚃𝙸𝙰𝙻} - 1}{2}⌋) + 1, 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 - 1]

Proof 39 On the one hand, if $𝐍𝐂𝐂 \leq 1$ , we have that $𝐌𝐈𝐍_𝐍𝐂𝐂 \geq 𝐍𝐕𝐄𝐑𝐓𝐄𝐗$ . On the other hand, if $𝐍𝐂𝐂 > 1$ , we have that $𝐌𝐈𝐍_𝐍𝐂𝐂 + 𝐌𝐈𝐍_𝐍𝐂𝐂 \leq 𝐍𝐕𝐄𝐑𝐓𝐄𝐗$ and that $𝐌𝐈𝐍_𝐍𝐂𝐂 + 𝐌𝐈𝐍_𝐍𝐂𝐂 + 1 \leq {𝐍𝐕𝐄𝐑𝐓𝐄𝐗}_{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}$ , which by isolating $𝐌𝐈𝐍_𝐍𝐂𝐂$ and by grouping the two inequalities leads to $𝐌𝐈𝐍_𝐍𝐂𝐂 \leq min (⌊\frac{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}{2}⌋, ⌊\frac{{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}_{𝙸𝙽𝙸𝚃𝙸𝙰𝙻} - 1}{2}⌋)$ . The result follows.

$𝐌𝐈𝐍_𝐍𝐒𝐂𝐂$ , $𝐍𝐀𝐑𝐂$

Proposition 40

𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 = 0 \Leftrightarrow 𝐍𝐀𝐑𝐂 = 0

Proof 40 By definition of $𝐌𝐈𝐍_𝐍𝐒𝐂𝐂$ and of $𝐍𝐀𝐑𝐂$ .

Proposition 41

𝐍𝐀𝐑𝐂 \geq 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂

𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌 : 𝐍𝐀𝐑𝐂 \geq 2 \cdot 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂

𝚎𝚚𝚞𝚒𝚟𝚊𝚕𝚎𝚗𝚌𝚎 : 𝐍𝐀𝐑𝐂 \geq 𝐌𝐈𝐍_{𝐍𝐒𝐂𝐂}^{2}

Proof 41 Similar to Proposition 29.

$𝐌𝐈𝐍_𝐍𝐒𝐂𝐂$ , $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$

Proposition 42

𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 = 0 \Leftrightarrow 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 = 0

Proof 42 By definition of $𝐌𝐈𝐍_𝐍𝐒𝐂𝐂$ and of $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$ .

Proposition 43

𝐍𝐕𝐄𝐑𝐓𝐄𝐗 \geq 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂

Proof 43 By definition of $𝐌𝐈𝐍_𝐍𝐒𝐂𝐂$ .

$𝐍𝐀𝐑𝐂$ , $𝐍𝐂𝐂$

Proposition 44

𝐍𝐀𝐑𝐂 = 0 \Leftrightarrow 𝐍𝐂𝐂 = 0

Proof 44 By definition of $𝐍𝐀𝐑𝐂$ and of $𝐍𝐂𝐂$ .

Proposition 45

𝐍𝐀𝐑𝐂 \geq 𝐍𝐂𝐂

Proof 45 Each connected component contains at least one arc (since, by hypothesis, each vertex has at least one arc).

$𝐍𝐀𝐑𝐂$ , $𝐍𝐒𝐂𝐂$

Proposition 46

𝐍𝐀𝐑𝐂 = 0 \Leftrightarrow 𝐍𝐒𝐂𝐂 = 0

Proof 46 By definition of $𝐍𝐀𝐑𝐂$ and of $𝐍𝐒𝐂𝐂$ .

Proposition 47

𝐍𝐀𝐑𝐂 \geq 𝐍𝐒𝐂𝐂

𝚗𝚘 𝚕𝚘𝚘𝚙 : 𝐍𝐀𝐑𝐂 \geq 2 \cdot 𝐍𝐒𝐂𝐂

Proof 47 57 (respectively 58) holds since each strongly connected component contains at least one (respectively two) arc(s).

$𝐍𝐀𝐑𝐂$ , $𝐍𝐒𝐈𝐍𝐊$

Proposition 48

𝐍𝐀𝐑𝐂 \geq 𝐍𝐒𝐈𝐍𝐊

Proof 48 Since isolated vertices are not allowed, each sink has a distinct ingoing arc.

$𝐍𝐀𝐑𝐂$ , $𝐍𝐒𝐎𝐔𝐑𝐂𝐄$

Proposition 49

𝐍𝐀𝐑𝐂 \geq 𝐍𝐒𝐎𝐔𝐑𝐂𝐄

Proof 49 Since isolated vertices are not allowed, each source has a distinct outgoing arc.

$𝐍𝐀𝐑𝐂$ , $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$

Proposition 50

𝐍𝐀𝐑𝐂 = 0 \Leftrightarrow 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 = 0

Proof 50 By definition of $𝐍𝐀𝐑𝐂$ and of $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$ .

Proposition 51

𝐍𝐀𝐑𝐂 \leq {𝐍𝐕𝐄𝐑𝐓𝐄𝐗}^{2}

𝐚𝐫𝐜_𝐠𝐞𝐧 = 𝐶𝐼𝑅𝐶𝑈𝐼𝑇 : 𝐍𝐀𝐑𝐂 \leq 𝐍𝐕𝐄𝐑𝐓𝐄𝐗

𝐚𝐫𝐜_𝐠𝐞𝐧 = 𝐶𝐻𝐴𝐼𝑁 : 𝐍𝐀𝐑𝐂 \leq 2 \cdot 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 - 2

𝐚𝐫𝐜_𝐠𝐞𝐧 = 𝐶𝐿𝐼𝑄𝑈𝐸 (\leq) : 𝐍𝐀𝐑𝐂 \leq \frac{𝐍𝐕𝐄𝐑𝐓𝐄𝐗 \cdot (𝐍𝐕𝐄𝐑𝐓𝐄𝐗 + 1)}{2}

𝐚𝐫𝐜_𝐠𝐞𝐧 = 𝐶𝐿𝐼𝑄𝑈𝐸 (\geq) : 𝐍𝐀𝐑𝐂 \leq \frac{𝐍𝐕𝐄𝐑𝐓𝐄𝐗 \cdot (𝐍𝐕𝐄𝐑𝐓𝐄𝐗 + 1)}{2}

𝐚𝐫𝐜_𝐠𝐞𝐧 = 𝐶𝐿𝐼𝑄𝑈𝐸 (<) : 𝐍𝐀𝐑𝐂 \leq \frac{𝐍𝐕𝐄𝐑𝐓𝐄𝐗 \cdot (𝐍𝐕𝐄𝐑𝐓𝐄𝐗 - 1)}{2}

𝐚𝐫𝐜_𝐠𝐞𝐧 = 𝐶𝐿𝐼𝑄𝑈𝐸 (>) : 𝐍𝐀𝐑𝐂 \leq \frac{𝐍𝐕𝐄𝐑𝐓𝐄𝐗 \cdot (𝐍𝐕𝐄𝐑𝐓𝐄𝐗 - 1)}{2}

𝐚𝐫𝐜_𝐠𝐞𝐧 = 𝐶𝐿𝐼𝑄𝑈𝐸 (\neq) : 𝐍𝐀𝐑𝐂 \leq {𝐍𝐕𝐄𝐑𝐓𝐄𝐗}^{2} - 𝐍𝐕𝐄𝐑𝐓𝐄𝐗

𝐚𝐫𝐜_𝐠𝐞𝐧 = 𝐶𝑌𝐶𝐿𝐸 : 𝐍𝐀𝐑𝐂 \leq 2 \cdot 𝐍𝐕𝐄𝐑𝐓𝐄𝐗

𝐚𝐫𝐜_𝐠𝐞𝐧 = 𝑃𝐴𝑇𝐻 : 𝐍𝐀𝐑𝐂 \leq 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 - 1

Proof 51 62 holds since each vertex of a digraph can have at most $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$ successors. The next items correspond to the maximum number of arcs that can be achieved according to a specific arc generator.

Note that, when the equality is reached in 62, the corresponding extreme graph is in fact the graph initially generated. The same observation holds for inequalities 63 to 71. As a consequence all $U$ -arcs have to be turned into $T$ -arcs.

Proposition 52

2 \cdot 𝐍𝐀𝐑𝐂 \geq 𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 52 By induction on the number of vertices of a graph $G$ :

If $𝐍𝐕𝐄𝐑𝐓𝐄𝐗 (G)$ is equal to 1 or 2 Proposition 52 holds.
Assume that $𝐍𝐕𝐄𝐑𝐓𝐄𝐗 (G) \geq 3$ .
- Assume there exists a vertex $v$ such that, if we remove $v$ , we do not create any isolated vertex in the remaining graph. We have $𝐍𝐀𝐑𝐂 (G) \geq 𝐍𝐀𝐑𝐂 (G - v) + 1$ . Thus $2 \cdot 𝐍𝐀𝐑𝐂 (G) \geq 2 \cdot 𝐍𝐀𝐑𝐂 (G - v) + 1$ . Since by induction hypothesis $2 \cdot 𝐍𝐀𝐑𝐂 (G - v) \geq 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 (G - v) = 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 (G) - 1$ the result holds.
- Otherwise, all the connected components of $G$ are reduced to two elements with only one arc. We remove one of such connected component $(v, w)$ .
  
  Thus $𝐍𝐀𝐑𝐂 (G) = 𝐍𝐀𝐑𝐂 (G - {v, w}) + 1$ . As by induction hypothesis, $2 \cdot 𝐍𝐀𝐑𝐂 (G - {v, w}) \geq 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 (G - {v, w}) = 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 (G) - 2$ the result holds.

Note that, when the equality is reached in 52, the corresponding extreme graph is in fact a perfect matching of the graph. As a consequence all $U$ -arcs that do not belong to any perfect matching have to be turned into $F$ -arcs.

Proposition 53

𝐚𝐫𝐜_𝐠𝐞𝐧 = 𝐿𝑂𝑂𝑃 : 𝐍𝐀𝐑𝐂 = 𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 53 From the definition of $𝐿𝑂𝑂𝑃$ .

$𝐍𝐂𝐂$ , $𝐍𝐒𝐂𝐂$

Proposition 54

𝐍𝐂𝐂 = 0 \Leftrightarrow 𝐍𝐒𝐂𝐂 = 0

Proof 54 By definition of $𝐍𝐂𝐂$ and of $𝐍𝐒𝐂𝐂$ .

Proposition 55

𝐍𝐂𝐂 \leq 𝐍𝐒𝐂𝐂

Proof 55 Holds since each connected component contains at least one strongly connected component.

Note that, when the equality is reached in 55, each connected component of the corresponding extreme graph is strongly connected. As a consequence all sink vertices of the graph induced by the $T$ -vertices and the $T$ -arcs should have at least one successor.

$𝐍𝐂𝐂$ , $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$

Proposition 56

𝐍𝐂𝐂 = 0 \Leftrightarrow 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 = 0

Proof 56 By definition of $𝐍𝐂𝐂$ and of $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$ .

Proposition 57

𝐍𝐂𝐂 \leq 𝐍𝐕𝐄𝐑𝐓𝐄𝐗

𝚗𝚘 𝚕𝚘𝚘𝚙 : 2 \cdot 𝐍𝐂𝐂 \leq 𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 57 77 (respectively 78) holds since each connected component contains at least one (respectively two) vertex.

Note that, when the equality is reached in 77, the corresponding extreme graph does not contain any arc between two distinct vertices. As a consequence any $U$ -arc between two distinct vertices is turned into a $F$ -vertex.

Proposition 58

\begin{matrix} 𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗 \land 𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎_𝚕𝚘𝚘𝚙𝚜_𝚊𝚛𝚎_𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍 : \\ 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 \leq {𝐍𝐕𝐄𝐑𝐓𝐄𝐗}_{𝙸𝙽𝙸𝚃𝙸𝙰𝙻} - (𝐍𝐂𝐂 - 1) \end{matrix}

Proof 58 Holds since between two “consecutive” connected components of the initial graph there is at least one vertex that is missing.

$𝐍𝐒𝐂𝐂$ , $𝐍𝐒𝐈𝐍𝐊$

Proposition 59

𝐍𝐒𝐂𝐂 \geq 𝐍𝐒𝐈𝐍𝐊 + 1

Proof 59 Since each sink cannot belong to a circuit and since no isolated vertex is allowed at least one extra non-sink vertex is required the result follows.

$𝐍𝐒𝐂𝐂$ , $𝐍𝐒𝐎𝐔𝐑𝐂𝐄$

Proposition 60

𝐍𝐒𝐂𝐂 \geq 𝐍𝐒𝐎𝐔𝐑𝐂𝐄 + 1

Proof 60 Since each source cannot belong to a circuit and since no isolated vertex is allowed at least one extra non-source vertex is required the result follows.

$𝐍𝐒𝐂𝐂$ , $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$

Proposition 61

𝐍𝐒𝐂𝐂 = 0 \Leftrightarrow 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 = 0

Proof 61 By definition of $𝐍𝐒𝐂𝐂$ and of $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$ .

Proposition 62

𝐍𝐒𝐂𝐂 \leq 𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 62 Proposition 62 holds since each strongly connected component contains at least one vertex.

Proposition 63

𝚊𝚌𝚢𝚌𝚕𝚒𝚌 : 𝐍𝐒𝐂𝐂 = 𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 63 In a directed acyclic graph we have that each vertex corresponds to a strongly connected component involving only that vertex.

$𝐍𝐒𝐈𝐍𝐊$ , $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$

Proposition 64

𝐍𝐕𝐄𝐑𝐓𝐄𝐗 = 0 \Rightarrow 𝐍𝐒𝐈𝐍𝐊 = 0

Proof 64 By definition of $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$ and of $𝐍𝐒𝐈𝐍𝐊$ .

Proposition 65

𝐍𝐕𝐄𝐑𝐓𝐄𝐗 > 0 \Rightarrow 𝐍𝐒𝐈𝐍𝐊 < 𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 65 Holds since each sink must have a predecessor that cannot be a sink and since each vertex has at least one arc.

$𝐍𝐒𝐎𝐔𝐑𝐂𝐄$ , $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$

Proposition 66

𝐍𝐕𝐄𝐑𝐓𝐄𝐗 = 0 \Rightarrow 𝐍𝐒𝐎𝐔𝐑𝐂𝐄 = 0

Proof 66 By definition of $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$ and of $𝐍𝐒𝐎𝐔𝐑𝐂𝐄$ .

Proposition 67

𝐍𝐕𝐄𝐑𝐓𝐄𝐗 > 0 \Rightarrow 𝐍𝐒𝐎𝐔𝐑𝐂𝐄 < 𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 67 Holds since each source must have a successor that cannot be a source and since each vertex has at least one arc.

Global Constraint Catalog

4. Further Topics

4.3.4.2. two parameters/one final graph