Graphe partitionable

Définitions

Partition d'un entier

Soit n un entier strictement positif, une partition de n est une suite d’entiers telle que :

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 une partition de | V | (le nombre de sommets du graphe G).

G est dit admettre une S-partition s'il existe une partition de V telle que :

• 
• 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 :

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.

• Portail de l'informatique théorique