Modular decomposition

Modular decomposition

sage.graphs.modular_decomposition.modular_decomposition.modular_decomposition(g)

Returns a modular decomposition of the given graph.

INPUT:

  • g – a graph

OUTPUT:

A pair of two values (recursively encoding the decomposition) :

  • The type of the current module :

    • "Parallel"
    • "Prime"
    • "Serie"
  • The list of submodules (as list of pairs (type, list), recursively...) or the vertex’s name if the module is a singleton.

Note

As this fuction could be used by efficient C routines, the vertices returned are not labels but identifiants from [0, ..., g.order()-1]

ALGORITHM:

This function uses a C implementation of a 2-step algorithm implemented by Fabien de Montgolfier [FMDecb] :

EXAMPLES:

The Bull Graph is prime:

sage: from sage.graphs.modular_decomposition.modular_decomposition import modular_decomposition
sage: modular_decomposition(graphs.BullGraph())
('Prime', [3, 4, 0, 1, 2])

The Petersen Graph too:

sage: modular_decomposition(graphs.PetersenGraph())
('Prime', [2, 6, 3, 9, 7, 8, 0, 1, 5, 4])

This a clique on 5 vertices with 2 pendant edges, though, has a more interesting decomposition

sage: g = graphs.CompleteGraph(5)
sage: g.add_edge(0,5)
sage: g.add_edge(0,6)
sage: modular_decomposition(g)
('Serie', [0, ('Parallel', [5, ('Serie', [1, 4, 3, 2]), 6])])

REFERENCES:

[FMDecb]Fabien de Montgolfier http://www.liafa.jussieu.fr/~fm/algos/index.html
[HabibViennot1999b]Michel Habib, Christiphe Paul, Laurent Viennot Partition refinement techniques: An interesting algorithmic tool kit International Journal of Foundations of Computer Science vol. 10 n2 pp.147–170, 1999
[CapHabMont02b]C. Capelle, M. Habib et F. de Montgolfier Graph decomposition and Factorising Permutations Discrete Mathematics and Theoretical Computer Sciences, vol 5 no. 1 , 2002.

Previous topic

Products of graphs

Next topic

Convexity properties of graphs

This Page