Discussion :

[SHILI1]

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]

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]

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]

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 ?

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 ?

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]

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]

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} ?