Graphe partitionnable

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En théorie des graphes, un graphe partitionnable[1],[2] est un type particulier de graphe.

Définitions[modifier | modifier le code]

Partition d'un entier[modifier | modifier le code]

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

-partition d'un entier[modifier | modifier le code]

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

-partition d'un graphe[modifier | modifier le code]

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[modifier | modifier le code]

Un graphe est dit partitionnable s'il admet une -partition pour toute partition de .

Graphe -partitionnable[modifier | modifier le code]

Un graphe est dit -partitionnable s'il admet une -partition pour toute -partition de .

Exemples[modifier | modifier le code]

-partition de [modifier | modifier le code]

  • Une -partition de est .
  • Une -partition de est .
  • Une -partition de est .

-partition de [modifier | modifier le code]

Soit le graphe tel que :

représenté ci-dessous par :

Graphe 6 sommets.png

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

Graphe k partitionable.png

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[modifier | modifier le code]

  1. (en) « Graphclass: partitionable », Information System on Graph Classes and their Inclusions (consulté le 23 janvier 2018).
  2. Nicolas Trotignon, Graphes parfaits : Structure et algorithmes (Thèse), Université Grenoble I, Joseph Fourier, (arXiv 1309.0119.pdf).