Discussion :

[luckyvae]

Bonjour tout le monde

Alors, je vous explique mon problème. J'ai un graphe et je cherche à obtenir des ensembles de nœuds E = {v_1, v_2, ..., v_n } tels que pour tout v_i de E, il y ait un arc vers chacun des autres v_j de E.

Jusque là, j'ai réussi à faire un algo qui fait ça. Le seul soucis, c'est que si j'ai l'ensemble {v_1, v_2, v_3, v_4}, mon algo me fournit également tout les sous-ensembles possibles à partir de cet ensemble (car ceux-ci répondent aussi à la définition). Or, ce que je voudrais, c'est avoir des ensembles tels qu'aucun ne soit un sous-ensemble d'un autre.

Voilà, je sais pas si vous voyez ce que je veux dire, et si oui, si vous voyez une méthode pour y arriver.

Voici l'algo que j'utilise pour l'instant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
//soit:
//*nbNodes le nombre de noeuds dans un graphe
//*c le nombre représentant un noeud (0 <= c < nbNode)
//*set l'ensemble des ensemble complètement liés
//alors:
//la procédure se charge de créer et d'ajouter à set les ensembles complètements
//lié utilisant les noeuds c jusque nbNodes-1
procedure createSets(int nbNodes, int c, Set<Set> set):
  if(c == nbNodes) {
    return;
  }
  for(int i = c + 1; i < nbNodes; i++) {
    if (linkBetween(c, i)) {
      Set e;
      e->add(c);
      e->add(i);
      fillSet(nbNodes, i + 1, e, set);
    }
  }
  createSets(nbNodes, c + 1, set);
}
 
//soit:
//*nbNodes le nombre de noeuds dans un graphe
//*c un nombre représentant un noeud
//*e un ensemble de noeuds tel qu'il existe un lien entre chacun de ses membres
//  pris deux à deux
//*sets un ensemble d'ensembles de noeuds complètements liés
//alors:
//la procédure se charge de créer des ensembles complètement liés qui utilisent
//les noeuds présents dans e. À ces ensembles ne seront ajoutés que des
//noeuds n tels que c<= n < nbNodes et d'ajouter ces ensembles dans sets
procedure fillSet(int nbNodes, int c, Set e, Set<Set>* sets) {
  for(int i = c ; i < nbNodes; i++) {
    bool ok = true;
    foreach( j in e ){
      ok = ok && linkBetween(j, i);
    }
    if(ok) {
      Set other = e->copy();
      tmp->add(i);
      fillSet(nbNodes, i, tmp, set);
    }
  }
 
  if(e->size() > 2) {
    sets->add(e);
  }
}

Voili voilà, si vous avez besoin de plus de précision, n'hésitez pas

edit:
je suis quasi persuadé que ce problème est NP complet, mais je me dit qu'il est jamais trop tard pour démontrer que P=NP, non?

PS: au passage, l'expression "complètement lié" n'a rien de rigoureux et je suppose qu'il doit y en avoir une officielle, et que peut-être à partir du nom exact, ce serait possible de trouver des pistes d'algos...

[Biribibi]

Bonjour,

Ton problème est de générer l'ensemble des cliques maximales d'un graphe.
Ce n'est pas un problème de décision donc parler de problème NP-complet n'a pas vraiment de sens.
Par contre, il y a potentiellement un nombre exponentiel de cliques maximales et du coup un algorithme pour ce problème sera forcément exponentiel.

Il y a des algorithmes pour générer les cliques maximales avec un délai polynomial entre chaque clique.
Voir par exemple:
On generating all maximal independent sets de David S. Johnson, Mihalis Yannakakis, Christos H. Papadimitriou

Pour ton algorithme, je regarderai plus tard dans le détail ce qu'il fait.

Pour un peu de lecture:
http://en.wikipedia.org/wiki/Clique_...aximal_cliques

[benDelphic]

D'aprés ce que j'ai compris il cherche un algorithme pour une couverture de graphe en cliques . Il cherche des ensembles disjoints ( d'où couverture ) de sous graphe ( d'après sa définition sont des cliques ).

[Biribibi]

Ha oui, en effet, je n'avais pas très bien lu le problème. Excusez moi.

Donc, si j'ai bien le problème de décision associé est:
existe-t-il une partition des sommets du graphe en cliques maximales ?

Je ne connais pas ce problème. Ca semble être NP-complet à vu de nez.
Il y a certains problèmes NP-complets qui y ressemblent un peu comme par exemple CLIQUE-COVER:
existe-t-il une partition des sommets du graphe en au plus k cliques ?

Je pense qu'on doit pouvoir réduire le premier problème au second.
J'essaierai d'y réfléchir un peu.