Graphe partitionable

Définitions

Partition d'un entier

Soit n un entier strictement positif, une partition de n est une suite d’entiers $(s_1, \ldots, s_m)$ telle que :

• $m \ge 1$
• $\forall i \in \left \{ 1, ...,m \right \}, s_i > 0$
• $s_1 + \ldots + s_m = n$

k-partition d'un entier

Une k-partition de n est une partition de n possédant k éléments.

S-partition d'un graphe

Soit G = (V,E) un graphe simple où :

• V est l'ensemble non vide des sommets de G.
• E est l'ensemble des arêtes de G, c'est-à-dire un sous-ensemble de l'ensemble des parties à deux éléments de V.

Soit $S = (s_1, \ldots, s_m)$ une partition de | V | (le nombre de sommets du graphe G).

G est dit admettre une S-partition s'il existe une partition $P(S)=\left \{V_i : i \in \left \{ 1, ...,m \right \} \right \}$ de V telle que :

• $\forall i \in \left \{ 1, ...,m \right \}, |V_i| = s_i$
• $\forall i \in \left \{ 1, ...,m \right \}, G[V_i]$ est un graphe connexe.

L'ensemble P(S) est alors dit être une partition de G induite par S.

Graphe partitionable

Un graphe G = (V,E) est dit partitionable s'il admet une S-partition pour toute partition S de | V | .

Graphe k-partitionable

Un graphe G est dit k-partitionable s'il admet une S-partition pour toute k-partition S de | V | .

Exemples

k-partition de n

• Une 2-partition de 5 est (3,2).
• Une 4-partition de 10 est (1,4,1,4).
• Une 7-partition de 22 est (2,2,3,1,3,8,3).

S-partition de G

Soit le graphe G = (V,E) tel que :

• $V = \left \{ a,b,c,d,e,f \right \}$
• $E = \left \{ \left \{ a, b \right \},\left \{ b,c \right \}, \left \{ c,d \right \},\left \{ d, e \right \},\left \{ e,f \right \}, \left \{ f,a \right \},\left \{ c, e \right \} \right \}$

représenté ci-dessous par :

| V | = 6. G admet 3 partitions de 6 possibles : (1,1,4), (1,2,3) et (2,2,2) (en considérant que l'ordre des différentes suites n'a pas d'importance).

Ces trois partitions de l'entier 6 peuvent être appliquées respectivement pour partager le graphe G comme ceci :

Il existe bien d'autres façons d'appliquer ces 3 partitions sur ce graphe. Le schéma ci-dessus est une des représentations possibles.