A. VOCABULAIRE POUR DECRIRE UN GRAPHE

• Nœuds (sommets) et liens (arêtes)
• Matrice de connexité associée / graphes isomorphes

• Graphes vides/connexes/complémentaires
• Graphes planaires / non planaires
• Composantes connexes
• Cycles/ Régions

• Graphes valués
• Graphes orientés

B.1) Indicateurs globaux

• Indicateurs de connexité
• Indicateurs de connectivité
• Autres indicateurs

• Centralité de degré
• Centralité d'éloignement moyen
• Centralité d'éloignement maximal
• Centralité d'intermédiarité

C.1) Analyse des réseaux de transport

• Mesures d'accessibilité
• Mesures d'efficacité
• Représentations cartographiques

• Indices de sinuosité
• Indices hiérarchiques - Lois de Horton

• Forme générale d'un réseau social
• Evaluation des positions individuelles

Document 1 : VOCABULAIRE DE DESCRIPTION DES GRAPHES

1.1 Nœuds et arêtes / Matrice de connexité

Supposons que quatre équipe A,B,C et D se rencontrent dans une poule de championnat. Au bout de quelques semaines, les rencontres suivantes ont eu lieu : A a rencontré C et D ; B a rencontré D ; C a rencontré A et D ; D a rencontré A, B et C

La liste des rencontres peut être représentée par un graphe non orienté  sous forme de figure ou de matrice de connexité symétrique :
 
 

Graphe des rencontres	Matrice de connexité
		A	B	C	D
	A	-	0	1	1
	B	0	-	0	1
	C	1	0	-	1
	D	1	1	1	-

Les équipes A, B, C et D, représentées par des points, sont appelées sommets du graphe, tandis que les rencontres, représentées par des traits, sont appelées arêtes du graphe.

1.2 Graphes vides et graphes complets :

Graphe vide

Graphe complet

  1.3 Graphes complémentaire :

Deux graphes sont complémentaires s'ils n'ont aucune arête commune et si leur réunion donne un graphe complet.
 

Graphe G

Graphe complémentaire (~G)

1.4 Graphes isomorphes :

Graphe G1

Graphe G2

1.5 Graphe planaire / non planaire

Graphe planaire Ce graphe est planaire car on peut éviter un croisement des arêtes en changeant leur tracé.

Graphe non planaire Ce graphe est non-planaire car aucun arrangement ne permet d'éviter le croisement d'au moins deux arêtes.

1.6 Graphe connexe / composantes connexes

Graphe connexe

Graphe non connexe

 1.7 Graphes connexes élémentaires

Chemin

Arbre

Circuit

1.8 Cycles

Graphe à plusieurs cycles

Graphe sans aucun cycle

1.9 Graphes valués

  1.10 Graphes orientés

Dans certains cas, les relations représentées par un graphe ne sont pas symétriques (A peut être en relation avec B sans que B soit en relation avec A) et le graphe doit être orienté. Les sommets sont alors reliés par des flèches et la matrice associée n'est pas nécessairement symétrique.

Dans l'exemple du tournoi de football on peut remplacer la relation " Les deux équipes A et B se sont rencontrées" (symétrique) par la relation "L'équipe A s'est déplacé sur le terrain de l'équipe B pour la rencontrer". La matrice indique alors les déplacements des équipes et l'on suppose que chaque équipe rencontre les autres deux fois (match aller et match retour).
 

Graphe orienté A et C se sont rencontrés à tour de rôle, tout comme A et D. C s'est déplacé en D mais le match retour n'a pas eu lieu. Idem pour D qui a joué en B.	Matrice associée
		A	B	C	D
	A	-	0	1	1
	B	0	-	0	0
	C	1	0	-	1
	D	1	1	0	-
	La somme des lignes indique le nombre de matchs joués à l'extérieur. La somme des colonnes indique le nombre de matchs joués à domicile

Document 2 : Indicateurs globaux de connexité

Les indicateurs globaux de connexité mesurent le degré de fragmentation d'un graphe en composantes connexes séparées les unes des autres. Soit S le nombre de sommets d'un graphe, C son nombre de composantes connexes et S1..Sk le nombre de sommets de chacune des composantes connexes (S₁+S₂+…S_k = S), on peut définir deux indices de connexité dont les valeurs sont comprises entre 0 (graphe vide) et 1 (graphe connexe).

Indice de connexité simple : IC1 = (S-C)/(S-1)

Indice de connexité pondéré : IC2 = [ (S₁)² +(S₂)² + … (S_k)² ] / S²
 
 

Exemple d'application :

Calcul des indices de connexité :
 

Situation	Indice de connexité simple	Indice de connexité pondéré
Graphe 1	9/9 = 100%	100/100 = 100%
Graphe 2	8/9 = 89 %	(25+25)/100 = 50%
Graphe 3	8/9 = 89 %	(81+1)/100 = 81%
Graphe 4	7/9 = 78%	(49+4+1)/100 = 54 %

Commentaire :

• L'indice de connexité simple est relativement imprécis et peu fiable, car il ne tient pas compte que du nombre de composantes connexes et pas de leurs tailles respectives. Il est évident que les situations présentées sur les graphes 2 et 3 ne sont pas équivalentes, or elles correspondent à un même indice de connexité simple (89%).

• L'indice de connexité pondéré, beaucoup plus précis, exprime la probabilité que deux sommets tirés au hasard puissent être reliés par un chemin (i.e. appartiennent à la même composante connexe). Il montre que le graphe 3 est beaucoup plus connexe que le graphe 2. On remarque d'ailleurs que le graphe 4 (pourtant découpé en trois composantes connexes) a une connexité pondérée supérieure au graphe 2 (pourtant découpé simplement en 2).

Document 3 : Indicateurs globaux de connectivité

Les indicateurs globaux de connectivité mesurent la densité et la variété des relations possibles, directes ou indirectes entre les sommets d'un graphe. Ils permettent de préciser les différences entre des graphes connexes (qui ont tous des indices de connexités égaux à 100%). Leur calcul repose sur le nombre de sommets (S), le nombre de liens (L) et le nombre de composantes connexes (C) d'un graphe.

Indicateurs de connectivité basé sur la fréquence des liens

• L'indice de connectivité bexprime le rapport entre le nombre de liens et le nombre de sommets. Cet indice est simple à calculer. Une valeur supérieure ou égale à 1 indique la présence de circuits à l'intérieur du graphe.

• L'indice de connectivité g est une version standardisée de l'indice précédent, avec une valeur comprise entre 0 et 1. Il exprime le rapport entre le nombre de liens observé et le nombre maximal de liens possibles. Dans le cas d'un graphe planaire, le nombre maximal de lien est égal à 3(N-2), ce qui donne la formule suivante :

• Le nombre cyclomatique mexprime le nombre maximal de circuits indépendants que l'on peut construire simultanément à l'intérieur d'un graphe.

• L'indice de connectivité a est une version standardisée de l'indice précédent, avec une valeur comprise entre 0 et 1. Cet indice exprime le rapport entre le nombre observé de circuits indépendants et sa valeur maximale. Dans le cas d'un graphe planaire, le nombre maximal de circuits est égal à (2N-5), ce qui donne la formule suivante:

Calcul des indices de connectivité

	L	S	C	b	g	m	a
Graphe1	5	6	1	0.83	42 %	0	0 %
Graphe2	5	6	2	0.83	42 %	1	14 %
Graphe3	9	6	1	1.50	75 %	4	57 %

Document 4 : Indicateurs locaux de position

Les indicateurs locaux de position permettent de mesurer le degré de centralité ou d'accessibilité des différents sommets à l'intérieur d'un graphe. Les avantages relatifs des différents sommets peuvent varier selon le critère retenu.

Exemple d'application

• La centralité de degré (C_D) : elle correspond au nombre de liaisons directes qui partent d'un sommet. Elle correspond en géographie à la notion de carrefour.

• La centralité d'éloignement moyen (C_E) : elle correspond à la distance moyenne entre un sommet et l'ensemble des autres sommets. Le calcul de cette mesure de centralité implique la construction d'une matrice de distances de plus court chemin à l'intérieur du graphe.

• La centralité d'éloignement maximal (C_M) : elle correspond à la distance maximale entre un sommet et l'ensemble des autres sommets.

• La centralité d'intermédiarité (C_I) : elle correspond au nombre de liaisons transitant obligatoirement par un sommet, c'est-à-dire au nombre de liaisons entre les autres sommets qui peuvent être contrôlées depuis un sommet donné.

Document 5 : Analyse des réseaux de transport

5.a) Exemple d'une nouvelle autoroute
Source : Cole J.P., 1975, pp. 101-102
 
 
 
 
 
 

5.b) Exemple d'une nouvelle ligne de métro
Source : Chapman, 1977, pp. 212-214

Document 6 : Analyse des réseaux hydrographiques

6.1) Analyse de la sinuosité des cours d'eau

L'indice de sinuosité le plus simple est le rapport entre la longueur du talweg et la distance à vol d'oiseau entre ses extrémités. Toutefois cette méthode est peu fiable (dépend de l'échelle à laquelle on effectue la mesure) et certains auteurs proposent d'utiliser à la place la dimension fractale de la longueur du cours d'eau . Pour plus de détails :

Hauchard E., Delahaye D., Frankhauser P., 1999, "Analyse morphologique de talwegs et comportement scalant", Espace Géographique, 28, 3, pp. 215-224.

6.2) Analyse de la hiérarchie des talwegs à l'aide des lois de Horton

1. Sans connaître le débit des cours d'eaux, on peut les hiérarchiser en attribuant un niveau 1 aux talwegs initiaux et en considérant que la jonction de deux talwegs de même niveau forme un talweg de niveau supérieur (Méthode de Strahler). Ainsi deux talwegs de niveau 1 forment un talweg de niveau 2, deux talwegs de niveau 2 forment un talweg de niveau 3, etc.
2. On peut ensuite dénombrer le nombre de talweg de chaque niveau et calculer leur longueur moyenne.

 

 
 
 

3. On montre alors qu'il existe en général une relation exponentielle entre le nombre de talwegs et leur niveau (1ere loi de Horton) ainsi qu'entre la longueur moyenne des talwegs et leur niveau (2^e loi de Horton).

Document 7 : Analyse des réseaux sociaux

Un exemple de réseau social est fourni par le graphe des enseignants de géographie de l'Université Paris 7 pour le critère : "participe au même module d'enseignement".

DEUG 2000-2001

LICENCE 2000-2001

L'analyse de ces graphes permet de repérer les groupes d'enseignants qui travaillent le plus souvent ensemble, les liens indirects qu'ils peuvent nouer, le rôle clé de certains enseignants situés à l'interface entre plusieurs groupes, etc.

On remarquera par exemple, en licence, la position charnière des enseignants de GO303 (Grasland, Mering, Guerois) entre les enseignements de climatologie-télédétection d'une part et les enseignements de géographie régionale ou de géographie humaine d'autre part…