Équilibre, équivalence, ordre et préordre à distance minimum d'un graphe complet

G. Ribeill

Mathématiques et Sciences Humaines (1973)

  • Volume: 43, page 71-106
  • ISSN: 0987-6936

Abstract

top
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.

How to cite

top

Ribeill, G.. "Équilibre, équivalence, ordre et préordre à distance minimum d'un graphe complet." Mathématiques et Sciences Humaines 43 (1973): 71-106. <http://eudml.org/doc/94131>.

@article{Ribeill1973,
abstract = {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.},
author = {Ribeill, G.},
journal = {Mathématiques et Sciences Humaines},
language = {fre},
pages = {71-106},
publisher = {Ecole Pratique des hautes études, Centre de mathématique sociale et de statistique},
title = {Équilibre, équivalence, ordre et préordre à distance minimum d'un graphe complet},
url = {http://eudml.org/doc/94131},
volume = {43},
year = {1973},
}

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
PB - Ecole Pratique des hautes études, Centre de mathématique sociale et de statistique
VL - 43
SP - 71
EP - 106
AB - 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.
LA - fre
UR - http://eudml.org/doc/94131
ER -

References

top
  1. [1] Abelson, R., Rosenberg, M., « Symbolic psychologie : A model of attitudinal cognition », Behav. Sc., 3-1-13. 
  2. [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. 
  3. [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. Zbl0239.05122MR300927
  4. [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. [5] Flament, C., Théorie des graphes et structures sociales, Paris, Mouton et Gauthier-Villars, 1965. Zbl0169.26603MR221966
  6. [6] — « Équilibre d'un graphe, quelques résultats algébriques », Math. Sci. hum., n° 30, 1970. Zbl0222.05124
  7. [7] Harary, F., « On the notion of balance of a signed graph », Mich. math. Journal, 2. Zbl0056.42103MR67468
  8. [8] Harary, F., « On local balance and n-balance in signed graphs », Mich. math. Journal, 3. Zbl0070.18502MR73170
  9. [9] Harary, F., Norman, R.Z., Cartwright, C., Structural models : An introduction to the theory of directed graphs, New York, Wiley, 1965. Zbl0139.41503MR184874
  10. [10] Jacquet-Lagrèze, E., « Opinions valuées et graphes de préférence », Math. Sci. hum., n° 33, 1971. Zbl0224.92025MR300363
  11. [11] Kendall, M.G., Babington, Smith, B., « On the method of paired comparison » , Biometrika, 33, 1940, pp. 239-251. Zbl66.0651.01MR2761
  12. [12] Remage, R., Thompson, W.A., « Maximum likelihood paired comparison rankings », Biometrika, 53, 1966, pp. 143-149. Zbl0138.13207MR196854
  13. [13] Ribeill, C., « Recherche sur les graphes déséquilibrés », Metra International, Direction Scientifique, Note de Travail n° 166. 
  14. [14] Roy, B., Algèbre moderne et théorie des graphes, Paris, Dunod, vol. 2, chap. 10, 1969. Zbl0238.90072MR250927
  15. [15] Slater, P., « Inconsistencies in a schedule of paired comparisons », Biometrika, 48, 1961, pp. 303-312. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.