Aller au contenu

Graphe partitionnable

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

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 $n$ un entier strictement positif, une partition de $n$ est une suite d’entiers $(s_{1},\ldots ,s_{m})$ telle que :

$m\geq 1$
$\forall i\in \left\{1,...,m\right\},s_{i}>0$
$s_{1}+\ldots +s_{m}=n$

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

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

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

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},\ldots ,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)=\left\{V_{i}:i\in \left\{1,...,m\right\}\right\}$ de $V$ telle que :

$\forall i\in \left\{1,...,m\right\},|V_{i}|=s_{i}$
$\forall i\in \left\{1,...,m\right\},G[V_{i}]$ est un graphe connexe.

L'ensemble $P(S)$ est alors dit être une partition de $G$ induite par $S$ .

Graphe partitionnable[modifier | modifier le code]

Un graphe $G=(V,E)$ est dit partitionnable s'il admet une $S$ -partition pour toute partition $S$ de $|V|$ .

Graphe $k$ -partitionnable[modifier | modifier le code]

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

Exemples[modifier | modifier le code]

$k$ -partition de $n$ [modifier | modifier le code]

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

Soit le graphe $G=(V,E)$ tel que :

$V=\left\{a,b,c,d,e,f\right\}$
$E=\left\{\left\{a,b\right\},\left\{b,c\right\},\left\{c,d\right\},\left\{d,e\right\},\left\{e,f\right\},\left\{f,a\right\},\left\{c,e\right\}\right\}$

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

↑ (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

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Graphe_partitionnable&oldid=190903840 ».

Concept en théorie des graphes

Catégories cachées :