Graphe partitionable

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Sommaire

1 Définitions
2 Exemples
- 2.1 k-partition(n)
- 2.2 S-partition de G

[modifier] Définitions

[modifier] Graphe partitionable

Un graphe G est dit partitionable s'il admet une S-partition pour toute partition S de $| V |$ . $| V |$ correspond au cardinal de l'ensemble des sommets de G.

Un graphe G est dit k-partitionable s'il admet une S-partition pour toute k-partition S de $| V |$ .

[modifier] S-Partition

On note $[m] = \left \{ 1, ...,m \right \}$ .

Soient G un graphe et $\ S = (s_1, ..., s_m )$ une partition de $\ |V|$ , G est dit admettre une S-partition s'il existe une partition $\ P(S)=\left \{V_i : i \in [m]\right \}$ de V telle que :

$\ \forall i \in [m], |V_i| = s_i$
$\ \forall i \in [m], G[V_i]$ est un graphe connexe. L'ensemble P(S) est alors dit être une partition de G induite par S.

On considère de plus ici que :

V est un ensemble non vide
L'ensemble des arêtes E est un sous-ensemble de l'ensemble des parties à deux éléments de V

[modifier] Partition d'un entier

Soit $n$ un entier strictement positif, une partition de $n$ est une suite d’entiers $\ (s_1, ..., s_m )$ vérifiant

$\ m \ge 1$
$\ \forall i \in [m] \mbox{ on a } s_i \ne 0$
$\sum_{i=1}^m s_i = n$

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

[modifier] Exemples

[modifier] k-partition(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).

[modifier] S-partition de G

Soit le graphe G tel que V = {a,b,c,d,e,f} et 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 :