Les problèmes que nous traitons ici sont en partie familiers aux lecteurs de la revue. L'apport original consiste selon nous dans le fait d'avoir rapproché des problèmes classiques (équilibre d'un graphe, ordre à distance minimum) pour en souligner les analogies profondes et, du coup, plonger de manière féconde ces problèmes dans un ensemble plus large, en particulier en posant le problème de l'équivalence et du préordre à distance minimum d'un graphe complet. Notre exposé se présente donc comme le développement en parallèle de quatre problèmes très apparentés. Pour souligner les analogies, nous avons parfois adopté une terminologie commune relativement à certains concepts. A partir de concepts relatifs à un sommet et de propriétés locales définies sur les sommets, nous avons ainsi construit un algorithme pour résoudre le problème de l'équilibre, de l'équivalence et de l'ordre à distance minimum d'un graphe complet, le cas du préordre pouvant être résolu par un algorithme semblable mais plus lourd. Enfin, pour terminer cette note, nous proposons une méthode heuristique générale qui s'applique indifféremment à n'importe lequel des quatre problèmes traités.
The problems which we treat in this paper are partly familiar to the reader of this journal. The originality of the contribution consists, according to us, in the fact that we have brought together classical problems (balance of a graph, ordering at minimal distance) in order to underline their profound analogies, and at the same time, to immerse the problems in a larger framework in a fruitful manner, particularly by posing the problem of equivalence and preordering at minimal distance of a complete graph. Our exposition is presented, therefore, as the parallel development of four very closely related problems. In order to bring out the analogies, we have at times adopted a common terminology with repect to certain concepts. Aside from concepts concerning a vertex and local properties defined on vertices, we have also constructed an algorithm to solve the problem of balance, equivalence and of the ordering at minimal distance of a complete graph. The case of preordering could be resolved by a similar but more ponderous algorithm. Finally, to end this note, we propose a general heuristic method which can be applied indifferently to each of the four treated problems.
@article{MSH_1973__43__71_0,
author = {Ribeill, G.},
title = {\'Equilibre, \'equivalence, ordre et pr\'eordre \`a distance minimum d'un graphe complet},
journal = {Math\'ematiques et sciences humaines},
pages = {71--106},
publisher = {Ecole Pratique des hautes \'etudes, Centre de math\'ematique sociale et de statistique},
volume = {43},
year = {1973},
mrnumber = {371726},
zbl = {0278.05107},
language = {fr},
url = {http://www.numdam.org/item/MSH_1973__43__71_0/}
}
TY - JOUR AU - Ribeill, G. TI - Équilibre, équivalence, ordre et préordre à distance minimum d'un graphe complet JO - Mathématiques et sciences humaines PY - 1973 SP - 71 EP - 106 VL - 43 PB - Ecole Pratique des hautes études, Centre de mathématique sociale et de statistique UR - http://www.numdam.org/item/MSH_1973__43__71_0/ LA - fr ID - MSH_1973__43__71_0 ER -
%0 Journal Article %A Ribeill, G. %T Équilibre, équivalence, ordre et préordre à distance minimum d'un graphe complet %J Mathématiques et sciences humaines %D 1973 %P 71-106 %V 43 %I Ecole Pratique des hautes études, Centre de mathématique sociale et de statistique %U http://www.numdam.org/item/MSH_1973__43__71_0/ %G fr %F MSH_1973__43__71_0
Ribeill, G. Équilibre, équivalence, ordre et préordre à distance minimum d'un graphe complet. Mathématiques et sciences humaines, Tome 43 (1973), pp. 71-106. http://www.numdam.org/item/MSH_1973__43__71_0/
[1] , , « Symbolic psychologie : A model of attitudinal cognition », Behav. Sc., 3-1-13.
[2] , « Note sur les ordres totaux à distance minimum d'une relation binaire donnée », Math. Sci. hum., n° 17, 1966, pp. 47-48. | Numdam
[3] , « Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux », Math. Sci. hum., n° 37, 1972, pp. 5-25. | Numdam | MR | Zbl
[4] , « A propos des problèmes du nombre minimum d'arcs à évaluer pour supprimer les circuits d'un graphe », Math. Sci. hum., n° 20, 1967, pp. 61-68.
[5] , Théorie des graphes et structures sociales, Paris, Mouton et Gauthier-Villars, 1965. | MR | Zbl
[6] - « Équilibre d'un graphe, quelques résultats algébriques », Math. Sci. hum., n° 30, 1970. | Numdam | Zbl
[7] , « On the notion of balance of a signed graph », Mich. math. Journal, 2. | MR | Zbl
[8] , « On local balance and n-balance in signed graphs », Mich. math. Journal, 3. | MR | Zbl
[9] , , , Structural models : An introduction to the theory of directed graphs, New York, Wiley, 1965. | MR | Zbl
[10] , « Opinions valuées et graphes de préférence », Math. Sci. hum., n° 33, 1971. | Numdam | MR
[11] , , , « On the method of paired comparison » , Biometrika, 33, 1940, pp. 239-251. | MR
[12] , , « Maximum likelihood paired comparison rankings », Biometrika, 53, 1966, pp. 143-149. | MR | Zbl
[13] , « Recherche sur les graphes déséquilibrés », Metra International, Direction Scientifique, Note de Travail n° 166.
[14] , Algèbre moderne et théorie des graphes, Paris, Dunod, vol. 2, chap. 10, 1969. | MR
[15] , « Inconsistencies in a schedule of paired comparisons », Biometrika, 48, 1961, pp. 303-312.
