extraire un clique a partir d'une matrice d'adjacence

**SHILI1** · 15/04/2013, 19h50

salut a tout,
y a il quelqu'un qui a une idée sur l'extraction des cliques(sous graphe complet) a partir d'une matrice d'adjacence d'un graphe.
bref je veux extraire le sous matrice correspondant a ce clique pour faire des traitement a part
je n'a pas abouti a aucune idée qui me permette de résoudre ce truc .

**kwariz** · 15/04/2013, 20h54

Bonsoir,

tu veux quoi exactement ? Lister toutes les cliques maximales ou maximum, toutes les cliques de plus k noeuds ?
Tu peux t'inspirer des liens fournis par wikipedia par exemple ...

**SHILI1** · 16/04/2013, 01h49

je veux et a partir d'une matrice d'adjacence d'un graphe donné,extraire tous les cliques de différents taille.
je veux une idée pas un lien vers un cours
exple:
je veux extraire le sous matrice comme dessous
0 1 1 0 1 1
1 0 1 1 0 1
1 1 0 1 1 1
0 1 1 0 1 1
1 0 1 1 0 1
1 1 1 1 1 0
===> comment extraire cette matrice
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

merci pour tout

**kwariz** · 16/04/2013, 02h34

Envoyé par SHILI1

je veux et a partir d'une matrice d'adjacence d'un graphe donné,extraire tous les cliques de différents taille.

Si tu veux toutes les cliques tu auras du coup toutes les paires de sommets liés par une arrête ... est-ce bien ce que tu veux, je ne pense pas ?

Envoyé par SHILI1

je veux une idée pas un lien vers un cours

Un lien vers une page wikipedia n'est pas un lien vers un cours ... même si c'est aussi dans les cours qu'on apprends à avoir des idées. Où ailleurs peux-tu trouver un algorithme qui te donne une liste de clique ?

Envoyé par SHILI1

exple:
je veux extraire le sous matrice comme dessous
0 1 1 0 1 1
1 0 1 1 0 1
1 1 0 1 1 1
0 1 1 0 1 1
1 0 1 1 0 1
1 1 1 1 1 0
===> comment extraire cette matrice
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

merci pour tout

En numérotant les sommets de 0 à 5 je suppose que ta matrice décrit le graphe suivant, avec la clique qui est en rouge pour la matrice extraite :

qui est donc une clique maximum. Comme indiqué sur wikipedia, c'est un problème NP difficile. D'après wikipedia un bon point de départ serait d'utiliser l'algorithme de Bron-Kerbosch et de ne garder que la plus grande des cliques maximales. Cependant si on creuse un minimum on trouve d'autres références et même des implémentations en c++ ... le bonheur non ? enfin quand on cherche ...

**SHILI1** · 16/04/2013, 12h54

merci pour votre aide.
mais je cherche a parcourir la matrice d'adjacence d'un graphe,extraire les cliques l'un après l'autre sans contrainte sur le taille de clique.
je peux détecter un clique de taille 3,faire un traitement appart puis je détecte un clique de taille 5

**kwariz** · 16/04/2013, 13h25

Donc si on reprend ton exemple avec mes labels tu cherches non seulement à trouver la clique {0,2,4,5} mais aussi toutes ses sous cliques {0,2},{0,4},{0,5},{2,4},{2,5},{4,5},{0,2,4},{0,2,5},{2,4,5} ?

**SHILI1** · 17/04/2013, 00h15

je veux parcourir le matrice extraire un clique puis la supprimer avec ses sommets puis retours a la matrice et faire le même traitement jusqu’à éliminer tous les cliques

**kwariz** · 17/04/2013, 03h15

Ce n'est toujours pas clair pour moi ce que tu veux réellement faire, néanmoins si tu veux à partir d'un graphe extraire une clique maximum puis recommencer jusqu'à obtenir un graphe vide le plus simple est de t'inspirer du source MaxCliqueDyn dont je t'ai déjà donné le lien dans un post précédent. Ou sinon implémenter la version simple de l'algorithme de Bron-Kerbosch en ne gardant que la plus grande des solutions.