View
104
Download
1
Category
Preview:
Citation preview
1
Enumération des cliques maximales d’un graphe,
des bicliques maximales d’un graphe biparti
LIMOS – Clermont-Ferrand
Alain Gély, Lhouari Nourine, Bachir Sadi
10 Novembre 2006
Journées Graphes & Algorithmes, Novembre 2006, Orléans
2
1. Définitions
2. Problématique de l’énumération
Mesure de Complexité
Méthodes d’énumération
3. Enumération des Cliques Maximales
Existant
Graphe des transitions des cliques maximales
Propriétés du graphe de Transitions
4. Enumération des Bicliques Maximales
Propriétés du graphe de transition
5. Conclusion
3
1. Définitions
2. Problématique de l’énumération
Mesure de Complexité
Méthodes d’énumération
3. Enumération des Cliques Maximales
Existant
Graphe des transitions des cliques maximales
Propriétés du graphe de Transitions
4. Enumération des Bicliques Maximales
Propriétés du graphe de transition
5. Conclusion
4G = ( V , E )
1
2 3
4
5
7
6
Clique Maximale
x,y C (x,y) E
Pour tout zC , C z n’est pas une clique
G = ( U, V , E )
DéfinitionsClique maximale, Biclique maximale
5G = ( V , E )
1
2 3
4
5
7
6
Clique Maximale
x,y C (x,y) E
Pour tout zC , C z n’est pas une clique
G = ( U, V , E )
1 23
45
67
Biclique Maximale
x,y B, x U, y V (x,y) E
Pour tout zB , B z n’est pas une biclique
DéfinitionsClique maximale, Biclique maximale
6
1. Définitions
2. Problématique de l’énumération
Mesure de Complexité
Méthodes d’énumération
3. Enumération des Cliques Maximales
Existant
Graphe des transitions des cliques maximales
Propriétés du graphe de Transitions
4. Enumération des Bicliques Maximales
Propriétés du graphe de transition
5. Conclusion
7
Algorithme d’EnumérationDéfinition
Entrée : S une structure discrète, P une propriété
Sortie : Liste des configurations de S satisfaisant P
S = un graphe G(V,E)
P = être une clique maximale de G
Sortie : Liste des cliques maximales de G
Taille de l’entrée : n
Taille de la sortie : N ( # Configurations )
8
1. Définitions
2. Problématique de l’énumération
Mesure de Complexité
Méthodes d’énumération
3. Enumération des Cliques Maximales
Existant
Graphe des transitions des cliques maximales
Propriétés du graphe de Transitions
4. Enumération des Bicliques Maximales
Propriétés du graphe de transition
5. Conclusion
9
Algorithme d’énumération
Polynomiale : O((n+N)k)
Complexité temporelle
Taille de l’entrée : n
Taille de la Sortie : N ( # configurations )
Polynomiale par objet : O(nk N)
A délai polynomial : O(nk N)
C1 C2 Ci Ci-1 CNDébut Fin
O(nk) O(nk) O(nk) O(nk)
Complexité Spatiale
Polynomiale : O(nk)
Exponentielle : O(nkN) ( stockage nécessaire au traitement)
10
1. Définitions
2. Problématique de l’énumération
Mesure de Complexité
Méthodes d’énumération
3. Enumération des Cliques Maximales
Existant
Graphe des transitions des cliques maximales
Propriétés du graphe de Transitions
4. Enumération des Bicliques Maximales
Propriétés du graphe de transition
5. Conclusion
11
Méthodes d’énumération
Enumération dans l’ordre lexicographique
(exemple : sous-ensembles de {1,2,3})
Trouver une première configuration C
Calculer Suivant(C)
Première configuration :
Suivant() : 1
Suivant(1) : 12
Suivant(12) : 123
Suivant(123) : 13
Suivant(13) : 2
Suivant(2) : 23
Suivant(23) : 3
12
Retour-Arrière
Choisir une propriété P
Enumérer les configurations qui vérifient P
Enumérer les configurations qui ne vérifient pas P
1, 12, 123 , 2, 23
Contenir 1 Ne pas contenir 1
Méthodes d’énumération(exemple : sous-ensembles de {1,2,3})
13
- Notion de proximité entre objets à générer
- Recherche d’un chemin Hamiltonien
1 2
12
3
13 23
123
Code de Gray (Gray 54)
Méthodes d’énumération(exemple : sous-ensembles de {1,2,3})
- « construction » d’un graphe de proximité
14
Méthode de Recherche Locale Inverse (Avis Fukuda 96)
- Fonction de voisinage
- Optimisation d’un critère
1
2
123 13
23
123
Méthodes d’énumération(exemple : sous-ensembles de {1,2,3})
- Inversion de la recherche
Ø
15
Dans tous les cas
Utilisation d’arbre / de graphe ayant pour sommet des objets à construire
Méthodes d’énumération
1 2
12
3
13 23
123
Ø
2
12
3
13 23
123
Ø Ø
1
12
2
23123
1
Code de Gray13
3
2
12
3
13 23
123
Ø
1
Retour-arrière( )Ø 1 12 123 13 2
Suivant( )
23 3
16
1. Définitions
2. Problématique de l’énumération
Mesure de Complexité
Méthodes d’énumération
3. Enumération des Cliques Maximales
Existant
Graphe des transitions des cliques maximales
Propriétés du graphe de Transitions
4. Enumération des Bicliques Maximales
Propriétés du graphe de transition
5. Conclusion
17
ExistantG = ( V , E )
{1,2,3}
{1,5}
{1,6}
{2,3,4}
{2,3,7}
{4,5}
{6,7}
C(G)
C(G) exponentielle
Algorithmes :
• Espace polynomial
• Délai polynomial
• Ordre lexicographique
Prochaine clique maximale lexicographique : NP-complet
1
2 3
4
5
7
6
[Tsukiyama & al 77][Johnson & al 88]
Enumération des cliques maximales
18
1. Définitions
2. Problématique de l’énumération
Mesure de Complexité
Méthodes d’énumération
3. Enumération des Cliques Maximales
Existant
Graphe des transitions des cliques maximales
Propriétés du graphe de Transitions
4. Enumération des Bicliques Maximales
Propriétés du graphe de transition
5. Conclusion
19
Enumération des cliques maximales
G = ( U , V )
{1,2,3}
{1,5}
{1,6}
{2,3,4}
{2,3,7}
{4,5}
{6,7}
C0
C1
C2
C3
C4
C5
C6
?
C(G)
Intuition
Définir un graphe de proximité
C(G) , Ensemble de sommets
T(G) = (C(G) ,T)
Graphe des transitions des cliques max de G
Reste à déterminerL’ensemble des transitions
1
2 3
4
5
7
6
20
Cx Cyj
Transition utilisant un sommet j de V
j n’appartient pas à Cx
j appartient à Cy
ensembledes arcs
Soit Kj( ), un opérateur sur une clique maximale
Transition ssi Cy = Kj( Cx ),
Enumération des cliques maximales
21
Kj( ) ?
1 2 3 4 j n
Voisinage de J
i
Est une clique
j n
Complétion (gloutonne) pour obtenir une clique maximale C
C est une clique maximale de G … ou non
Enumération des cliques maximales
22
j Cx, Kj(Cx) Plus petite clique max. de
{ Cx { 1, … , j } v(j) } { j , … , n}
Préfixe de Cx
Voisinage de j dans le préfixe de Cx
Labels supérieur à j
Kj( )
1
2 3
4
5
7
6
Enumération des cliques maximales
23
1. { 1,2,3} { 1,…,4 } = {1,2,3}2. V(4) = {2,3,5}3. {1,2,3} {2,3,5} = {2,3}4. Plus petite clique maximale de {2,3} {4,…,7}
K3({1,2,3}) = {2,3,4} C(G)
K4({1,2,3}) ?
1
2 3
4
5
7
6
{1,2,3} {2,3,4}4
Transition
1
2 3
4
5
7
6
Enumération des cliques maximales
24
1. { 1,6} { 1,2,3 } = {1}2. V(3) = {1,2,4,7}3. {1} {1,2,4,7} = {1}4. Plus petite clique maximale de {1 } {3,…,10}
K3({1,6}) = {1,3} C(G)
K3({1,6}) ?
1
2 3
4
5
7
6
{1,6} ?3
Pas de transition de label 3
1
2 3
4
5
7
6
Enumération des cliques maximales
25
T(G) Graphe des transitions de G
67
237
123
234
45
15
16
5
6
1
1
7
4
7
2
4
2
14
4
65
6
27
2
6
1
4
1
2 3
4
5
7
6
G(V,E)
26
1. Définitions
2. Problématique de l’énumération
Mesure de Complexité
Méthodes d’énumération
3. Enumération des Cliques Maximales
Existant
Graphe des transitions des cliques maximales
Propriétés du graphe de Transitions
4. Enumération des Bicliques Maximales
Propriétés du graphe de transition
5. Conclusion
27
Propriétés de T(G)
Idée de la preuve :
Soit C0 la plus petite clique maximale de G
• Il existe un chemin de C0 vers n’importe quelle Ci
• Il existe un chemin de Ci vers C0
C0 Ck ClCi Cj
T(G) est fortement connexe
28
T(G) Graphe de transitions de G
67
237
123
234
45
15
16
5
6
1
1
7
4
7
2
4
2
14
4
65
6
27
2
6
1
4
1
2 3
4
5
7
6
G(V,E)
29
1
12
123
123 234
123 15 234 45
123 16 15 16 234 6 45 6
123 237 16 67 15 7 16 7 234 237 45 7
1
2 3
4
5
7
6
1
2 3
4
5
7
6
1
2 3
4
5
7
6
1
2 3
4
5
6
7
1
2 3
4
5
6
7
1
2 3
4
5
6
7
1
2 3
4
5
7
6
T(G) : Chemin de C0 vers Ci
Induction structurelle
30
1
12
123
123 234
123 15 234 45
123 16 15 16 234 45
123 237 16 67 15 16 234 237 45
1
2 3
4
5
7
6
1
2 3
4
5
7
6
1
2 3
4
5
7
6
1
2 3
4
5
6
7
1
2 3
4
5
6
7
1
2 3
4
5
6
7
1
2 3
4
5
7
6
4
5
7
5
66
7 7
31
T(G)
67
237
123
234
45
15
16
5
6
1
1
7
4
7
2
4
2
14
4
65
6
27
2
6
1
4
1
2 3
4
5
7
6
G(V,E)
32
T(G)
67
237
123
234
45
15
16
5
6
1
1
7
4
7
2
4
2
14
4
65
6
27
2
6
1
4
1
2 3
4
5
7
6
G(V,E)
33
1
12
123
123 234
123 15 234 45
123 16 15 16 234 45
123 237 16 67 15 16 234 237 45
1
2 3
4
5
7
6
1
2 3
4
5
7
6
1
2 3
4
5
7
6
1
2 3
4
5
6
7
1
2 3
4
5
6
7
1
2 3
4
5
6
7
1
2 3
4
5
7
6
4
5
7
5
66
7 7
T(G) : plus de chemins de C0 vers Ci que de séquences de construction
34
Résultat :
T(G) possède plusieurs arbres couvrant
enracinés en C0
35
2 Etapes :
1. Choisir une arborescence T(G) (enracinée en C0)(plusieurs choix)
2. Parcourir l’arborescence recouvrante(plusieurs choix)
G(V,E) |V|=n, |E|=m
• Construction de C0 O(m)
• calcule des Transitions O(m)
• Tester la maximalité O(m)
• # transitions pour une clique max. O(n)
O(n.m)
1i
n
C0
T(G) Graphes de transitions de G – Algorithmes & Complexités
36
[ Tsukiyama & al. 77 ]
Graphe de transitions
Ordre quelconque – espace polynomial – Délai Polynomial
67
237
123
234
45
5
46
15 5
16
7
7
67237123 234 451516
Arbre couvrant :
• Chemins définis par des séquences de construction
• Choisir la plus petite séquence lexicographique
Parcours : En profondeur d’abord
37
[Johnson & al. 88]
Graphe de transitions
67
237
123
234
45
5
46
15 5
16
7
7
67237123 234 4515 16
Ordre lexicographique – espace exponentiel
Délai polynomial
Propriété de l’arbre couvrant de Tsukiyama :
• If Cx atteignable depuis Cy, alors Cy < Cx
Parcours : Stockage et reprise
123
15
16
234
237
67
45
38
1 2
3 4
5 6
7 8
1
3 5
827
46
Classes particulières - Graphes de Comparabilité
[Cai, Kong, 92]
Sommets numérotés selon une extension linéaire de l’ordre
Hypothèse
Ordre lexicographique – espace polynomial
Délai polynomial
39
1 2
3 4
5 6
7 8
1
3 5
827
46
La séquence des cliques maximales de G dans l’ordre lexicographique forment un
chemin Hamiltonien dans T(G)
Résultat
Classes particulières - Graphes de ComparabilitéOrdre lexicographique – espace polynomial
Délai polynomial
40
1. Définitions
2. Problématique de la génération
Mesure de Complexité
Méthodes de génération
3. Génération des Cliques Maximales
Existant
Graphe des transitions des cliques maximales
Propriétés du graphe de Transitions
4. Génération des Bicliques Maximales
Propriétés du graphe de transition
5. Conclusion
41
II. Enumération des bicliques maximales
G = (U,V,E)
2
3
1
5
6
7
8
42
1. Définitions
2. Problématique de la génération
Mesure de Complexité
Méthodes de génération
3. Génération des Cliques Maximales
Existant
Graphe des transitions des cliques maximales
Propriétés du graphe de Transitions
4. Génération des Bicliques Maximales
Propriétés du graphe de transition
5. Conclusion
43
Enumération des bicliques d’un graphe Biparti
Hypothèse de numérotations
Si i U , j V alors i < j
G = (U,V,E)
1 2 n
n+1 n+1 m
44
1
12
123
T(G) : chemin de C0 vers Ci avec des labels dans V (exclusivement)
1234
Sommets de U : clique
i
j Cliques max.
atteignables par une séquence sur V
Propriété
45
1 2 3 4 j ni
Sommets de U Sommets de V
j
i Cyi Cx
j VTransition => Cx ∩ V Cy ∩ V
Propriété
Enumération des bicliques d’un graphe Biparti
46
Propriétés du graphe de transitions
(123,78)
(13,578)
(1,5678)
(1234,8 )
5 6 7 8
1 2 3 4U
V
(12,678)
6 57
56
65
Treillis de Galois sous graphe de T(G)
Propriétés
Utiliser la structure de treillis = utiliser un sous graphe de T(G)
Propriété
47
Connexion entre algorithmes connus
[Tsukiyama & al. 77]
équivalent à un génération dans l’ordre lectique
Bicliques énumérables à partir de V seulement
Next-Closure [Ganter 84] et [Tsukiyama & al 77] énumèrent les bicliques maximales selon la même
séquence
Remarque
67
237
123
234
45
5
4
615 5
16
7
7
48
1. Définitions
2. Problématique de la génération
Mesure de Complexité
Méthodes de génération
3. Génération des Cliques Maximales
Existant
Graphe des transitions des cliques maximales
Propriétés du graphe de Transitions
4. Génération des Bicliques Maximales
Propriétés du graphe de transition
5. Conclusion
49
Conclusion
Mise en place d’un cadre général d’énumération
Comparaison d’algorithmes en utilisant T(G)
Adaptation à la génération des bicliques maximales
Algorithmes de génération des cliques et des bicliques
Propriétés supplémentaires de T(G) ?
Etudes de Classes de graphes particulières
Perspectives
50
Merci
Recommended