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...