5.274. proper_forest

DESCRIPTIONLINKSGRAPH
Origin

Derived from πšπš›πšŽπšŽ, [BeldiceanuKatrielLorca06].

Constraint

πš™πš›πš˜πš™πšŽπš›_πšπš˜πš›πšŽπšœπš(π™½πšƒπšπ™΄π™΄πš‚,π™½π™Ύπ™³π™΄πš‚)

Arguments
π™½πšƒπšπ™΄π™΄πš‚πšπšŸπšŠπš›
π™½π™Ύπ™³π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›-πšœπšŸπšŠπš›)
Restrictions
π™½πšƒπšπ™΄π™΄πš‚β‰₯0
πš›πšŽπššπšžπš’πš›πšŽπš(π™½π™Ύπ™³π™΄πš‚,[πš’πš—πšπšŽπš‘,πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›])
|π™½π™Ύπ™³π™΄πš‚|β‰ 1
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰₯1
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰€|π™½π™Ύπ™³π™΄πš‚|
πšπš’πšœπšπš’πš—πšŒπš(π™½π™Ύπ™³π™΄πš‚,πš’πš—πšπšŽπš‘)
π™½π™Ύπ™³π™΄πš‚.πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›β‰₯1
π™½π™Ύπ™³π™΄πš‚.πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›β‰€|π™½π™Ύπ™³π™΄πš‚|
π™½π™Ύπ™³π™΄πš‚.πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›β‰ π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘
Purpose

Cover an undirected graph G by a set of π™½πšƒπšπ™΄π™΄πš‚ trees (i.e.,Β a tree is a connected graph without cycles that contains at least two verticesΒ [Cayley89]) in such a way that each vertex of G belongs to one distinct tree.

Example
3,πš’πš—πšπšŽπš‘-1πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›-{3,6},πš’πš—πšπšŽπš‘-2πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›-{9},πš’πš—πšπšŽπš‘-3πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›-{1,5,7},πš’πš—πšπšŽπš‘-4πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›-{9},πš’πš—πšπšŽπš‘-5πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›-{3},πš’πš—πšπšŽπš‘-6πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›-{1},πš’πš—πšπšŽπš‘-7πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›-{3},πš’πš—πšπšŽπš‘-8πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›-{10},πš’πš—πšπšŽπš‘-9πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›-{2,4},πš’πš—πšπšŽπš‘-10πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›-{8}

The πš™πš›πš˜πš™πšŽπš›_πšπš˜πš›πšŽπšœπš constraint holds since the undirected graph associated with the items of the π™½π™Ύπ™³π™΄πš‚ collection corresponds to a forest containing π™½πšƒπšπ™΄π™΄πš‚=3 trees: each tree respectively involves the vertices {1,3,5,6,7}, {2,4,9} and {8,10}.

Symmetry

Items of π™½π™Ύπ™³π™΄πš‚ are permutable.

Algorithm

A filtering algorithm for the πš™πš›πš˜πš™πšŽπš›_πšπš˜πš›πšŽπšœπš constraint was proposed by N.Β Beldiceanu et al. inΒ [BeldiceanuKatrielLorca06]. It achieves hybrid-consistency and its running time is dominated by the complexity of finding all edges that do not belong to any maximum cardinality matching in an undirected n-vertex, m-edge graph, i.e.,Β O(mΒ·n).

Systems

tree in Choco.

See also

common keyword: πšπš›πšŽπšŽΒ (connected component,tree).

Keywords

characteristic of a constraint: undirected graph.

constraint arguments: constraint involving set variables.

constraint type: graph constraint.

filtering: hybrid-consistency.

final graph structure: connected component, tree, no cycle, symmetric.

Arc input(s)

π™½π™Ύπ™³π™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈ(β‰ )β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš—πš˜πšπšŽπšœ1,πš—πš˜πšπšŽπšœ2)

Arc arity
Arc constraint(s)
πš’πš—_𝚜𝚎𝚝(πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘,πš—πš˜πšπšŽπšœ1.πš—πšŽπš’πšπš‘πš‹πš˜πšžπš›)
Graph property(ies)
β€’ 𝐍𝐕𝐄𝐑𝐓𝐄𝐗=(𝐍𝐀𝐑𝐂+2*π™½πšƒπšπ™΄π™΄πš‚)/2
β€’ 𝐍𝐂𝐂=π™½πšƒπšπ™΄π™΄πš‚
β€’ 𝐍𝐕𝐄𝐑𝐓𝐄𝐗=|π™½π™Ύπ™³π™΄πš‚|

Graph class
πš‚πšˆπ™Όπ™Όπ™΄πšƒπšπ™Έπ™²

Graph model

The graph constraint enforces the following conditions:

  • Each connected component of the final graph has n vertices and 2Β·(n-1) arcs. This is equivalent to the fact that each connected component has not any cycle.

  • Since we use the πΆπΏπΌπ‘„π‘ˆπΈ(β‰ ) arc-generator and since, by definition, the final graph does not contain any isolated vertex, each connected component of the final graph involves more than one vertex.

  • The number of connected components of the final graph is equal to 𝐍𝐂𝐂.

  • All the vertices of the initial graph belong to the final graph.

  • The final graph is symmetric.

PartsΒ (A) andΒ (B) of FigureΒ 5.274.1 respectively show the initial and final graph associated with the Example slot. For each connected component we display its number of arcs as well as its number of vertices. The πš™πš›πš˜πš™πšŽπš›_πšπš˜πš›πšŽπšœπš constraint holds since the final graph has π™½πšƒπšπ™΄π™΄πš‚=𝐍𝐂𝐂=3 connected components and no cycle.

Figure 5.274.1. Initial and final graph of the πš™πš›πš˜πš™πšŽπš›_πšπš˜πš›πšŽπšœπš constraint
ctrs/proper_forestA
(a)
ctrs/proper_forestB
(b)