En théorie des graphes, un graphe partitionnable.. est un type particulier de graphe.
Définitions
Partition d'un entier Soit un entier strictement positif, une partition de est une suite d’entiers telle que :
-partition d'un entier Une -partition de est une partition de possédant éléments.
-partition d'un graphe Soit un graphe simple où : est l'ensemble non vide des sommets de G. est l'ensemble des arêtes de G, c'est-à-dire un sous-ensemble de l'ensemble des parties à deux éléments de .
Soit une partition de (le nombre de sommets du graphe G).
est dit admettre une -partition s'il existe une partition de telle que :
est un graphe connexe. L'ensemble est alors dit être une partition de induite par .
Graphe partitionnable Un graphe est dit partitionnable s'il admet une -partition pour toute partition de .
Graphe -partitionnable
Un graphe est dit -partitionnable s'il admet une -partition pour toute -partition de .
Exemples
-partition de Une -partition de est . Une -partition de est . Une -partition de est .
-partition de Soit le graphe tel que :
représenté ci-dessous par :
. admet 3 partitions de 6 possibles : , et (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 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.
Notes et références
Catégorie:Concept en théorie des graphes