title: Graphe partitionnable
text: # 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.
  
  