Graphe partitionnable

En théorie des graphes, un graphe partitionnable est un type particulier de graphe.

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\geq 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 partitionnable

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

Graphe k-partitionnable

Un graphe $G$ est dit $k$-partitionnable 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.