1This paper aims to identify the problems that arise when a transportation network has to be represented by one - or several - parameter(s). A short review of the literature leads to the conclusion that at present there is no single and unambiguous criterion with which to distinguish two graphs that are topologically distinct. Perspectives are discussed regarding the effects of the shape of the communication network on the results of an optimal location model.

Introduction

2Le modèle de la k-médiane vise à déterminer les localisations et les affectations qui minimisent la désutilité des déplacements entre la demande pour un bien (ou service) et l'offre correspondante. Bureaux de Poste, services d'urgence, services récréatifs sont autant d'exemples qui font des modèles de localisation-affectation un outil opérationnel d'aide à la décision. Dans la pratique, le milieu géographique est représenté par un ensemble de points qui symbolisent la demande et les sites potentiels d'offre; les déplacements de la demande vers l'offre (ou inversement) s'effectuent le long d'un réseau de transport représenté par des liens entre les noeuds. Les résultats de la résolution d'un problème tel que la k-médiane sont donc dépendants des caractéristiques du réseau de transport et notamment de la quantité de routes disponibles et de l'organisation spatiale de celles-ci.

3La forme du réseau de communication modifie les localisations et l'efficacité du système spatial mais aussi la répartition de la demande entre les k facilités, la taille des aires de marché et l'équité entre les demandeurs : Peeters et Thomas le démontrent de façon exploratoire en 1995 en introduisant des modifications de la forme d'un réseau théorique sur un lattis quadrangulaire de points, et en 1996 (Arnold, Peeters et Thomas) sur un lattis hexagonal. Leurs résultats indiquent que, même indépendamment de la connexité du réseau, la structure géographique du réseau exerce une nette influence sur divers aspects de la localisation d'une offre et l'affectation de la demande à cette offre. Les distances entre offre et demande, en termes d'efficacité et d'équité, ainsi que les localisations de l'offre et les aires de marché diffèrent selon la configuration spatiale du réseau. Empiriquement, Oppong (1996) montre dans quelle mesure les résultats optimaux dépendent du type de réseau, selon que l'étude de localisation optimale est conduite en saison sèche (réseau dense) ou en saison des pluies (communications malaisées).

4Mesurer l'effet de la forme du réseau de communication sur les résultats de la k-médiane signifie maîtriser les nombreux éléments caractérisant le réseau. L'objectif du présent article est de poser succinctement les problèmes que soulèvent actuellement encore la caractérisation de la forme d'un réseau par un - ou plusieurs - paramètre(s).

De la théorie des graphes à la géomorphométrie

5Soit un réseau de communication représenté par un graphe simple connexe valué, où e est le nombre d'arêtes et n et le nombre de sommets. Puisqu'une localisation optimale peut toujours être trouvée sur un noeud du réseau (Hakimi, 1964), ce dernier peut être représenté par un graphe connexe dont les noeuds sont à la fois les points de demande et les points d'offre potentiels, et dont les arêtes sont les routes du réseau de transport, les plus courts chemins entre points. A l'exclusion des cas triviaux de très petits réseaux, il existe généralement un très grand nombre de formes spatiales différentes susceptibles de relier les n points de demande aux k points d'offre de manière connexe (Read, 1979, p 409). Afin de mieux comprendre comment les résultats de la k-médiane peuvent dépendre des caractéristiques spatiales du réseau, il convient de contrôler le plus grand nombre possible de caractéristiques du réseau pour pouvoir examiner l'effet d'un petit nombre d'entre elles sur les résultats du modèle de localisation-affectation. Une des premières étapes de notre programme d'étude est donc de trouver des paramètres significatifs permettant de décrire un réseau et de départager les isomorphismes.

6Soit un espace géographique représenté par un ensemble de noeuds et de liens (graphe). Les caractéristiques spatiales de ce réseau sont multiples : (1) la taille et la forme du territoire étudié, c'est-à-dire les dimensions du graphe (étendue) et la forme de ses limites. La forme de l'enveloppe (exemple : une commune, un département, un pays, etc.) détermine l'importance des effets de frontière sur les résultats. (2) La représentation du contenu du territoire est résumée par un nombre de points (n ) qui représentent la demande et/ou l'offre. Ces points sont caractérisés par leur nombre, mais aussi par leur localisation géographique (coordonnées) et par un poids associé à chacun de ces points (quantité de demande). Enfin, (3), les liens entre ces noeuds constituent un dernier élément spatial décrivant la forme du réseau de communication. Ils sont caractérisés par leur nombre (e ), mais aussi par leur localisation spatiale (couples origine-destination), par leur longueur, par le flux de transport qui y est affecté et par leur capacité (flux maximum). La forme des liens dépend de la localisation des points de demande/d'offre.

7Notre problème est d'associer à chaque réseau un (ou plusieurs) indicateur(s) de description, et de départager ainsi les réseaux en catégories exclusives. Quels réseaux se ressemblent et selon quels critères ? Quels réseaux sont topologiquement identiques ? La littérature relative à ce problème est vaste mais souvent ancienne (années 60 et 70) et relève de différents domaines de la science; nous tenterons de résumer l'état de nos connaissances dans les quelques paragraphes qui suivent et dans le tableau repris ci-dessous.

8De nombreuses mesures sont issues directement de la théorie des graphes (Berge, 1963; Busacker et Saaty, 1965). Kansky (1963) utilise plusieurs indices exprimant la centralité, la connexité (la continuité du réseau), la connectivité (le maillage plus ou moins complet), la nodalité (les relations plus ou moins nombreuses et directes entre chaque point du réseau et tous les autres). Certains indices sont dits globaux (ex.: nombre cyclomatique, , , ), d'autres locaux (ex.: le diamètre, l'indice de Shimbel, l'accessibilité)(Dupuy, Stransky, 1996; Berry, Marble, 1968). En général, ces indices sont aisément calculables mais ils ne prennent pas en compte la longueur des liens, ni la qualité des communications (Smith, 1975) et discriminent mal des réseaux de tailles identiques (Cliff, Haggett, Ord, 1979; James e.a., 1970) puisqu'essentiellement basés sur le nombre de liens (e ) et/ou de noeuds (n ). Pour un nombre donné de liens et de noeuds, il est dès lors très aisé de trouver deux réseaux topologiquement différents mais caractérisés par des indices identiques (James e.a., 1970; Arnold, Peeters, Thomas, 1996).

9Ord propose en 1967 les indices S et I pour caractériser et classifier les réseaux de transport : S et I sont basées sur l'analyse des distributions de fréquences de la matrice des plus courts chemins associée au graphe; S et I dépendent des moments d'ordre 1 à 3. La comparaison des réseaux passe par un graphique croisant les valeurs de S et de I; selon leur position sur le graphique bidimensionnel, une conclusion est tirée quant à la distribution théorique des fréquences des plus courtes distances de chacun des réseaux étudiés. Les graphes planaires relèvent le plus souvent d'une distribution beta-binomiale, les graphes non-planaires sont hypergéométriques. Lorsque le nombre d'arcs augmente, I tend vers zéro et S vers -1. Des pondérations peuvent être considérées. Ces indices sont cependant toujours insuffisants pour départager deux formes de réseaux : deux paires de valeurs S-I identiques peuvent correspondre à des réseaux différents (Cliff, Haggett, Ord, 1979).

10Une troisième catégorie d'indicateurs provient de la géomorphométrie, de l'analyse topologique des réseaux dentritiques (drainage, rivières). Les rivières sont vues comme des graphes planaires faits de sources, fourches ou bifurcations, et d'une embouchure (lien terminal). Limitée aux arbres directionnels (les rivières coulent dans un seul sens, de la source vers l'embouchure), ces indicateurs sont principalement basés sur la notion d'ordre. Plusieurs définitions de l'ordre existent; elles dépendent de leur auteur et de la nature de la mesure (nominale, ordinale, cardinale) (voir par exemple Horton, 1932, Strahler, 1952, Scheidegger, 1965, Schreve, 1966, 1967). A côté de ces notions topologiques, certains géomorphologues tiennent compte de la notion de longueur et de distance entre la source et l'embouchure (exemple : Werner, Smart, 1976; Jarvis 1972; Liao, Scheidegger, 1968). Une multitude d'indicateurs descriptifs simples existent, tous basés sur l'ordre, les bifurcations et la longueur de la rivière. Werner et Smart (1973), Jarvis (1977) et Jarvis et Werrity (1975) proposent une classification multivariée des rivières selon un choix de critères topologiques. Aucune des méthodes d'ordonancement n'est cependant extrapolable à des réseaux de communications puisque par définition le trafic est bidirectionnel et se déroule tant sur des circuits que des arbres. Aucun indice pris isolément ou en combinaison avec d'autres ne permet de tenir compte des formes sous-jacentes : deux réseaux non-isomorphes peuvent avoir des indicateurs dont les valeurs sont identiques. Des réseaux géométriquement différents dans le plan euclidien peuvent être topologiquement identiques et des réseaux ayant un nombre de sources identique ont une complexité topologique comparable mais sont topologiquement différents !

11Enfin, les valeurs et vecteurs propres des matrices d'adjacence des graphes-réseaux constituent une dernière famille de descripteurs. Kendal (1957) et Cliff et Ord (1981) décrivent un algorithme pour obtenir les valeurs propres et vecteurs propres de ces matrices. A l'époque, ils concluaient d'une part qu'un réseau fortement connecté génère de larges valeurs propres, et d'autre part, qu'au plus élevée est la valence d'un lien, au plus grand est le vecteur propre. Cette interprétation a été discutée (Hay, 1975; Tinkler, 1972; Boots, 1982, 1984; Boots, Royle, 1991; Griffith, Jones, 1980) car - tout comme en analyse factorielle - des vecteurs propres différents ne conduisent pas toujours à une interprétation dépourvue d'ambiguïtés. Cette méthode reste cependant un regard intuitif et tâtonnant, très empirique sur les graphes. Elle n'a pas abouti à l'identification certaine d'un indicateur clair de structure spatiale d'un graphe.

12A côté de ces quatre pistes d'investigations, peu de progrès significatifs ont été faits à notre connaissance, cela malgré l'émergence de nouvelles méthodes telles les fractales ou les réseaux neuronaux. A l'heure actuelle, il est encore bien malaisé de caractériser un réseau de communications par un indicateur de forme.

Conclusions

13En conclusion, la littérature géographique s'avère encore actuellement relativement pauvre en mesures efficaces de la forme des réseaux de communications. La plupart des progrès datent des années 60-70 et se sont arrêtés là. Aucun indicateur ou groupe d'indicateurs ne permet de caractériser avec certitude une forme de réseau de communication, de départager deux réseaux de façon non ambigüe. Or, il y a tout lieu de penser que certains réseaux tendent vers la concentration d'acitivtés, d'autres vers la dispersion.

14Vu la nature de la revue CYBERGEO, nous nous permettons de terminer cet article par trois questions :

• Avons-nous omis des articles fondamentaux en matière de descripteurs de graphes ? Dans l'affirmative, lesquels ?

• Quel(s) critère(s) utiliser pour départager des graphes isomorphes ?

• Et, quel(s) critère(s) pourrait-on imaginer pour opérer une partition de l'ensemble des graphes en classes qui conduirait à une typologie qui soit utile du point de vue de la k-médiane, qui conduirait à minimiser la diversité interne des classes quant aux résultats de la k-médiane ?