Jeudi 18 mai 2006, à 14h15.
Orateur : Lucile Denoeud.
Titre : Maximum de la distance de transfert entre deux partitions.
Transparents.
Résumé :
La distance de transfert est définie sur l'ensemble des partitions d'un
ensemble fini X. Etant données deux partitions P et Q sur X, cette
distance correspond au nombre minimum de transferts d'un élément d'une
classe dans une autre (éventuellement vide) nécessaires pour transformer
P en Q, ou réciproquement Q en P.
Cette distance fut tout d'abord introduite par S. Régnier en 1965 puis
étudiée par Day (1981) qui montra que son calcul revient à la résolution
d'un problème de couplage maximum de poids minimum dans un graphe biparti.
Cette distance présente l'inconvénient de ne pas être normalisée. C'est
en partie dans ce but que nous avons déterminé les valeurs extrémales de
la distance de transfert sur différents ensembles de partitions.
Il est trivial de trouver le maximum d_max de la distance de transfert
entre deux partitions quelconques de X : d_max = |X|-1 (c'est la
distance entre la partition à une classe et la partition à |X| classes).
Nous avons tout d'abord déterminé la distance maximum entre deux
partitions dont les nombres de classes sont donnés ou majorés. Nous
avons ensuite poursuivi cette étude en établissant le maximum de la
distance de transfert à une partition P donnée et le maximum de la
distance de transfert entre une partition P donnée et une partition dont
le nombre de classes est donné ou majoré.
Nous présenterons ces résultats ainsi qu'une partie de leurs preuves.