Vertex partitioning of a class of digraphs
Résumés
Un ensemble de sommets V' d'un graphe orienté G = (V,A) est un pseudo puits si son demi-degré extérieur est faible. La recherche d'un pseudo puits dans un graphe d'ordre élevé est un problème de forte complexité combinatoire. Nous montrons, sur une famille partitulière de graphes, que l'utilisation d'une classification hiérarchique des sommets, dont l'ensemble est muni d'une métrique bien choisie, permet la mise en évidence de pseudo puits par leur agrégation en 1er.
Entrées d’index
Mots-clés :
classification hiérarchique, dissimilarité, graphe de petits mondes, partitionnement d'un graphe orientéPour citer cet article
Référence électronique
Louis Ferre et Bertrand Jouve, « Vertex partitioning of a class of digraphs », Mathématiques et sciences humaines [En ligne], 158 | Été 2002, mis en ligne le 10 février 2006, consulté le 13 février 2026. URL : http://journals.openedition.org/msh/2857 ; DOI : https://doi.org/10.4000/msh.2857
Haut de pageDroits d’auteur
Le texte et les autres éléments (illustrations, fichiers annexes importés), sont « Tous droits réservés », sauf mention contraire.
Haut de page
