Version imprimable
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 .
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 ...
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
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 ?Citation:
Envoyé par SHILI1
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 ?Citation:
Envoyé par SHILI1
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 :Citation:
Envoyé par SHILI1
http://i48.tinypic.com/yc3uc.png
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 ...
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
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} ?
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
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.
salut .. SVP j'ai besoin de l'implementation de l'algorithme de Born-Kerbosh en C ou C++ .. et merci d'avance
https://gist.github.com/gaoyuan/5042022
mais je n'ai pas du tout checké le code ni testé (j'adore poster des liens sans les regarder :mrgreen:)
merci beaucoup :mrgreen: .. est ce qu'il y a une implementation avec listes chainées ? le input sera une fichier texte qui contient les arrêtes !
Une fois que tu l'auras programmé, il y en aura une :mrgreen: