Graphe partitionnable

En théorie des graphes, un graphe partitionnable^[1]^,^[2] 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}, \dots, s_{m})$ telle que :

$m \geq 1$
$\forall i \in {1, ..., m}, s_{i} > 0$
$s_{1} + \dots + 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}, \dots, 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) = {V_{i} : i \in {1, ..., m}}$ de $V$ telle que :

$\forall i \in {1, ..., m}, | V_{i} | = s_{i}$
$\forall i \in {1, ..., m}, 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 = {a, b, c, d, e, f}$
$E = {{a, b}, {b, c}, {c, d}, {d, e}, {e, f}, {f, a}, {c, e}}$

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.

Notes et références

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

Portail de l'informatique théorique

[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, 2004 (arXiv 1309.0119.pdf).

[1]

[2]

Graphe partitionnable

Définitions

Partition d'un entier

k-partition d'un entier

S-partition d'un graphe

Graphe partitionnable

Graphe k-partitionnable

Exemples

k-partition de n

S-partition de G

Notes et références

$k$ -partition d'un entier

$S$ -partition d'un graphe

Graphe $k$ -partitionnable

$k$ -partition de $n$

$S$ -partition de $G$