Graph theory and hierarchisation models

Graph theory and hierarchisation models

REGIONAL AND URBAN ECONOMICS -. Vol. 2, No. 3 (1972) 263-296 GRAPH THEORY AND HIERARCHISATEON MODELS B. ROUGET Uwhmity of Dijon Received May 19...

2MB Sizes 2 Downloads 56 Views

REGIONAL

AND URBAN

ECONOMICS

-. Vol. 2, No. 3 (1972)

263-296

GRAPH THEORY AND HIERARCHISATEON MODELS

B. ROUGET Uwhmity of Dijon

Received May 197 1

Summur~~: Graph theory is use.. in order to obtain hierarchical structures of interregional and * intraregional tlows.

1. Introduction

1. I . The gravitation hypothesis Gravitation models and central place theory are attempts to achieve a rational explanation of economic space, through resear!:h into the laws governing the organization and functioning of spati& systems. The purpose of this study is not to present these models, but to isolate from them. very schematically, the essential aspects they IWW in common, and to suggest their treatments by graph theory. Based originally on a close analogy with Newtonian physics, gravitation models compare economic space to a gravitation field, and then set out to explain the interactions between masses dispersed over the space from the gravitation hypothesis, which is formulated as follows: Any two masses exert on each other attraction forces, whose common intensity is a direct function of the masses involved, and an inverse function of the distance separating them. The gravitation force working between two masses Mi and Mi separated by a distance dg, is detined as:

in which equation G is a constant, a, b and c are the elasticities of force F with respect to the variables Mi, Mi and dq.

264

8. Rouget, Graph theory and hiemrchisation models

The difference in character between economic and physical phenomena accounts for the flexible formulations usually applier-l: the masses can be populations concentrated in a point of the territory, or revenues, or productions, etc.; distances can be physical, or economic (transportation costs, time needed to cover a certain stretch). The formulation just given serves as a base for spatial interaction models, but there are also models which derive directly from the gravitdtion hypothesis, viz.: the gravitation force exerted upon a unit mass, placed in a point i, by n masses situated in points i = 1, 2, . . . . n, will determine the potential in i:

which offers a yardstick for the overall influence of the n masses experienced in that point; the potential emerges also as n measure of the accessibility of a point i within the space to the set of masses spread over that space; the gravitation hypothesis is, in that case. expressed as follows: a mass exerts on its surroundings an impa ; which diminishes as the distance to the mass increases. Apart from potential models, this last formulation has led to the statistical study made by Reilly (1929) (based on the gradient of the attraction force), and more generally the study of market areas, either formalized or not; here attempts are made to define the range of the attraction of a town on its hinterland in terms of t’,;,: behaviour of the consumers living near that town. The construction made by August Losch also started from there, for the t.heory of the economic region has resulted from the analysis made of the networks of market areas; in that sense the theory of central places is a gravitation model. 1.2. Critical discussion of the models Gravitation models eventually show up the disparities between various masses in a spatial system, which form a hierarchic set. In fact, one need only look at the levels of the relations establishing themselves between.such masses, to discover that some of them enjoy a privileged position due to their proximity to all the masses, that is to say to the populations, and to the all-over revenue such as it is spatially dispersed. This analysis of accessibility holds for the potential models (Rouget, 197 1 ), where all the points along an isopotential curve are also placed

B. Rcuget, Graph theory and hierarchisation

models

265

such as to influence all the masses, the point(s) with the highest potential occupying the highest level in the hierarchy - maximal access to the world market, proximity of labour, etc. It is, moreover, possible t0 give priority - as in the theory of central places - to the functional character of the relations between various masses, by founding the hierarchy on the difference in central functions, i.e. on the difference in character between good:. h1:idservices offered to the consumers by various ms.ges. A mass which possesses a certain function is hierarchically superor to all those’that lack this function, while entering into competition with all others that offer the same function to consumers; in both cases the hierarchy may have more than one mass on the same level. Among the points of criticism that might be directed at these models, we shall consider only the one that is concerned with the peculiar conception of space underlying them, following the example of the theories of spatial location. In gravitation models, space is supposed to be the physical support of the interrelations between individuals, representing the attraction forces exerted by population concentrations. Space is represented by the distance between masses, which is the fundamental variable to explain the varying intensity of the gravitation force within the space; having, says Moran, “its own laws, its own function” (1966, p. 147). However, this variable is incapable of reflecting realistic spatial conditions, because the assumptions of homogeneity and continuity of space deprive the models of any operational character. 1.2.1. Homogeneity hypothesis Space is compared to an isotropic plane; the mathematical transcription of this hypothesis leads to reasoning within the scope of Euclidian metric space, generally conceived of as a plane. Accordingly, the distance between two geographical locations has the properties of the Euclidian distance. De,#i’nition:A metric space is any pair formed by a set E and a mapping d of E*E in Xt fulfilling the following conditions, which hold for any value of x, y, z belonging to E: - separation condition: x = y - d(x, _V)= 0 - symmetry condition: d(x Y) = dcU, x) - triangular inequality condition: d(x, VI G d(x, 2) + &, Y) d(x, y) is called the distance from x toy; the Euclidian distance can be

266

8. Rouge?,

Graph

theory

and

hietatchisation

tndels

defimd in the planeas: D = [(x,--Y,)~ +(?s~---JJ~)~]: where-+ ~2 and J+,, y2 are, respectively, the components of points x and y in space R2. The separation condition means that it is impossible to introduce the concept of a point’s surroundings, however fruitful it might seem in certain analyses to consider a mass as a combination of several spatially distinguished sub-sets, between which relations are established; gravitation models study only relations between clearly distinguished masses, not their internal structure. The symmetry condition itnplics that it is always possible to move between two locations in both directions at the same cost; one need but think of natural slopes to know that this condition is not &ways verified by the existing communication networks. The triangular inequality condition means that it is always to one’s advantage to move in a straight line between two points, avoiding any stopping place wflich lies outside that line, because that is the shortest route. It is easy to imagine that this hypothesis constitutes a serious constraint any time the non-homogeneity of space (mountain, river) makes it necessary to pass through a location outside that straight line. Typically, with road connections it happens quite often that the most direct route is of little importance because of its high risk coefficient; a car-driver will in such a case undoubtedly prefer the motor road, even if it takes him away from the shortest route. Conseq-uently, the gravitation force works between two masses along the straight line which connects the location points of these masses; as homogeneous space constitutes a veritable transport surface, flows of good:, and persons will be conveyed along that straight line in both directions at the same cost. Classical analysis will prove that, even with no deformation at all, there are working, within a given space, attraction forces which make each of the elements of that space specific; if one introduces the non-homogeneit.ies that characterize that space, it will obviously still harbour those forces, but it can no longer a priori be stated in which direction they will work. 1.2.2. Continuity hypothesis Ail the points of a geographical space exist; translated into mathematical terms this hypothc;is means that the space represents a convex Wt.

Defhzition: A sub-set of R” is convex if whenever it contains

points x and JJ, it also contzins the segment (x y).

the

B. Rouge& Graph theory and hierarchisatiotl models

261

Consequently, all points within the space are potential places of transit for the flows; moreover, the gravitation field will influence the whole geographical space; a concentration of population will, therefore, make an impact which diminishes uniformly in all directions as the distance to that concentration increases; this distance effect is strictly mechanical. The non-continuity of actual space generates breaks in the gravitation fields, which will then I:O longer be defined for the whole geographical space. The hypotheses of hom(:>geneity and continuity are reflected both in the circular form of the market area around every town - abstraction being made from the phenomena of spatial competition between various supply centres -- and in the shape of the curves of equal spatial potential, which il!ustrates how this macro-economic variable varies continuously within an abstract space; actually, by reducing the space to a factor working according to laws that are entirely determined, these variations deprive the models of any operational character. However, if one abandons the notion of Euclidian metric space and the geometrical constructions resu’ting from it, it becomes once more possible to introduce into the an; iysis the complexity of gravitation phenomena, and the differentiated impact of flistance. Graph theory, already successfully applied to the analysis of location (Garrison, 1960; Dacey and Nystuen, 196 1; Ponsard, 1966; Scharlig, 1969; Gadreau, 197 I), offers a valuable contribution here. without questioning the foundations of the hierarchisation models, &Ice no judgment is passed on the gravitation hypothesis. The object of the preseflt study is to suggest measuring tools for the forces of spatial attraction, by emphasizing certain aspects of graph theory that are specially suited to the analysis of disparities and to the search for hierarchies. The nodes of directed graphs and of, p-graphs G = (X. r) that are envisaged here are the spatial masses - towns or regions - of a finite set x = I i, j, k, . . . , n) containing n elements; the one-many mapping l? is a relation of influence or of hierarchy defined for this set. The structure thus outlined is composed of points between which there may or may not exist relations; the space will, therefore, be compared to a constellation of point masses grouped *ithin a network of interrelations. This hypothesis is only slightly restrictive as compared with the models such as they are usually built. There seems no need to take the shape of the spatial system into account, since we are concerned with the analysis of such properties as will subsist even when the system has been subject to continued transformation.

268

l3. Rouget. Graph theory and hierarchisation malels

Space need now no longer be homogeneous and continuous: actually, continuity can be presumed to exist only along the arcs of the graph. if they represent physical roads of communication; as regards the concept of distance, this may be re-interpreted as follows: (a) d(C) = 0 (bj d(ij) + dtjk) 2 d(ik) Further, if and only if the graph is symmetrical, one has: (c) d(ij) = dtji). In property (a) one recognizes the separation condition introduced in the definition of a metric space; condition (b) is that of triangular inequality; and condition (c) that of symmetry. Accordingly, if the graph is symmetrical, d(ij) is a distance. The deviation is the length of the shortest road between two points, but this shortest road need no longer be detined with reference to the straight line. This means that the homogeneity hypothesis is abandoned and that the actual direction of the gravitation forces has !,een sorted out, each graph expressing the particular properties of the economic space it represents. The contribution of graph theory will be developed in two successive examples, of which the first one will refer to interregional flows of migrants, the second to interregional flows of telephone calls. Two main procedures of classifying the nodes of a graph will be applied: a classification according to the powers of the nodes of a p-graph, and a classification resulting from the ordinal function of a graph.

2. Merregional migrations of the working population,

1962- I968

Gravitation models characterize the position of each spatial mass in relation to the set of masses to which they belong. Now graph theory makes it possible to study the situation of each node by analysing its centrality. If the deviation of a node i is defined by ei = maxjd(ii), then a node with minimum deviation will be called the centre of the graph. A centre is a point which can get in touch with all the others without having recourse to a lot of re-transmissions. A graph may count no, one, or several centres; it is possible for several centres of a graph to be considered as occupying equally advantageous positions. On the other hand it is possib?e to ascribe to each node i of a graph a centrality index:

fl. Rouget, Graph theory and hierarchisation

models

269

so as to measure the disparity of the individual positions of the graph. The centrality, thus derived from the length of the shortest road between two nodes, proves inadequate to incorporate fully the notion of potential. The matrix associated with a p-graph makes it possible to study the accessibility of various points of the spatial structure, taking into account simultaneously the length and the number of roads. On the basis of the information contained in the interaction flows that are supposed to be known, it is possible to define a p-graph of influence, and to attribute to each of its nodes an index of power or accessibility. The results obtained by applying this analysis to the flows of interregional migrations will be given. 2.1. Dealing with migration flows 2.1.1. 2graph of influence Imagine a p-graph G = (X, r) with n nodes, and let mii be the number of arcs running from a node i to a node j; the matrix associated with p-graph G is matrix M = [mijl n,n. *M is the matrix associatedwith pgraph c, obtained by inverting the orientation of all arcs of C; the following theorems and corollaries can be proved (Berge, 1967, pp. 124-125). Theorem: Let there be two p-graphs: G = (X, U) and _H= (X. V) with their respective associated matrices M = [mijl and N = [“ii 1. Then to matrix M + N will correspond the p-graph formed by combining the arcs of U and of V; to matrix M-N will correspond the p-graph defined as follows: from a node i to a node j one traces as many arcs as there are distinct rosds running from i to j, made up of a U-arc followed by a V-arc. Corollary I: If G is a p-graph with associated matrix M, the element pi;) of matrix Mk -- obtained by taking k times the product of M by itself - is equal to the number of distinct roads of length k running from i to j. Corollary 2: In a graph G there exists at least one roald of length equal to k, if, and only if, Mk # 0; there will be no loop if, and only if, Mk = 0 from a certain power onwards. The interaction flows, of a given nature, which are established in the

270

B. Rouget. Graph theory and hierarchisation models

course of a certain period between the masses of a spatial system, are supposed to be known; these flows define a structure of interaction that can be. represented by a table of interaction coefficients tii, obtained after elimination of the dimensional effects comprised in the initial flows. This table is of the order (II; n), the spatial system being composed of n masses. Taking into consideration the interaction coefficients, one is generaB$y able to determine dominance relations between certain spatial masses when a suitable dominance criterion is chosen. Exumple: Let us consider four regions, A, B, C, D, between which migration flows establish themselves. These flows are represented in the table of interaction coefficients printed below (flows may be expressed in percentages of the region of origin’s population, or in percentages of the total number of migrants from each region, etc.).

Region of departure

Region of arrival

A

A 13 C D

0.4 0.3 0.3 .-

B

C

D

0.1

O-3

0.4

0.2

0.1 0.4

0.2 0 1

0.1

The disparity of the coefficients may lead to a hypothesis according to which A dominates B, and D dominates both A and C. For this purpose, one needs a dominance criterion, which in the present case could be formulated as follows: a region i dominates a region 1 if ‘ii .< lli and if the relative difference between the two interaction coefficients is not under 10%. A dominance relation defined in this way for the set of regions will, in general, be partial; it is non-reflexive and asymmetric; it may be intransitive. The results obtained depend much on the selection of a suitable dominance criterion for each economic problem to be dealt with. There may exist, however, other types of relations between spatial masses, as may become evident from the following pairs of regions; A and C, B and C, B and .D, where the masses maintain relations of cornparable importance. In such a case one speaks of symmetrical influences between two masses. Finally, it is possible for certain masses to affect themselves, owing to the interplay of existing internal relations. Seen in this light, the influence relatio!h - in the broad sense -

B. Rougct, Graph theory r:d hierarchisation models

271

constructed for the set of masses, may or may not be partial, mutual, symmetric, transitive, according to the properties of the concrete system that is being studied. On this relation as a base, a 2-graph of influence, defined as follows, can be constructed: - the nodes of the digraph are the rz masses i, j, . . . , II ; dominance of a mass i over a mass j is represented by two arcs pointing from i to j: - symmetrical influence between two masses k and 1 is represented by two arcs pointing in opposite directions between k and 1; - internal relations within a mass are indicated by a ring around the corresponding node; - it is stipulated moreover that two nodes can be finked by no arc at all. Example: the 2graph corresponding to the table of coefzicients tii and its associated matrix, are, respectively (fig. 1):

Fig. 1. Z-graphof influence with associated matrix.

In this example, only the existence or the absence of dominance relations between pairs of spatial masses is considered. However, the procedure is general enough to reason in the same way starting with a p graph, so as to take into account any disparities which might exist between these relations. 2. I .2. Calculation of the powers of the nodes Let M = [ntijl be the matrix associated with a 2-graph of influence; its interpretation in terms of influence or accessibility to actual influences at work within the system, is as follows: - mij constitutes a measure of the direct influence of i on i, or of the accessibility of j for the direct influence of i; - Let pi;) be the general term of the matrix Mk; according to corollary 1 given above, p(k) represents the indirect influence of the lith drgree of i .3n j, or thg accessibility ofj for the indirect influence of the kth degree going out from i;

272

B. Rouge& Graph theory and hierarchisation mode!z

- hence, 4ij = WZij+pff’ +/I!;’ + . . . +#) represents the overall influence (direct influence, and indirect influences up to the kth degree) of i on j. or the overall accessibility of j for the influence of i. If one knows the overall influence exerted on a spatial mass by each or” the other masses in the system, one can determine with which centre a given town is lin.ked, and evaluate the attraction zones of each main centre. Reasoning from the rows and columns of the associated matrix and its successive powers, one reaches the following conclusions: - the external semi-degree of a node i, i.e. Zy=, ‘nii’ constitutes a measure of the direct influence exerted by mass i on all the masses of the spatial structure; the internal semi-degree of node j, i.e. Cy=, mii, is a measure of the direct influence undergone by that mass; - the total number of roads of a length equal to k with their initial node in point i, Zy__rp$), constitutes a measure of the indirect influence of the kth degree exerted by a mass i; the total number of roads of length k that accept j as terminal node, IS:=, pi,!) is a measure of the influence of the kth degree experienced by that mass; - hence, the total number of roads shorter than or equal to k, originating from or terminating in a given node, represent the overall influence (direct and indirect influences) exerted on or experienced by that mass, or, respectively, the accessibility of the system for its overall influence or that of the mass for the influences at work within the system. If one wants to define the powers of the nodes of a p-graph, one should distinguish two cases. Firsf case: the p-graph to be studied contains no loops. The relation which determines the p-graph is not a relation of influence, since there is no symmetric influence between nodes, nor does the p-graph show any rings; such a transitive dominance relation is called a hierarchic relation. From a rank v of, ont has MU = [ 0 j . The power of a node i is its overall influence -- direct and indirect through roads shorter than or equal to s, s representing the longest road, or roads, figuring in the p-graph.

Ill(i) = C rnij + C pf) + . . . + c i

i

pi;’

i

The overall influence experienced by a node j is defined by

B. Rouge& Graph theory and hiewchisarbn

n, (j)

=

C

mii +

C pi;) + ... + C

i

i

pi,!)

models

273

.

i

Example:

l

A

B

C

D

A

0

2

2

2

l-I,(A)=

B

0

0

2

0i

l-l,(B)=2

n,(B)

C

0

0

0

0

n,(c)=0

n,(C)=

D

0

0

0

0

II,(D)=0

fi,(D)=2

10

&(A)=0 =2 8

Comparison of the two power indices for each n:ade allows one to appreciate the disparities betwee‘ the situations C and D. Yet in this method, the same weight is attributed to all influences, whatever the length of the roads through which they are transmitted. One could imagine introducing a coefficient which would reflect the weakening inherent to indirect influences; but there is no reason at all to maintain beforehand that an identical weight should be adotpted for all the roads of the p-graph. So, the chosen index is not unique but may be substituted by other definitions, such as: l-I,(i) =

c

mij + 8

i

II,(i)

=q

c jr+/?)+ ... +; c pf;’ i

i

C mij+ q2 C pi;) + ... + 4’ C pii) i

i

O
1.

i

Second cuse: the p-graph to be studied has at least one loop. If, moreover, there is no acceptable economic criterion suitable tar diminishing the weight of indirect influences, the procedure described above cannot be applied. It is then possible to use the definition of the power of a node proposed by Berge ( 1967, pp. 128- 13 1). If M is the matrix associated with a p-graph of influence G, the iterated power of the first order of a node i is the external semi-degree of that node. if Mk = [$)I and if we suppose Z .$) = p,(i), then pk (i) is called the iterated power of the kth order o t node i. Now if the nodes of the p-graph are arranged according to the total number of roads leading from there, and inade to converge through successive power-raisings of the associated matrix, one arrives at the

B. Rouget, Graph theory and hierarchisarianmodels

274

definition of power II(i) of a node i by p&J ll(ij

=

lim k+= p,(l)+

. . . +pJn)

It is then proved that this limit exists and that vector II = [ ll( I ), . . . . II(n)] tends to become an eigenvector of matrix M. To calculate the powers, it is not necessary, in practice, to know the matrices [email protected]; indeed, whatever the value of i:

The node whose power is the maximum, is in the best situation to influence all nodes, or the one with maximum overall accessibility. The same procedure makes it possible to determine the overall influence n(i) experienced by each node of a p-graph of influence, or the accessibility of any spatial mass among the set of masses of a system; the same calculations are carried through for matrix ‘M rissociated with the p-graph of influences received, or for the columns of matrix M. Example: The powers of the nodes of the Z-graph with associated imatrix M, are: p,(A)=4 pi(B) = 3 p,(C) = 3 p,(D)=6

p,(A)=4+(3X2)+3= 13 pz(B)=3+3+6= 12 p*(C)=4+3+3= 10 p,(D)=(4>;2)+3+(3~2)+6=23

In the same way, the iterated powers of successive orders are oblained; the approximate powers no(i) and no(i) are the following: l-l’(A) = 0.23 l-IO(B) = 0.21 rP(C) = 0.17 I-IO(D)= 0.39

no(A) R’(B) ii%) n’(D)

= 0.22 = 0 34 = 0:3 1 = 0 . 13

‘I’he least dominating nodes are not necessarily also the most dominarzd. Using the ratio lI/n as an indicator of the situation of each

8. Rouget, Graph theory and hierarchisation models

275

spatial mass, one is prone to making interpretative errors: thus J region that is little dominating and little dominated may well be independent in respect of the spatial system isolated for purposes of study. 2.2. Application to in terregional data The exercise refers to interregional migrations of the total working population in France during the period 1962- 1968 (table 1). The data are taken from the population census carried out in 1968 by the National lnstitute of Statistics and Economic Studies (INSEE). The spatial framework of the analysis was that provided by the 21 “circonscriptions d’action regionale”. By total working population are meant those people in the active population who have a job and those who are in search of a job. Along the rows of table 1, one reads the out-migrants Xi/ from region i to every region listed in the columns. With the help of this table, the idea is to construct a 2-graph of influence, and to calculate for each of the 21 districts an index of the influence it exerts on the set of regional masses, as well as an index of the influence it receives from this set of masses. The definition of power applied here is that formulated by Berge. It is true that the arrangement finally achieved refers to the particular type of interaction considered here, and could be contested by the results founded on the study of other interregional flows. It seems, however, that the interaction focused on here is not a bad indicator of the economic dynamism of the regions concerned. Various criteria of dominance of one region over another may be defined; it is suggested here that region i dominates region i if *ii F-5 i

(table 2)

xii i

and if the relative difference between the two emigration rates is not under 10%; Xu is the flow of active migrants from i to i, Pi and l”i the total working population of regions i and i, measured .in 1962 (table 3); hence, two regions maintain symmetric relations of influence if the relative difference between their emigration rates is less than or equal to 10%. 0ne might contest this choice of a dominance criterion, for there is an alternative criterion: xji

-r

;’

-

i domirates i

,

B. Rouget, Graph theory and hierarchisattbn mdels

276

Table 1

Interregional migrations,period 1962-1968 Source: Collections de1’t.N.S.E.E.. Novembre 1969, S&icD.no.3 i 1

i

2

3

____-

---

I 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

8640

4

-___

13

6

7

.._.-----~-~-----_pI

8

9

IO

11

13160 20060 112808680 7340 5500 2440 2780 13540 580 1360 480 3560 13406020 1000 1740 860 3700 1620 880 800 8700 Ii60 440 280 680 4000 2360 4360 380 1320 620 340 280 1540 1300 2240 1820 3340 1240 1220 740 520 4840 1020 5140 2780 620 580 660 540 160 4000 940 820 2760 340 700 1220 700 3800 700 9720 2960 2160 1280 1680 2460 [email protected] 860 1500 1280 980 1620 420 2160 2460 7640 3720 840 260 340 880 180 640 760 4220 1320 360 180 380 480 260 4220 340 2440 2600 200 880 (780 7220 5500 880 820 1080 600 420 1120 2920 3180 3580 580 1140 14t'O480 400 10360 820 1020 6620 500 600 840 1300 1220 480 5820 1060 1120 2820 900 740 1160 1620 900 620 2080 1140 740 1900 520 1080 900 1160 2180 320 1080 340 240 2100 240 280 380 260 100 160 560 1160 780 2260 900 7380 1240 1900 2220 2720 1220 540 340 2500 460 2380 460 620 460 360 860 720 480 1240 180 880 1060 1120 1120 560 660 920 1160 2020 760,1560 I680 1860 2260 1040 1420 3720

14

15

.-. .._ 16

17

-____18

19

-. .~_ ___-. 20

21

Total

emigrants

1

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

l2

16900

13500 22860 5340 16760 380 32320 880 25780 400 17320 2400 24280 3180 127206140 4620 800 5500 1460 29340 940 36180 880 20300 460 .24700 740 21260 680 10440 360 18360 1300 11020 420 14600 640 24320 1480

-_--_I--_._

i

5

15080 7700 740 700 560 460 1840 680 1900 3820 4740 760 640 580 940 980 1060 840 560 280 340 360 9460 6720 1160 1540 1180 5580 680 1100 280 2020 620 500 340 440 640 500 2900 i260 -

14280 9360 1000 660 860 780 780 420 2180 1400 700 400 LUOO 560 2260 1540 1680 1260 700 540 560 320 1660 1240 1760 500 7140 1340 8780 10120 2840 1160 1680 2460 1100 1660 1800 6020 2620 2620 .__.___

4820 15580 4240 220 2220 320 240 2000 480 480 1480 400 1400 2340 1940 600 1260 420 220 10520 1900 460 4420 ,960 2I!O 4020 ,’700 40 1580 280 60 4360 180 880 2260 580 180 2080 380 2500 2000 840 2640 3520 1280 1620 4040 1400 1080 2880 820 5800 2140 9140 200 8720 1600 420 15640 1520 -.___ ~------.

7680 26520 700 2380 520 1600 580 2080 620 2380 540 1080 960 2460 1440 4040 1280 5360 820 2120 320 1960 880 2180 600 3120 780 2420 2460 4440 7020 4880 640 780 4740 14320 1180 2540 10420 8240

221580 43100 53960 41080 68540 52180 50540 68220 56460 21300 26520 75320 72000 58540 68340 63820 27120 72380 38960 53160 75700 -

--.

- .I_

EZ’O LZ’O oz.0 P8’0 92’0 trl.0 90’0 60’0 6O-0 SI’O SI’O II’O LI-o 01’0 80’0 1)1’0 60’0 SI’0 61’0 61

PE’O 16‘0 LI’O f 1’0 SI’O PO’0 90’0 So’0 SO’0 80’0 Lo’0 Ef’O 80’0 SZ’O Lo’0 60-O t%-0 01’0

fl’o 62’0

16’1 OS’0 f8’0 SZ’O SE-0 9t’o EQ’O 1f’0 ZZ’O f S’O OP’~ t79’o If’o ft’o IZ’O If’o I. “0 62’0 OS.0 99’0 OZ

1L.o

17

.----

----------------.

_..

PI.0 8p’O LE.0 9f’O 1z-0 ZZ’O LI’I Of’0 8P’O ff’0 S8‘1 +‘I’0 Of’0 9Z’O 9f’O ft’o 6f’O ___. LI

61’0 LZ’O St’0 20’0 60’0 ZO’O 10’0 EO’O fO-0 M)‘O ZI’O 81’0 60’0 VITO So’0 ZI’O 91

zd’o PZ’O so.0 ZI '0 60’0 or.0 SI’O ZI’O 01’0 80’0 81’0 Lo’0 PI’0 01-o EZ’O Sl

L.Z’I 81’0 9 I”0 SI’O f I’0 OZ.0 LI’O 81’0 El’0 82’0 PI’0 El’0 IZ’O St’0

PI

ZI’O f 9’0 01’0 SO’0 01’0 LO-O 01’0 SI’O 6p’O ZI’O 80’0 SI’O 61’0

f 1

C6’0 60’0 01’0 El’0 30 11‘0 26’0 tZ’0 f f-0 01’0 SI’O L.C.0

SE-1 PO.0 22’0 ZZ’O 11’0 SZ’O 09’1 PO’0 11’1 EE’O 60’0 ZI’O 6L’1 ZP’O ZE’O IZ’O 60’0 LO’0 so’0 PI’0 01’0 EO’O eo.0 9f’O 68’0 PYO 60‘0 IZ’I f 1’0 80’0 85’0 ZI’O LZ’O

81

21’0 21’0 LI’O LO’0 81’0 El.0 ZZ’O PO’1 PO’1 SO’0 LO’0 01-O 11’0 ZI’O 8L’0 ZYil 81’0 21’0 81’0 tf’0 -.._-ZI

.-----

01

60’0 61’0 01’0 12’0 LO 0 60’0 91’0 f I’0 SO’0 EO’O +O’O 9Z.O 90’0 60’0 60’0 ZZ’O MY0 SO’0 PO’0 90’0 OL’O SZ’O SfO t6.0 90’0 80’0 LYO Zl-0 fO’0 01’0 LO’0 60’0 SO’0 90’0 SO’0 80’0 LE.0 IZ’O ~0’0 90’0 ___._. -- .. II

_--.-

2~0 6Z-o 6Z’0 S9’o --.-

t

‘001

f

LI’O 01’0 80’0 fZ’0 60’0 fI’0 6t’O LO’0 01’0 f t-0 to.0 LO’0 99’0 80’0 11’0 EZ’O 60’0 PI’0 62’0 11’0 11’0 81’1 81’0 SI’O Zf’O 6Z’O 11’0 ZL’O 81’0 60’0 f I’0 01’0 SO’0 L 1’0 90’0 SO’0 61’0 ZI’O SI’O 91-o ZZ’O VL’O HP.0 01-O 91’0 tG’0 00’1 OZ.0 62’0 LI’O ZL’O 99’0 Zl’(; 8L’o ff’o ZP’O .__._~

91’0 $1’0 El’0 90’0 12’0 61’0 91’0 EO’O ZI’O 60’0 5tr.O 60’0 11’0 LO’0 ED’0 so-o 80’0 ZI’O 60’0 80’0 PI-O 11’0 EI’O 90’0 LI’O ZI’O SO’0 60’0 EZ’O Sl’ir 11’0 60’0 PI-0 11’0 90’0 9f’O 11’0 80’0 60’0 SS’O S9’0 60’0 EI’I LO-0 08’0 PI ‘0 z 1’0 CO’0 Of’0 9Z’O SO’0 El’0 01’0 61’0 90’0 IZ’O 21-O f1’0 11’0 II.0 91’0 91’0 fP.0 fZ’o 11’0 bZ’0 ~0-0 ~L’O IZ’O 9S’I Pi’0 91’0 LZ’I 8Z’o SL’O 01-O t1‘0 81’0 Zz’r!. 8Z’o - -. _. -.--_._~~--_._.L

S

8

9

6

l

!d

-

hr

f1’0 ZI’O 80’0 LO’0 11’0 80’0 80’0 80’0 60’0 60’0 6f’O s 1’0 Pit.0 VZ’O ZP’O 80’0 11-O LO’0 96’0

IZ’O .

Z

S~ll+llJa03

60-Z 89’2 SI’Z LO’1 6Z’f ES’Z 8S’Z Z9’f 19-f 26’1 LD’I L8’0 ES’1 $8’1 SO’C 00’S LIT IO’0 OI’P P8’Z

I!?

IZ oz 61 81 11 91 El PI EI II II 01 6 8 1 9 S P f Z 1

B. Rouge& Grcrphtheory and hierarchisation models

278

Table 3 List of regions: Total working population, 1962 -----I_-... ____--__-. 4 015 400 Region Parlsienne 474 600 Champagne 557 100 Picardie 557 000 Haute-Notmandie ‘I74 400 Centre Basse-Normandie 515 100 568 300 Bourgogne 1 320 400 Nord Lorraine 830 400 529 800 Alsace 372 900 FrancheComt6 Pays de la Loire 1004 LOO 999 100 Bretagne 560 300 PoitouCharentes 958 000 Aquitaine 839 400 Midi-Pyr&&s Limousin 317 300 Rho^ne-Alpes 1 722 800 511700 Auvergne Languuedoc 544 100 1 162 200 Rovence - CGte d’A;:ur- Corse

-_1

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 --

_-.-_.__

--_. - --. -._--___- --

----I_

where Xi and Xi are the total flows of migrants originating from the regions i and j and going to all other regions concerned. The results obtained, though in general depending on the criterion used, do not differ considerably in this sort of case. The dominance relation defines the 2-graph of influence as follows: the nodes of the graph are the 2 1 regions; dominance of a region i over a region j is represented by two arcs pointing from i to j; a symmetric influence is indicated by two arcs pointing in opposite directions. The 2-graph of influence is reflexive, ensuring in all cases the existence of loops and the applicability of the procedure. The associated matrix (table 4) is such that for any pair of regions i and j it is true that ??lij + rn.. = 2; in fact, all emigration coefficients have been used to determ/ie the relations of dominance between regions. This restriction will be lifted id the second example to be worked out. Directly and indirectly, the most powerful region according to this criterion will attract the largest portion of the active population in each azgion. Table 5 presents the approximate values of the powers. Three regions _occupy a dominant position, viz. the Paris region, the region Rhane-Alpes, and the region Prover&e-C&e d’Az.ur-Corsica. The regions

B. Rouge& Graph theory and kierarchisation

moL!els

279

Table’ 4 Associated matrix _. -- _. _._ i

1 2 3 4 5 6 7 8 9 10 11 I2 13 14 15 16 17 18 19 20 21

j

I

2

3 4

_.~_.~

5 6

7

----.

8 9

122222222222222222222 012000000010000020200 001102200010120120220 021102211120020200100 022212212222221220220 020001010020000000200 020002112120010220210 022111112220220120220 022102001021120120220 022102102120020220220 011000000010000020220 022202221221222120220 021202201220120220220 020002100020010020000 022212222220221220220 021002011021020120220 0002020000000000?0000 0222222222222222;1222 0001000000000200’0 0 20 2021000000 0 2 2 2 2 2 2 2 --____-.-_

_..___..-_-

--.--

-~__.-.

10 11 12 13 14 15 16 17 18 19 20 21 -__._.__.. --.-_, _~_____

200;:0010 2 2 2 2 2 2 2 2 ‘:I 0 -.. ..-.---__--

12

0

2 2

1

---_- ---

Table 5 Powers of the regions .__.-~---_

Region _._---_--_I_-_.---1 [email protected] Parisienne 18 Rhfine-Alpes 2 1 ProvenceCdte d’Azur 5 Centre 12 Pays de la Loire 1S Aquitaine 8 Nord I3 Bretagne 10 Alsace 9 Lorraine 4 Haute Normandie 7 Bourgogne 16 Midi-Pyr$&es 3 Picardie 20 Languedoc 6 Basse Normandie 14 PoitouCharentes 11 Franche ComtG 19 Auvergne 2 Champagne 17 Limousin

no 15.6 13.2 11.1 8.4 7.6 7.5 5.5 4.4 3.7 3.5 3.4 3.2 3.1 2.7 1.6 i 1 0.9 0.9 0.9 0.8

___II_ _-.-.~__--

--

i=lo 0

0 0

0.2 0.7 0.2 2.5 1.5 2 2.9 6.4 4.5 3.8 5.4 7.6 10.6 8.5 9.5 10.5 10.3 12.9

>l

>I >l >1 >l >I >I
280

B. Rouget. Graph theory and hierarchisation models

Centre and Aquitania are also in a good position to influenc: the other rl;gions; the regions least dominating, according to the criterion chosen, aTe also the most dominated: Limousin, Auvergne, Champagne, Franche-Comtg and Lower Normandy. The region Midi-Pyrenees, at thi same time little dominating and little dominated, offers an example of an independent region in respect of the interregional system. In total, only 7 regions out of 21 have a power index lI” higher than the average national index, which is 4.76; the display of scores, varying in a proportion from about one to twenty, reflects the extreme disparity that prevails among the different regions in France. One will remember that the results do not change noticeably when the dominance criterion applied refers to the share emigration from region i to region i has in total flow of emigrants coming from i; nor do they vary perceptibly if only emigration coefficients higher than 1% are taken into consideration..

3. Flows of intraregional telephone communications,

1969

The method based on powers of nodes of a p-graph may be applied to all kinds of interaction and of spatial systems. The second application to be undertaken here, relating to the flows of telephone calls of the region Bourgogne-Franche-ComttZ, will confirm that, just as various regions are linked more or less strongly to a few dominating regions, so, within one region, the various urban centres are dominated more or less strongly by a very small number of centres. Finally, attention will be drawn to the significance of ordinal functions for the hierarchisation of graphs without loops. 3.1. Dealing with flows of telephone calls Telephone statistics are among the rare sources of information which allow the study of interurban relations; even these sources are gradually disappearing owing to the installation of automatic telephone exchanges. For this reason, the management carries out periodic counts at peak hours; the statistics used in this paper stem from a count performed by the PTT managem,nt in December 1969. They refer to all traffic, both manual and au,omatic, exchanged between various centres in the region, Bourgogne-Franche-Comte, and are expressed in Erlangs/metre (table 6)+ It is easy to reconstruct from such data the

R Rouget, Graph theory and hierarchisotion models

J

p..

~

~r C~

~ . . o ~ . . ~

m

¢NI

!'i'i'i!ili!i'i'i' i m

m

0

~0

C~

"8 m

281

B. Rouget, Graph theory and hierarchisation models

282

~ . ~

"4"

°

0

.

°

,

r~



.

°

°

r~

r~

~

-

-

-

-

~

~

~

~

.~

.

°

,

,

,

~

,

°

,

,

m

t~lr".

r,..

,~fel

(.~

,

0

.

,

~J ,

0

,

.

°

,

.

m

J

~ - ~

~

o ~ o ~

~ o o o

~

.

,

B. Rougct, Graph theory and hierarchisation

models

283

number of actual communications between urban centres: it suffices to mu!Gply each figure of table 6 by 60 (to get the number tjf communication-minutes?? and afterwards to divide the results by S (the average duration of a call, in min). This conversion hdS not been carried out and the figures in Erlangs will be used for the reasoning. The results do show up a classification of the towns in the region, but it should be observed that the calls are registered as taking place between groups of telephone subscribers, groups that comprise sizeable rural regions. Moreover, the areas and population covered by the various groups are far from equivalent. On the other hand one may say that there are proportionally more subscribers in urban ,than in rural parts, and that the telephone is more intensively used in urban parts. Also, it must be pointed out that table 6 contains only centres whose total numbers of outgoing calls towards the set of other ccntres within the region exceed 12.5 Erlangs, that is to say 150 real communications. No mart. than 34 centres in the region Bourgogne-FrancheComte come up to tL;I mark. The criterion of dominance chosen is the following: a town i dominates a :own i if xii

xji

x
(tables 7 and 8)

i

where xii represents the flow of telephone communications from i to i. Xi and Xj are the total flows of communication coming from the towns i and i and going to all other analysed centres. The relative difference between the two coefficients of interaction must be at least equal to 10%. Only coefficients higher than 1% have been used to define the relations of dominance and of symmetrical influence, because they reflect a significant flow between 2 centres. The results, arranged by power categories and, within each category, by decreasing order of powers, show up (table 9) an extreme dispersion of scores, reflecting the very pronounced disparities between the situations in various groups. No more than 8 out of 34 centres have an overall influence index II” which exceeds the average regional index of 2.94; these 8 are, arranged by decreasing influence: Dijon, Chalon, sur Saane, Besancon, Beaune, Montbeliard, Macon, Belfort, Sons le Saunier. Among these eight privileged centres, the first three account for 75% of the group’s total scores. Examination of the indices of intluence

B. l~ouget. Graph theory and hierarchisation models

284

~0





~

~

.

.

.

.

.

.

°

~

. u

~J

.

°

.

.

o

,

U

~ ~ - ~ .

U

,

o

,

.

.

,

.

.

,

°

.

e-

.

.

.

.

.

¢'I

.

°

,

,

,

,

.

.

.

.

o

~

~

~

,

.

o

#

2 3 4 5 6 7 8 9 10 II 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

I

--

22

0.21

0.08 0.48 0.14 ___

0.14

0.16

24

14.08 1.37 6.27 8.18 3.4.7 0.15 1.01 0.08

5.73

0.09 0.10

2.41

0.51 1.41

0.07 0.19

0.11

0.03

0.30

0.30

1.33

0.66

0.40

0.09

- .-..-

0.24

0.12

0.22

1.90 0.16

0.72 0.35 0.71 0.19

0.18

1.33 0.04

0.20 2.54

0.33

1.14 0.40 0.11

0.33

28

2.26 5.62

1.46

1.03

0.07 0.19

0.35 0.56 0.16

29

0.31 0.42

0.13

5.59 0.09

34.99 1.60

0.16

O.il 0.16 0.25 0.24

0.63 0.76 4.46 1.20 0.15 0.14 O.QT

30

0.44 0.10

0.05

0.12

1.59

j-40 0.47

0.18

0.27 0.42 1.05 6.41 0.05

31

0.31

0.95

0.14 2.13 0.66

0.05

0.03

0.06 0.42 0.62 0.88 0.02

32

0.31 0.12

0.95 0.11

2.33 0.19

0.16 0.18 0.30

0.21 0.59 :.59 0.16 0.11 0.14 0.15

33

.-

__._-_-.-l_-.-_lll________

0.55 10.06 18.86 4.33 0.45 15.16 1.37 0.13 0.13 0.33 0.33 6.38 7.78 4.94 0.54 0.19 0.27 0.84 14.87 13.63 0.10 0.10 0.92 25.99 28.24 0.26 12.94 23.59 26.07 0.16 53.08 3.59 2.&l 0.21 65.92 1.14 22.55 0.14 0.34 48.42 1.85 27.24 0.35 49.54 9.81 4.83 3.50

1.32 12.57 10.12 6.75 20.25 7.62

0.12

0.09

0.13 0.30

0.19

1.04 0.35

0.11 0.39 0.40 2.45

0.15 0.28

0.52

3.57

2.20

27

----. .--- - --.---

36.17 32.03 0.59 43.87 4.28 29.53 18.68 20.90 6.01 0.38 0.70 0.39 0.21 0.34 0.34 0.14

31.05 16.78 10.84

0.39

0.08 0.39

1.45 0.40 0.42

1.14

26

0.48 1.49 0.18 1.89 0.19 10.91

0.81 0.17 1.09 0.16 0.02 0.14 0.19

25

0.39

2.99 0.43

1.21 0.92 0.91 1.60

0.48 2.12 3.63 4.91

0.66 0.11

2.08 21.78 1.11 1.71 10.93 0.73 0.11 1.05

23

-._ _ ._.--_.-.

0.14

0.08

0.15

0.06

0.06

0.19 0.25

0.25

0.10 0.13 0.19 0.10

0.12 0.26

0.10 0.13 0.39 0.25 0.20 0.15

0.31 0.09

0.12 0.12

0.44 0.33

11.31 16.62 13.15 14.36

1.65 1.30 30.92 1.53 il.82 28.27 1.60 16.16 40.97

2.04 33.11 19.24

0.16 0.35

0.81 0.39 0.91 0.63

0.13 0.13 0.13 1.01 14.92 12.02 11.60

0.16 0.14

0.07 0.14

0.11

0.21 0.42 2.31 0.40 0.76 11.43 1.17 2.42 4.12 0.11 0.96

0.17 0.55

21

0.44

0.27 0.16 0.18

4.34 0.39

0.40 0.16 0.80

20

0.72

2.98 0.52

0.27

0.27 1.79 4.62 0.16 6.23 0.34 0.94 0.73

19

0.40 0.64

1.61 0.16 1.16 1.14

4.99 3.04 34.22 2.26

2.08

18 0.15

Table 7 (continued)

9.77 7.42 3.07 4.18

0.10 0.13 0.31 O.iO

(1.24

0.05

0.30

0.44 0.14

0.91 0.19

0.24

0.1 i 0.16

0.08

0.27 3.06 2.33 4.41 0.10

34

z VI

z & 3

0 z.

% * w P ;: g

s 3 0” G

P s 9

2

9

286

B. Rouget, Graph theory and hierarchisation models

I

m

o%

.=. a~

J

D

8. Rouget, Graph theory and hierarchisation

models

287

Table 9 Classification of telephone groupings __

_ .-._

no -_I_30 18-12 5.5-3

_.~__.~~~ .~ _-._ _._. ._ -. tirokpings ------._... _--_.-..-

. ---.----.

.._.

-.

..-.

__--.

__-

--w

Dijon (3) Chnlon (24) -. Besanwn (5) Beaunc (1) - Montbehard (7) - Macon (27) .- Belfort ( 18) .- Lons le Saunier ( 12)

2-l

Montceau (28) - Auxcrre (30) - Le Creusot (25) -

0.8-O. I

Vesoul(22) - Dole (11) .- Autun (23) Joignl (32) - Nevers (17) - SaintClaude

(14) -- Lou-

hans (26j - Avallon (31) - Sens (33) - Pontarlier (9) Tonerrr: (34) -- Chatillon (2) -- Champagnole (IO) Morteau 18) -Clamecy (15) - Gray’{ 19) -- Montbard (4) - Morez (13) - De&e 06) 0.7-O

Paray le Menial (29) -- Lure (20) - Malche (6) -Luxeuil 121).

10 IO-7 6.8-3

2.8-l 0.8-O

Morez ! 13) Ciamecy (15) - Tonerre (34) - Louhans (26) Champagnole ( 10) Decize ( 16) - Avallon (3 1) - Sense (33) - Paraq ie Monial(29) - Montbard (4) - Maiche (6) - Autun (23) - News (17) - Luxeu;i (21) Morteau (8) - Chatillon (2 i -- Gray ( 19) - Pontarker (9) - Lure (20) - Dole (11) - Saint-Claude (14) Le Creusot (25) - Montceau (28) - Lons le Saunier (12) - Macon (27) - Belfort l.18) - Vesoul(22) MontbCliard (7) - Beaune (1 b - Besawon (5) Joigny (32) -- Chalon (24) --‘,$uxerre 130) - Dijon (3) -. _ --__ __._~. .,_.~__ --._________._ _____ ----..

received allows a number of highly dominated centres to appear: Morez, Clamscy, Tonnerre, Louhans, Champagnole. Decize. Lastly, most of the ccntres that show but slight dominance, are not much dominated either, although this is not a genera1 rule: severai centres seem relatively independent of the spatial systern analysed. They might well be so if they maintain only few relations with the set of centyes, or if they limit their relations to a very small n.umber of other towns; but their relative indcpendencz might just as well signify that they just have no ties with the system as it was isolated by the analyst in the first place, which in this case was a regional system determined on the basis of non-economic criteria. These centres might well turn aut to be dominating or dominated centres within a different regional

288

B. Rouget, Graph theoty artd hierarchisatiotr models

framework. To check this, that different regional framework would have to be reconstructed. By the same token there might exist outside the privileged spatial system, other centres that really ought to be connected with it. So, when demarcating economic regions one should try to isolate a set of sufficiently homogeneous centres, that is tc say centres where the various elements are linked together by adcyuate interactions. As a hierarchy implies a degree of potential constraint that is related to the level one occupies, centres on lower levels should also be strongly dominated. Consequently, the final arrangement will be tied up not only with the chosen criterion of dominance and the level of interaction coefficients considered to indicate a genuivle flow between centres, but also with the regional framework that h:ls been isolated; cvcn so, such an arrangement will only give an incomplete idea of the exact situation of each centre. 3.2. Deterrninatio~t of the levels oj’a graph without loops Calculation of the powers of nodes leads to attaching to each node a cardinal index representative of its position in the analysed p-graph. The influence relation determining the latter has been defined as reflexive in the two examples treated before, but this hypothesis is contestable, because it involves an excessive number of roads in the p-graph. Moreover, the spatial system studied might be such that the corresponding p-graph has no loop; apart from the possibility of worr,ing out a cardinal index of the power Jf each spatial mass, there is thz possibility of establishing a hierarchy mzJlding to the level (ordinal classification) of the spatial masses by defining an ordinal function based on the nodes of a hicrarchized graph. 3.21.

Ordinal function of a graph without loops (Roy, 1969:, pp325-334) Defbzition: A hierarchic relation, to be indicated by >, is a relation defined on a set X and possessing the following properties: - non-reflexivity - anti-symmetry i > i and j > i * i = i - transitivity i>jandj>h*ii/c A hierarchic relation constitutes a strict order relation and is in that sense different from the influence relation defined previously; it represents a special cast of dominance relation, viz. a transitive dominance relation.

E. Rotget,

Graph themy and hicrarchisation

289

modeis

A model in which the superiority of spatial mass i over massj implies that mass j is n&the; equal nor supe~,or to 1, and in which the transitivity of dominance relations is alway? vf:rified, is called a hierarchisation model. A typical example of such a modei is the construction worked out by August Losch, with its level-wise hierarchy established between the central places constituting a regional system, and in which each mass, by nature and according to the importance of its connections with other masses, occupies a specific place in the hierarchy. A hierarchy can be visualized by means of a hierarchised graph G = (X, I’), whose nodes are the elements of the hierarchy and which is constructed in such a way that an arc (ij) represents the hierarchic superiority of i over j; a hierarchised graph is not)-reflexive, asymmetric and transitive. Levels of a hierarchised graph (Potward,1968) Let G = (X, T) be a graph without loops. The foilowing theorem c.:ln be proven: Theorem: A necessary and sufficient condition for a graph G = (f,., r) to be without loopy is that there exists a numbering u in non-negative integer values of its nodes, such that one has for each node i E X: u(i) < u(j)

vj E I’(i)

The rank r(i) of a node i is a specific cease of such a numbering; suppose

co = ri/r-’

(ip = (81

c, = ti/r-‘(0

c C(J

C2 = O/l+-‘(i)c .

C,_, ={i/PWc

I:,uC,i

VIE CO, one putsr(i) = 0 ViE

C,,

one putsr(i)=

1

ViE C,, r(i)=2

r-2

U CkI vie

Cr.+ r(i)=r-1

k =I)

the number of ranks being equal to r. The ordinal function thus defined satisfies the following two theorems, which will be accepted as true. Theorem: If u(i) is the number given to a node of rank r(i) within a

9. Rouget, Graph theory wtd hierarchisation models

290

numbering u, whatever the vaiue of u: r(i) G u(i)

X

WiE

Thiorem: In a graph without loops, a node has rank k if, an.1 only if, the maximum length of a road which makes this node into a terminal extremity is equal to k. If there is a hierarchised graph available, it seems logical to give a new definition of the ordinal function: it will then be spoken of as the pseudo Grundy function and will be indicated by g’(i); it is suggested to split up the set of nodes of the hierarchised graph (or of the hierarchised p-graph) into separate categories arranged in such a way that if a node belongs to one of these categories with number k, every node which follows the node under consideration in the hierarchy (that is to.say which figures among the descendants of the initial node) forms part of a category with a number lower than k, like this:

r-‘(i)

g’(j) < g’W

WiE

g’(i) > g’(j)

VjE r(i)

or

Let m he the number of levels of the hierarchy. Now there can be defined categories of equivalence: C,n_,

‘m-2

=

ViE Cm_, ; one puts g’(i) = m - I, C’(Cm_,)=/r; 1. G’ being the value ddc,pted in category Cm_ ,

Ci/P i=(l)

= G/T‘-’

iC

ViE Cm_,;

Cm_,!

one puts g’(i) = m - 2 G’(cm_ 2)=m-2 Cm_3 = Wl+i

cC,_,U

Cm_2I WiE Cm_3; one puts g’(i) = m - 3

. c0 = ii/P(i)c

G’(Cm -3 )=m-3 l!l k=m-1

Ck}

WjE

Co;

one puts g’(i) = 0 G’(c,)=O.

B. Rouge& Graph tbory

and hierarchisation

models

291

Definii’ior,: A pseudo Grundy function is a function g’(i) which is such that, ff)r each node ic Ck, the value g’(i) is the smallest integer positive number or zero not contained in the set:

with where PC’, is the transitive closure of C, . The value of the pseudo Grundy function for the nodes belonging to the same equivalence class Ck is the smallest integer positive number, or zero, that is not attributed to the categories of direct and indirect images of Ck. It follows from this definition that if I? = 0, it is no’t necerharily true that g’(i) = 0; a npde deprived of descendants does not r,ecessarily occupy the last level of the hierarchy. The fol!owin,g theorems can be proved: Theorem: In a hierarchised graph 6 = (X, I’), a node is of levei k if and only if the maximum length of road making each node i E Ck into an initial extremity is k. Theorem: If a graph is hierarchised and finite, it will admit one, and only one pseudo Grundy function. 3.2.2. Application to the flows of telephone calls With a view to determining the levels of a hierarchy of telephone groupings in the region Bourgogne-Franche-Comt& an attempt h;as been made to define a hierarchised graph. A simple one was chosen which can easily be reproduced if necessary, This graph is constructed as follows: - The nodes of the graph are the regional telephone exchanges usled in the previous exercise, with the exception of Tonnerre, left out to avoid loops in the graph; - the existence of hierarchic dominance of a spatial mass i over a mass j is represented by an arc pointing from i to 2; one says tha,t i > j if xij

x9i

xji i

with a relative difference of at least 10% between the two coefficients of calls. In order to make reproduction easier, only coefficients at least equal to 2% are taken into considerclripil when outlining relations

B. Rouget, Graph theory and hierarchisatiou models

292

m

q.~

m

m w.4

~

M

m

m

m

r~

m

w.~

m

m

m

m

~ v . q

~4

m v . d

B. Rotget, Graph theory and hierawhisation models

293

of the hierarchy. The graph thus defined is non-reflexive, asymmetrical - symmetrical influence a&lations being deliberately neglected - and intransitive; it contains no loops; its boolean matrix is represented in table 10. The most practical method to determine the levels of the graph and to structure it according to these levels is the following. If A, is the row in which the sums of the! columns of the boolean matrix of the graph appear, then the zeros of A, are the nodes that have no precedence; they form category Cm_., . Next, the sum-row of the rows corresponding with these nodes is taken from A, to form row A 1 ; the new zeros then appearing are the nodes i for which I’-’ i C C,n_l, constituting category Cm_2. This procedure is continued until all the nodes have been numbered and category C, constituted. The structured graph is plotted according to the levels mentioned hereafter. Nodes

Value of function g’

Dijon (3)

8

Besanccn (5) - Chalon (24) - Auxerre (30)

1

7

Beaune (1: - MontbWard (7) - Lons le Saunier (12) - Joiqy (32)

1

6

Dole (11) - Saint Claulde(14) - Belfort (18) Vesoul(22) - Macon (27) - Sens (33)

j

5

Pontarlier (9) - Gray (19) - Lure (20) - Le Creusot (25) -- Louhans (26) - Montceau (28)

1

4

Morteau (8) - Champagnole (10) - Luxeuilt21) 1 Autun (23)

3

M&he (6) - Morez 0 3) - Nevers (17) - Paray le Monial(29) - Avallon (31)

2

Chatillon (2) -

1

Montbard.14) - Decize (16)

1

Clamecy ( 15)

0

The hierarchy emerging contains 9 levels, which confirms th.e extreme disparity of the indrvidual positions in the spatial system isolated for the exercise. The classification obtained cannot be directly compared with the one previously achieved, as it results frolm an entirely different ;;rangement principle. It should not be forgotten either that only relations of some importance are represented, while numerous relations of weaker impact are ignored, so that the hierarchy reflects the threshold operated in the definition of relations of dominance.

294

B. Rouge& Graph theory and hierarchisation models

4. Conclusion

The. object of this study has been to demonstrate how the definition of space used in gravitation models limited their validity; the theory of graphs seems ?n instrument that surpasses traditional analysis for the purpose since it allows of ai‘plying mathematics to a real spatial structure and to the direct and indirect relations at work between the nodes of the graph to be studied. In this way it becomes possible to study the repercussions a local change in the interaction flows has throughout the spatial system. Besides, the graph theory makes it possible not only to reveal the disparities that affect different masses of a spatial system by isolating the hierarchy in which they are arranged, but also to quantify the overall attraction forces exerted by and on each mass. These contributions seem well worth the attention, because right from the start a new conception of space is introduced into the models. However, the examples reviewed here are not exhaustive and the next important step will be to give to the contribution offered by graph theory a new place within the framework of gravitation models. Here, the graph theory has been conceived of merely as a technique for analysing economic space. It will be up to further research to integrate it into an explicative theory of the organization of economic spaces.

References Berge, C. 1967. Theorie des graphes et ses applications, Dunod, Collection Universitaire de Mat&matiques. Paris (deuxi8me edition). Dacey, M.F. and J.D. Nystuen. 1961. A Graph Theory Jntcrpretation of Nodal Regions, Papers and Proceedings of The Regional Scieuce Association, Vol. 7. Gadreau, M. 1971. Localisation et Oligopole. Collection I.M.E., No. 1, Dunod, Paris. Garrison, W.L. 1960. Connectivity of the Iqterrtate Highway System, Papers and Proceedings of The Regional Science Association, Vol. 4. Lheritier, P. 1970. La thCorie des places i;entrales, M&moire D.E.S., Faculte de Science Economique et de Gestion, Dijon. Losch, A. 1954. Die Ritumliche Ordnung der Wkchaft, Hna, Gustav Fischer, 1944; American translation: The Economics of Location, New Haven, Yale University Press. Moran, P. 1966. L’analyse spatiale en science konomique, Cujas, collection Connaissances economiques, Vol. 17, Paris. Ponsard, C. 1955. Economic et E+ce: Essai d’intggration du facteur spatial dans l’analyse economique, Paris, SEDES. Ponsard. C. 1958. Histoire des thCories Bconomiques spatiales, Paris, Librairie Armand Colin.

B. Rouge& Graph theory and hierarchisation models

295

Ponsard. C. 1966. Une application de la th&orie des graphcs 2 I’analyse de I’espace ikonomique: une modele de localisation optimale de I’unitC de production dans une structure de concurrence, Paris, Gauthier-Villars, Travaux sur I’espace Gconomique, Collection Techniques Economiques Modernes. No. 4. Ponsard, C. 1968. Les modeles de hikarchisation et la pseudo-fonction de Grundy, Rivista Internazionale di Scienze Economiche e Commerciali, f6vrier 1968, CEDAM, Ed. Dott. A. Milani, Padova. Prost, M.A. 1965. La hierarchic des villes en fonction de leurs activitks dexommerce et de services, Gauthier-Villars, collection Techniques Economiques Modernes, Paris. Reilly, W.I. 1929. Methods for the Study of Retail Relationships, University of Texas Bulletin, No. 2944. Rouget. B. 1971. Modtiles de gravitation et thBorie des graphes, Collection I.M.E., No. 2, Dunod, Paris. Roy, B. 1969. Algibre moderne et thhorie des graphes, Dunod, Collection Finance et Economic AppliqutZ, Vol. 3 1, Paris. Roy, B. 1970. Ibid., Vol. 32. Scharlig. A. 1969. Localisation optimale et th6orie des graphes, Geneve. Cahiers Vilfredo Pareto, Librairie Droz.