Problème pour thèse

[sherlock]

Bonjour,

Dans le cadre d'une thèse, je dois résoudre le problème suivant :

Soit N boules tel que le nombre N est compris entre [10 : 30] : (b1 , b2 , ... , bN).
On considère l'ensemble des couples que l'on peut former avec les B boules, soit CN2
(nombre de combinaisons de 2 boules parmis N --> pour 10 boules, 45 couples).
Je dois former un ensemble de groupes de boules de taille P (avec P inférieur ou égal à N-2) qui exclut
l'ensemble des couples.

L'objectif est de déterminer la taille minimale de cet ensemble ainsi qu'une méthode de construction.
(en évitant une méthode récursive type graphe)

Pour être plus clair, voici un exemple :
- N = 5
- P = 2
Comme N = 5, on a 10 couples.
P = 2, on forme donc des groupes de 2 boules.

Liste des couples : (b1,b2) (b1,b3) (b1,b4) (b1,b5) (b2,b3) (b2,b4) (b2,b5) (b3,b4) (b3,b5) (b4,b5)

Groupe 1 : (b1,b2) --> on exclut les couples (b3,b4) (b3,b5) (b4,b5)
Liste des couples restants à exclure: (b1,b2) (b1,b3) (b1,b4) (b1,b5) (b2,b3) (b2,b4) (b2,b5)

Groupe 2 : (b3,b4) --> on exclut les couples (b1,b2) (b1,b5) (b2,b5)
Liste des couples restants à exclure : (b1,b3) (b1,b4) (b2,b3) (b2,b4)

Groupe 3 : (b5,b4) --> on exclut les couples (b1,b3) (b2,b3)
Liste des couples restants à exclure : (b1,b4) (b2,b4)

Groupe 4 : (b3,b5) --> on exclut les couples (b1,b4) (b2,b4)
Liste des couples restants à exclure :

Dans ce cas de figure simple, il faut donc 4 groupes pour exclure l'ensemble des couples.


Pour ma part, les pistes que j'ai sont les suivantes :
- ordonnées les groupes (traitées les couples liés à la boule 1, puis 2...)
- favoriser les liens pour augmenter le nombre de couple par groupe
...
Pour travailler le mieux c'est la représentation matricielle sous Excel


Des idées ?
--> Nombre minimum pour N et P données
--> Méthode de construction
(est ce un problème classique?)

[leon1789]

Dans le cadre d'une thèse... en maths ?

[sherlock]

Dans le cadre d'une thèse... en maths ?

Pas en math (concernant la sécurité).
Surveillance de la sécurité de capteurs (supposant un certain nombre de pannes).

[Ben314]

Salut,
Je suis pas 100% certain d'avoir tout compris : quand tu va faire un groupe de P boules, ça va t'éliminer tout les couples dont aucun des deux éléments ne fait parti des P boues de ton groupe, c'est bien ça ?

Par exemple, si , tu fait 3 groupes de P disjoints et c'est bon, tu as éliminé tout le monde ?

[Ben314]

Si c'est bien ça, une première "vague" approximation dit que le nombre k de groupes de P boules qu'il te faudra pour éliminer tout les couples doit vérifier :

[sherlock]

Si c'est bien ça, une première "vague" approximation dit que le nombre k de groupes de P boules qu'il te faudra pour éliminer tout les couples doit vérifier :

Oui Ben314, les couples éliminés sont ceux dont les boules n'appartiennent pas au couple (quand le nombre P est petit, la solution est immédiate, quand il est grand ... se pose la question de l'optimalité et d'une méthode de construction).
Effectivement, ta formule doit correspond au rapport : Cn2 / Cnp
qui fournit un seuil du nombre de groupe.