Mathématiques et sciences humaines/Mathematics and social sciences

n° 179 Automne 2007

Version imprimable   Signaler cette page  

Maximum de la distance de transfert à une partition donnée

Maximum of the transfer distance to a given partition

Irène Charon, Lucile Denoeud et Olivier Hudry

Télécharger le texte intégral (511k)

Résumé

Dans cet article, on étudie une distance définie sur l'ensemble des partitions d'un ensemble fini. Étant données deux partitions P et Q, cette distance, appelée distance de transfert, correspond au nombre minimum de transferts d'un élément d'une classe dans une autre nécessaires pour transformer P en Q, ou réciproquement Q en P. On détermine le maximum de la distance de transfert entre une partition donnée et une partition quelconque, indépendamment du nombre de classes, puis le maximum de cette distance entre une partition donnée et une partition dont le nombre de classes est majoré.

Abstract

In this paper, we study a distance defined over the partitions of a finite set. Given two partitions P and Q, this distance, called the transfer distance, is defined as the minimum number of transfers of an element from one class to another, required to transform P into Q or equivalently Q in P. We give some formulae for the maximum distance value between a given partition and any partition, then the maximum distance value between a given partition and a partition with an upper-bounded number of classes.

Index

Pour citer cet article

Irène Charon, Lucile Denoeud et Olivier Hudry, « Maximum de la distance de transfert à une partition donnée », Mathématiques et sciences humaines, n° 179 Automne 2007, [En ligne], mis en ligne le 21 décembre 2007. URL : http://msh.revues.org/document7403.html. Consulté le 28 novembre 2009.

Irène  Charon

École Nationale Supérieure des Télécommunications (ENST), 46 rue Barrault 75634 Paris cedex 13, charon@infres.enst.fr

Lucile  Denoeud

École Nationale Supérieure des Télécommunications (ENST), 46 rue Barrault 75634 Paris cedex 13, denoeud@infres.enst.fr

Olivier  Hudry

École Nationale Supérieure des Télécommunications (ENST), 46, rue Barrault 75634 Paris cedex 13, hudry@infres.enst.fr


 
Page générée par Lodel - Nous adhérons à www.revues.org

ISSN : 0987 6936
Ecole des hautes études en sciences sociales