5.239. map
| DESCRIPTION | LINKS | GRAPH |
- Origin
Inspired by [SedgewickFlajolet96]
- Constraint
- Arguments
- Restrictions
- Purpose
Number of trees and number of cycles of a map. We take the description of a map from Β [SedgewickFlajolet96]:
βEvery map decomposes into a set of connected components, also called connected maps. Each component consists of the set of all points that wind up on the same cycle, with each point on the cycle attached to a tree of all points that enter the cycle at that point.β
- Example
-
The constraint holds since, as shown by partΒ (B) of FigureΒ 5.239.1, the graph corresponding to the collection is a map containing cycles (i.e.,Β a first cycle involving vertices 1, 5 and 9 and a second cycle involving vertex 8) and 3 trees (i.e.,Β two trees respectively involving vertices 7 and 4, 6, 2 and attached to the first cycle, and one tree mentioning vertex 3 linked to the second cycle.)
- Typical
- Symmetry
Items of are permutable.
- Arg. properties
Functional dependency: determined by .
Functional dependency: determined by .
- See also
- Keywords
constraint arguments: pure functional dependency.
constraint type: graph constraint, graph partitioning constraint.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
Note that, for the argument of the constraint, we consider a definition different from the one used for the argument of the constraint:
In the constraint the number of trees is equal to the number of vertices of the final graph, which both do not belong to any circuit and have a successor that is located on a circuit. Therefore we count three trees in the context of the Example slot.
In the constraint the number of trees is equal to the number of connected components of the final graph.
PartsΒ (A) andΒ (B) of FigureΒ 5.239.1 respectively show the initial and final graph associated with the Example slot. Since we use the graph property, we display the two connected components of the final graph. Each of them corresponds to a connected map. The first connected map is made up from one circuit and two trees, while the second one consists of one circuit and one tree. Since we also use the graph property, we display with a double circle those vertices that do not belong to any circuit but for which at least one successor belongs to a circuit.
Figure 5.239.1. Initial and final graph of the constraint
(a) (b)