5.56. bipartite
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Argument
- Restrictions
- Purpose
Consider a digraph described by the collection. Select a subset of arcs of so that the corresponding graph is symmetric (i.e.,Β if there is an arc from to , there is also an arc from to ) and bipartite (i.e.,Β there is no cycle involving an odd number of vertices).
- Example
-
The constraint holds since the collection depicts a symmetric graph with no cycle involving an odd number of vertices. The corresponding graph is depicted by FigureΒ 5.56.1.
Figure 5.56.1. Two ways of looking at the bipartite graph given in the Example slot
- Typical
- Symmetry
Items of are permutable.
- Algorithm
The sketch of a filtering algorithm for the constraint is given inΒ [Dooms06]. Beside enforcing the fact that the graph is symmetric, it checks that the subset of mandatory vertices and arcs is bipartite and removes all potential arcs that would make the previous graph non-bipartite.
- See also
- Keywords
constraint arguments: constraint involving set variables.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph class
-
- Graph model
PartΒ (A) of FigureΒ 5.56.2 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 attribute of a given vertex. PartΒ (B) of FigureΒ 5.56.2 gives the final graph associated with the Example slot.
Figure 5.56.2. Initial and final graph of the set constraint
(a) (b)