5.205. map

DESCRIPTIONLINKSGRAPH
Origin

Inspired by [SedgewickFlajolet96]

Constraint

πš–πšŠπš™(π™½π™±π™²πšˆπ™²π™»π™΄,π™½π™±πšƒπšπ™΄π™΄,π™½π™Ύπ™³π™΄πš‚)

Arguments
π™½π™±π™²πšˆπ™²π™»π™΄πšπšŸπšŠπš›
π™½π™±πšƒπšπ™΄π™΄πšπšŸπšŠπš›
π™½π™Ύπ™³π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,𝚜𝚞𝚌𝚌-πšπšŸπšŠπš›)
Restrictions
π™½π™±π™²πšˆπ™²π™»π™΄β‰₯0
π™½π™±πšƒπšπ™΄π™΄β‰₯0
πš›πšŽπššπšžπš’πš›πšŽπš(π™½π™Ύπ™³π™΄πš‚,[πš’πš—πšπšŽπš‘,𝚜𝚞𝚌𝚌])
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰₯1
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰€|π™½π™Ύπ™³π™΄πš‚|
πšπš’πšœπšπš’πš—πšŒπš(π™½π™Ύπ™³π™΄πš‚,πš’πš—πšπšŽπš‘)
π™½π™Ύπ™³π™΄πš‚.𝚜𝚞𝚌𝚌β‰₯1
π™½π™Ύπ™³π™΄πš‚.πšœπšžπšŒπšŒβ‰€|π™½π™Ύπ™³π™΄πš‚|
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
2,3,πš’πš—πšπšŽπš‘-1𝚜𝚞𝚌𝚌-5,πš’πš—πšπšŽπš‘-2𝚜𝚞𝚌𝚌-9,πš’πš—πšπšŽπš‘-3𝚜𝚞𝚌𝚌-8,πš’πš—πšπšŽπš‘-4𝚜𝚞𝚌𝚌-2,πš’πš—πšπšŽπš‘-5𝚜𝚞𝚌𝚌-9,πš’πš—πšπšŽπš‘-6𝚜𝚞𝚌𝚌-2,πš’πš—πšπšŽπš‘-7𝚜𝚞𝚌𝚌-9,πš’πš—πšπšŽπš‘-8𝚜𝚞𝚌𝚌-8,πš’πš—πšπšŽπš‘-9𝚜𝚞𝚌𝚌-1

The πš–πšŠπš™ constraint holds since, as shown by partΒ (B) of FigureΒ 5.205.1, the graph corresponding to the π™½π™Ύπ™³π™΄πš‚ collection is a map containing π™½π™±π™²πšˆπ™²π™»π™΄=2 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.)

Symmetry

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

See also

common keyword: πšŒπš’πšŒπš•πšŽ, πšπš›πšŠπš™πš‘_πšŒπš›πš˜πšœπšœπš’πš—πš, πšπš›πšŽπšŽΒ (graph partitioning constraint).

Keywords

constraint type: graph constraint, graph partitioning constraint.

final graph structure: connected component.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌=πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘
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.205.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.205.1. Initial and final graph of the πš–πšŠπš™ constraint
ctrs/mapActrs/mapB
(a) (b)