Équilibre, équivalence, ordre et préordre à distance minimum d'un graphe complet
Ribeill, G.
Mathématiques et Sciences humaines, Tome 43 (1973), p. 71-106 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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},
     volume = {43},
     year = {1973},
     pages = {71-106},
     mrnumber = {371726},
     zbl = {0278.05107},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/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://gdmltest.u-ga.fr/item/MSH_1973__43__71_0/

[1] Abelson, R., Rosenberg, M., « Symbolic psychologie : A model of attitudinal cognition », Behav. Sc., 3-1-13.

[2] Barbut, M., « Note sur les ordres totaux à distance minimum d'une relation binaire donnée », Math. Sci. hum., n° 17, 1966, pp. 47-48. | Numdam

[3] Bermond, J.C., « Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux », Math. Sci. hum., n° 37, 1972, pp. 5-25. | Numdam | MR 300927 | Zbl 0239.05122

[4] Durand, B., « 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] Flament, C., Théorie des graphes et structures sociales, Paris, Mouton et Gauthier-Villars, 1965. | MR 221966 | Zbl 0169.26603

[6] - « Équilibre d'un graphe, quelques résultats algébriques », Math. Sci. hum., n° 30, 1970. | Numdam | Zbl 0222.05124

[7] Harary, F., « On the notion of balance of a signed graph », Mich. math. Journal, 2. | MR 67468 | Zbl 0056.42103

[8] Harary, F., « On local balance and n-balance in signed graphs », Mich. math. Journal, 3. | MR 73170 | Zbl 0070.18502

[9] Harary, F., Norman, R.Z., Cartwright, C., Structural models : An introduction to the theory of directed graphs, New York, Wiley, 1965. | MR 184874 | Zbl 0139.41503

[10] Jacquet-Lagrèze, E., « Opinions valuées et graphes de préférence », Math. Sci. hum., n° 33, 1971. | Numdam | MR 300363

[11] Kendall, M.G., Babington, Smith, B., « On the method of paired comparison » , Biometrika, 33, 1940, pp. 239-251. | MR 2761

[12] Remage, R., Thompson, W.A., « Maximum likelihood paired comparison rankings », Biometrika, 53, 1966, pp. 143-149. | MR 196854 | Zbl 0138.13207

[13] Ribeill, C., « Recherche sur les graphes déséquilibrés », Metra International, Direction Scientifique, Note de Travail n° 166.

[14] Roy, B., Algèbre moderne et théorie des graphes, Paris, Dunod, vol. 2, chap. 10, 1969. | MR 250927

[15] Slater, P., « Inconsistencies in a schedule of paired comparisons », Biometrika, 48, 1961, pp. 303-312.