En théorie des graphes , un graphe partitionnable [ 1] , [ 2] est un type particulier de graphe .
Définitions
Partition d'un entier
Soit
n
{\displaystyle n}
un entier strictement positif, une partition de
n
{\displaystyle n}
est une suite d’entiers
(
s
1
,
…
,
s
m
)
{\displaystyle (s_{1},\ldots ,s_{m})}
telle que :
m
≥
1
{\displaystyle m\geq 1}
∀
i
∈
{
1
,
.
.
.
,
m
}
,
s
i
>
0
{\displaystyle \forall i\in \left\{1,...,m\right\},s_{i}>0}
s
1
+
…
+
s
m
=
n
{\displaystyle s_{1}+\ldots +s_{m}=n}
k
{\displaystyle k}
-partition d'un entier
Une
k
{\displaystyle k}
-partition de
n
{\displaystyle n}
est une partition de
n
{\displaystyle n}
possédant
k
{\displaystyle k}
éléments.
S
{\displaystyle S}
-partition d'un graphe
Soit
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
un graphe simple où :
V
{\displaystyle V}
est l'ensemble non vide des sommets de G.
E
{\displaystyle 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
{\displaystyle V}
.
Soit
S
=
(
s
1
,
…
,
s
m
)
{\displaystyle S=(s_{1},\ldots ,s_{m})}
une partition de
|
V
|
{\displaystyle |V|}
(le nombre de sommets du graphe G).
G
{\displaystyle G}
est dit admettre une
S
{\displaystyle S}
-partition s'il existe une partition
P
(
S
)
=
{
V
i
:
i
∈
{
1
,
.
.
.
,
m
}
}
{\displaystyle P(S)=\left\{V_{i}:i\in \left\{1,...,m\right\}\right\}}
de
V
{\displaystyle V}
telle que :
∀
i
∈
{
1
,
.
.
.
,
m
}
,
|
V
i
|
=
s
i
{\displaystyle \forall i\in \left\{1,...,m\right\},|V_{i}|=s_{i}}
∀
i
∈
{
1
,
.
.
.
,
m
}
,
G
[
V
i
]
{\displaystyle \forall i\in \left\{1,...,m\right\},G[V_{i}]}
est un graphe connexe.
L'ensemble
P
(
S
)
{\displaystyle P(S)}
est alors dit être une partition de
G
{\displaystyle G}
induite par
S
{\displaystyle S}
.
Graphe partitionnable
Un graphe
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
est dit partitionnable s'il admet une
S
{\displaystyle S}
-partition pour toute partition
S
{\displaystyle S}
de
|
V
|
{\displaystyle |V|}
.
Graphe
k
{\displaystyle k}
-partitionnable
Un graphe
G
{\displaystyle G}
est dit
k
{\displaystyle k}
-partitionnable s'il admet une
S
{\displaystyle S}
-partition pour toute
k
{\displaystyle k}
-partition
S
{\displaystyle S}
de
|
V
|
{\displaystyle |V|}
.
Exemples
k
{\displaystyle k}
-partition de
n
{\displaystyle n}
Une
2
{\displaystyle 2}
-partition de
5
{\displaystyle 5}
est
(
3
,
2
)
{\displaystyle (3,2)}
.
Une
4
{\displaystyle 4}
-partition de
10
{\displaystyle 10}
est
(
1
,
4
,
1
,
4
)
{\displaystyle (1,4,1,4)}
.
Une
7
{\displaystyle 7}
-partition de
22
{\displaystyle 22}
est
(
2
,
2
,
3
,
1
,
3
,
8
,
3
)
{\displaystyle (2,2,3,1,3,8,3)}
.
S
{\displaystyle S}
-partition de
G
{\displaystyle G}
Soit le graphe
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
tel que :
V
=
{
a
,
b
,
c
,
d
,
e
,
f
}
{\displaystyle V=\left\{a,b,c,d,e,f\right\}}
E
=
{
{
a
,
b
}
,
{
b
,
c
}
,
{
c
,
d
}
,
{
d
,
e
}
,
{
e
,
f
}
,
{
f
,
a
}
,
{
c
,
e
}
}
{\displaystyle 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
{\displaystyle |V|=6}
.
G
{\displaystyle G}
admet 3 partitions de 6 possibles :
(
1
,
1
,
4
)
{\displaystyle (1,1,4)}
,
(
1
,
2
,
3
)
{\displaystyle (1,2,3)}
et
(
2
,
2
,
2
)
{\displaystyle (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
{\displaystyle 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 ) .