4.3. Graph invariants

Within the scope of the graph-based description this section shows how to use implied constraints, which are systematically linked to the description of a global constraint. This usually occurs in the following context:

  • Quite often, it happens that one wants to enforce the final graph to satisfy more than one graph property. In this context, these graph properties involve several graph parameters that cannot vary independently.

    EXAMPLE: As a practical example, consider the 𝚐𝚛𝚘𝚞𝚙 constraint and its first graph constraint. It involves the four graph parameters 𝐍𝐂𝐂, 𝐌𝐈𝐍_𝐍𝐂𝐂, 𝐌𝐀𝐗_𝐍𝐂𝐂 and 𝐍𝐕𝐄𝐑𝐓𝐄𝐗, which respectively correspond to the number of connected components, the number of vertices of the smallest connected component, the number of vertices of the largest connected component and the number of vertices of the final graph. In this example the number of connected components of the final graph cannot vary independently from the size of the smallest connected component. The same remark applies also for the size of the largest connected component. Having a graph invariant that directly relates the four graph parameters can dramatically improve the propagation.

  • Even though the description of a global constraint involves a single graph parameter 𝐂, we can introduce the number of vertices, 𝐍𝐕𝐄𝐑𝐓𝐄𝐗, and the number of arcs, 𝐍𝐀𝐑𝐂, of the final digraph. In this context, we can take advantage of graph invariants linking 𝐂, 𝐍𝐀𝐑𝐂 and 𝐍𝐕𝐄𝐑𝐓𝐄𝐗.

  • It also happens that we enforce two graph constraints 𝒢𝒞 1 and 𝒢𝒞 2 that have the same initial graph G. In this context we consider the following situations:

    • Each arc of G belongs to one of the final graphs associated with 𝒢𝒞 1 or with 𝒢𝒞 2 (but not to both). An example of such global constraint is the 𝚌𝚑𝚊𝚗𝚐𝚎_𝚌𝚘𝚗𝚝𝚒𝚗𝚞𝚒𝚝𝚢 constraint. Within the graph invariants this situation is denoted by 𝚊𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗.

    • Each vertex of G belongs to one of the final graphs associated with 𝒢𝒞 1 or with 𝒢𝒞 2 (but not to both). An example of such global constraint is the 𝚐𝚛𝚘𝚞𝚙 constraint. Within the graph invariants this situation is denoted by 𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗.

    In these situations the graph properties associated with the two graph constraints are also not independent.

In practice the graphs associated with global constraints have a regular structure that comes from the initial graph or from the property of the arc constraints. So, in addition to graph invariants that hold for any graph, we want also tighter graph invariants that hold for specific graph classes. The next section introduces the graph classes we consider, while the two other sections give the graph invariants on one and two graphs.