Tout d'abord quelques définitions pour comprendre mon problème :
Notre espace est discrétisé : M lignes, K collones.
toutes les courbes démarrent de (1,M) et finissent en (K,1) et sont toutes décroissante( a partir d'une case (x,y) on peut tracer soit en (x+1,y) (x+1,y-1) ou (x,y-1) ).
On dit qu'une courbe domine une autre courbe ssi elles est plus grande que la deuxième pour toutes valeurs de 1 a K.
Ma question :
Quel est le nombre de courbes non dominés maximum que l'on peut avoir dans un espace de taille MxK.
Exemple :
Si on a les 4 courbes suivante (rouge, verte bleu et jaune) les non dominé sont jaune est bleu, car la jaune domine la rouge et la verte, et la bleu domine la rouge et la verte mais la jaune ne domine pas la bleu de meme que la bleu ne domine pas la jaune.
Si on a les 2 courbes suivante (vert et rouge) les non dominées sont vert et rouge.
Si on a les 2 courbes suivantes (rouge et jaune) les non dominés sont la jaune.
Voila je sais pas si j'ai été assez clair, mais n'hésitez pas a me poser des questions si c'est pas le cas.
Merci encore.
P.S: Sur l'image de l'exemple si il y aplus sieurs couleur sur ne case c'est que plusieurs courbes passent par cette case.
