Upload
claudie-xx
View
111
Download
4
Embed Size (px)
Citation preview
Coloration gap sommet identifiante de graphes
12èmes journée Journées Graphes et Algorithmes (JGA’10), Marseille France.
Mohammed Amin TahraouiEric DuchêneHamamache Kheddouci
Université de Lyon 1
Plan
Coloration de graphe
Coloration arêtes
Étiquetage des sommets
Coloration sommet identifiante
Définition
Variantes du problème
Coloration Gap sommet-identifiante
Formalisation
Résultats
Perspectives
2
Colorations de graphe Coloration arêtes
Affecter à toutes les arêtes de graphe G=(V,E) une couleur de telle
sorte que deux arêtes adjacentes n’aient jamais la même couleur.
c :E {0,1,…,k-1}
’ (G) : Le nombre minimum de couleurs à utiliser pour
obtenir une coloration arête.
Théorème de Vizing’s : Δ ≤ ’ (G) ≤ Δ +1
12
(G) =3
3
1
2
3
3
Colorations de graphe Etiquetage des sommets
Sommet-identifiante (Vertex-distinguishing ) L’étiquetage des sommets est appelé sommet-identifiant si chaque
sommet de G est déterminé uniquement par son étiquette.
Sommet adjacent -identifiante (Adjacent vertex-distinguishing )L’étiquetage des sommets est appelé sommet adjacent-identifiant si deux sommets adjacents ne portent pas la même couleur.
Une coloration des arêtes peut induire une coloration sommet-identifiante ou une coloration sommet adjacent -identifiante
Coloration Sommet-Identifiante (Vertex-Distinguishing Edge Colorings)
4
Coloration sommet-identifianteDéfinition
Irregular weighting(Chartrand et al ,86)
1
2 2
3
3
2
6
32
3
5
8
610
7
9
5
Coloration des arêtes qui permette de distinguer
via une fonction de codage c
propreimpropre Tous Les sommets
Sommets adjacentsSommeUnion setUnion multi-set
vertex-distinguishing edge-colorings (Burris & Schelp, 97)
{1,2}
{2,4}{1,4}
{1,5}
{1,2,3}{1,3}1
2 2
4
3
1
5
31 {3,5}
ev
efvc )()(
ev
efvc
)()(
Coloration sommet-identifiante Variantes de problème
Propre impropre Tous Les sommets
Sommets adjacents
Sum Set Multi-set Reference
Irregular weighting
x x x Chartrand et al ,86
vertex-colouring edge-weighting
x x x Karonski et al, 04
VD-coloring x x x Burris & Schelp, 97
Adjacent strong edge coloring
x x x Zhang et al ,02
point distinguishing edge-coloring
x x x Harary & Pltholtan,85
detectablecoloring
x x x Chartrand et al ,06
vertex-colouring edge-partition
x x x Addario-Berry et al 04
General neighbour-distinguishing
x x x Ervin et al, 05
Coloration arête Identifiante Fonction de codage
Coloration Gap sommet-identifianteDéfinition
via une fonction de codage c. Somme Union setUnion multi-set
7
Gap
Coloration des arêtes qui permette de distinguer properNon proper Tous Les sommets
Sommets adjacents
Coloration Gap sommet-identifiante Formalisation
Définition 1 Soit un graphe G=(V, E)Soit f : E → {1,……k} Pour chaque sommet v de G :
7
1 2
9
6
2
2
32
109
10
6 5
7
4
0
1
8
Max
Min
Nombre chromatique gap (G): Le plus petit k tel que G admette une
coloration Gap-sommet-identifiante
Max f(e) v ∈ e - Min f(e) v ∈ e si d(v)>1
f(e) si d(v)=1 c(v)=
Coloration Gap sommet-identifiante Résultats
Bornes inférieures
Théorème 1 Soit G un graphe de n sommets tel que G ne contient aucune composante isomorphe à K1 ou K2
gap(G) ≥ n si (i) δ(G) ≥ 2 ou (ii) Tout sommet de degré au moins égale à 2 possède au moins deux sommets adjacents de degré 1 gap (G) ≥ n − 1 Sinon
4
1
2
3
5
0
1
02
3
2
4
41
1
30
3
3
234
1
32
1
5
5
Bornes supérieures
Conjecture: Pour tout graph connexe G d’ordre n>2 gap(G) ≤ n+1
Coloration Gap sommet-identifiante Résultats
Graphe de degré minimum δ (G) ≥ 2
Théorème 2 (Résultat principal)
Pour tout graphe k-arête-connexe d’ordre n tel que k ≥ 2,
gap(G) = n, si G n’est pas un cycle de longueur =2, 3(mod 4) (a)
gap(G) = n+1 sinon (b)
Coloration Gap sommet-identifiante Résultats
Théorème 3 :
gap(Cn) = n, si n=0, 1(mod 4) (a)
gap(Cn) = n+1 si n=2, 3(mod 4) (b)
Cycle
Coloration Gap sommet-identifiante Résultats
Coloration Gap sommet-identifiante
(a) : gap(Cn) = n Si n=0, 1(mod 4)
gap(Cn) ≥ n gap(Cn) ≤ n ? ? ?
Case (a).1 : n mod 4 =0
n/2 i mod 4=2f(ei) =
(i+1)/2 i impaire
n i mod 4=0
c(vi) =
n-(i+1)/2 i mod 4=1
(n-i)/2 i mod 4=2(n –i-1)/2 i mod 4=3
n-(i/2) i mod 4=0
f(e1)=1
2
4
8
3
4
4
8
7 3
2
6
51
4
0
gapCn) ≤ n ?
Case a.2 : n mod 4 =1
n-1 i mod 4=2f(ei) =
i i paire
n i mod 4=0
f(e1)=1
8
3
9
58
8
7
9
7
5
6
4
3
0
1
2
8
gap(Cn) =n
c(vi) =
n-1 i mod 4=2
n-i+1 i mod 4=0
n –i-1 i mod 4=3
n-i i mod 4=1
Coloration Gap sommet-identifiante
(a) : gap(Cn) = n Si n=0, 1(mod 4)
gap(Cn) > n ? ? ?
Chaque terme f(ei) apparaît deux fois avec le même signe (ou par deux signes différents)
Contradiction !!!!(n (n-1)/2 est impaire Si n=2, 3(mod 4) )
gap(Cn) > n
Coloration Gap sommet-identifiante
(b) : gap(Cn) = n+1 Si n=2, 3(mod 4)
o gap(Cn) ≥ n+1
o gap(Cn) ≤ n+1 ? ? ?
Case (b).1 : n mod 4 =3
n+1 mod 4= 0 (gap(Cn+1) = n+1)
Cn+1 doit contenir deux bords successifs de mêmes couleurs.
8
6
5
gap(Cn) = n+1
1
2
4
3
4
4
8
7 3
2
1
4
0
Coloration Gap sommet-identifiante
(b) : gap(Cn) = n+1 Si n=2, 3(mod 4)
4
gap(Cn) ≤ n+1 ?
Case (b).2 : n mod 4 =2
f(en)= f(en-1)=2, f(en-2)=3 et
1 i mod 4=2Pour 1≤ i ≤ n-3, f(ei) =
n+2-i i paire
2 i mod 4=0
f(e1)=7
1
52
2
6
4
21
0
5
gap(Cn) =n+1
Coloration Gap sommet-identifiante
(a) : gap(Cn) = n+1 Si n=2, 3(mod 4)
3
Coloration Gap sommet-identifiante Résultats
Coloration arête équilibrée
Définition 2Pour chaque sommet v de G=(V, E):
Soit un intervalle I(v)=[Min f(e) v ∈ e , Max f(e) v ∈ e ] Une coloration arête f de G est une coloration équilibrée si seulement si : Pour toute pair u,v de V : I(u) ∩ I(v)≠ Ø
I(v1)=[1,6]
v1
5
3
1
6
5
v2
v3
v4
I(v1) ∩ I(v2) ∩ I(v3) ∩ I(v4) ={5}
Coloration Gap sommet-identifiante Résultats
Théorème 4 :Soit G un graphe avec δ(G) ≥ 2. 1.S'il existe un sous-graphe couvrant H de G tel que δ(H) ≥2 2.S’il existe une coloration arête équilibrée de H tel que gap(H) ≤ k.
gap(G) ≤ k.
Preuve gap(H) ≤ k. Pour toute (u,v) de V:
c(u)≠c(v) et f : coloration équilibrée : x∈ I(u) ∩ I(v)
Pour toute (u,v) ∈ E(G)/E(H), f(e)=x,
gap(G) ≤ k.
3
0
2
2
4
2
1
2
I(v1) ∩ I(v2) ∩ I(v3) ∩ I(v4) ={2}
2
Théorème 5Pour tout graphe 2-arête-connexe G d’ordre n tel que G n’est pas un cycle de longueur =2, 3(mod 4), nous avons
gap(G) = n
Idée de preuve Proposer une coloration arête équilibrée d’un sous-graphe couvrant G’ de G.
Algorithme Polynomial
Coloration Gap sommet-identifiante Résultats
Notations
Au cours de l'algorithme:
Soit Sc l’ensemble courant des sommets codés .
Initialement Sc= Ø.
Un sommet v est inséré dans Sc si et seulement si il est incident à au
moins deux arêtes colorées (e1,e2). On fixe c(v) à |f(e1)-f(e2)|.
Coloration Gap sommet-identifiante Résultats
1
8
7
Sc
N(Sc)
P(u)
vu
Notations
Une fonction N(Sc) retourne l'ensemble des sommets voisins de Sc et
non encore inclus dans l’ensemble Sc.
Pour chaque sommet u de N(Sc), soit la fonction P(u) qui renvoie une
chaine entre deux sommets de Sc qui passe forcément par le sommet u.
Coloration Gap sommet-identifiante Résultats
Algorithme
Input: un graphe 2-arête-connexe G = (V, E) d'ordre n, différent d'un cycle
de longueur 1, 2 ou 3 (mod 4).
Output: une coloration gap sommet-identifiante de G avec n couleurs.
Coloration Gap sommet-identifiante Résultats
Etape 1: Prendre un sous-graphe H de G tel que H est isomorphe à :
Cycle de longueur multiple de 4.
Deux cycles distincts ayant au moins un sommet commun.
Observation
Par hypothése, si G est différent d'un cycle de longueur multiple de 4, Alors Δ(G) ≥3 , le sous-graphe H peut être toujours
obtenu à partir de G.
Coloration Gap sommet-identifiante Résultats
Etape 2: Coloration de sous-graphe H (10 fonctions de coloration)
Par exemple : H est un cycle de longueur multiple de 4
Sc=V(H)
1 i mod 4=2f(ei) =
n-i+1 i impaire
2 i mod 4=0
1
8
7
2
6
6
5
4
Coloration Gap sommet-identifiante Résultats
Principe1. Pour tout sommet v de H : 2 I(v)∈2. Pour toute paire de sommets (u,v) de H, c(u)≠c(v)
Etape 3: Choisir un sommet u ∈N(Sc),
Soit une chaine R=P(u) d’ordre k
Quatre fonctions sont proposées pour la la coloration arête de R selon la valeur k mod
4=0,1,2,3.
Sc= Sc U V(R)
Si |Sc|<|V|
1
8
7
2
6
6
5
4
u5
2
3
Coloration Gap sommet-identifiante Résultats
Principe1. Pour tout sommet v de Sc : 2 I(v)∈2. Pour toute paire de sommets (u,v) de Sc, c(u)≠c(v)
Etape 3: Choisir un sommet u ∈N(Sc),
Soit une chaine R=P(u) d’ordre k
Quatre fonctions sont proposées pour la la coloration arête de R selon la
valeur k mod 4=0,1,2,3.
Sc= Sc U V(R)
1
8
7
2
6
6
5
4
u
Principe1. Pour tout sommet v de Sc : 2 I(v)∈2. Pour toute paire de sommets (u,v) de Sc, c(u)≠c(v)
5
2
3
5
32
2 2
1
0
Coloration Gap sommet-identifiante Résultats
Etape 4:
Pour chaque sommet v de G : 2 I(v)∈
Pour toute paire de sommets (u,v) de G, c(u)≠c(v)
Pour chaque arête non-colorée: f(e) =2
Fin de l’algorithme
gap(G)=n.
1
8
7
2
6
6
5
4
5
2
3
5
32
2 2
1
0
2
2
Coloration Gap sommet-identifiante Résultats
Corollaire 6Pour tout graphe k-arête-connexe d’ordre n tel que k>2, nous avons gap(G)=n
Coloration Gap sommet-identifiante Résultats
Pour tout entier k>2, tout graphe k-arête-connexe contient un sous-
graphe 2-arête connexe couvrant G’ différent d'un cycle.
Selon l’algorithme précédent, G’ admet une coloration Gap sommet
identifiante équilibrée
Coloration Gap sommet-identifiante Résultats
Nous pouvons maintenant conclure que le résultat du Théorème 2 est
une conséquence directe du Théorème 3 et le Corollaire 6.
Théorème 2 (Résultat principal)
Pour tout graphe k-arête-connexe d’ordre n tel que k ≥ 2,
gap(G) = n, si G n’est pas un cycle de longueur =2, 3(mod 4) (a)
gap(G) = n+1 sinon (b)
Coloration Gap sommet-identifiante Résultats
Graphe de degré minimum δ (G) = 1
Théorème 7 :
gap(Pn) = n, si n=2, 3(mod 4) (a)
gap(Pn) = n-1 si n=0, 1(mod 4) (b)
Coloration Gap sommet-identifiante Résultats
Théorème 8 Pour tout arbre binaire complet BT d’ordre n > 3, nous avons
gap(BT) = n − 1.
Théorème 9Soit T un arbre de n sommets tel que T a au moins deux feuilles à une distance égale à 2, nous avons
gap(T) ≤ n.
Graphe de degré minimum δ (G) = 1
Coloration Gap sommet-identifiante Perspective
Conjecture 2 (Graphe de degré minimum δ (G) ≥ 2)
Pour tout graphe G d’ordre n avec un degré minimum δ (G) ≥ 2,
gap(G) = n, si G n’est pas un cycle de longueur =2, 3(mod 4) (a)
gap(G) = n+1 sinon (b)
Conjecture 3 (Arbre)
Pour tout arbre T d’ordre n ≥ 3,
gap(T) = n, si la condition (ii) du Théorème 1 est remplie (a)
gap(T) = n-1 sinon (b)
34
Merci pour votre Merci pour votre attentionattention