GO303 : Organisation de l'espace (1)
Analyse spatiale et modélisation des phénomènes géographiques
Claude Grasland
Université Paris VII / UFR GHSS - Licence de Géographie  / Année 2000-2001 / 1er  Semestre
Chapitre 2
GRAPHES ET RESEAUX
(Documents de cours)

 
 
 


A. VOCABULAIRE POUR DECRIRE UN GRAPHE

A.1) Qu'est-ce qu'un graphe ? A.2) Types de graphes A.3) Valuation et orientation B. OUTILS GENERAUX DE DESCRIPTION DES GRAPHES

B.1) Indicateurs globaux

B.2) Indicateurs locaux C. APPLICATIONS SPECIFIQUES DE LA THEORIE DES GRAPHES

C.1) Analyse des réseaux de transport

C.2) Analyse des réseaux hydrographiques C.3) Analyse des réseaux sociaux

Document 1 : VOCABULAIRE DE DESCRIPTION DES GRAPHES

1.1 Nuds 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 :

Un graphe formé uniquement de sommets isolés est un graphe vide. Un graphe ou chaque sommet est relié à tous les autres est un graphe complet
 
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 :

Deux graphes sont isomorphes s'ils correspondent à la même matrice de connexité
Graphe G1
Graphe G2

1.5 Graphe planaire / non planaire

On appelle graphe planaire, un graphe qui peut être tracé de telle façon que ses arêtes n'aient pas d'autres intersections ou de points communs que les sommets.
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

Quand tout sommet d'un graphe est lié à chacun des autres sommets par une chaîne, on dit que le graphe est connexe. Si un graphe n'est pas connexe, on appelle composante connexe d'un élément A l'ensemble des sommets qui sont liés à A par une chaîne. Un graphe non connexe se compose de plusieurs composantes connexes non reliées entre elles.
Graphe connexe
Graphe non connexe

 1.7 Graphes connexes élémentaires

Trois types de graphes connexes élémentaires peuvent être signalées
Chemin
Arbre
Circuit

 

1.8 Cycles

Un cycle est une chaîne d'arêtes qui part d'un sommet et aboutit au même sommet. Certains graphes comportent plusieurs cycles, d'autres n'en comportent aucun.
Graphe à plusieurs cycles
Graphe sans aucun cycle

1.9 Graphes valués

La plupart des graphes sont booléens, ce qui signifie que chaque paire de sommet est caractérisée par la valeur 0 (absence d'arête) ou 1 (présence d'une arête). On peut toutefois définir également des graphes valués ou chaque arête est associée à une mesure entière ou réelle. Les matrices de distance sur réseausont un exemple de graphe valué. Pour éviter toute confusion, on associe une distance infinie aux sommets d'un graphe valué qui ne sont pas reliés par une arête. Un graphe valué connexe permet de calculer des distances sur réseau (plus court chemin) .
Graphe valué

Matrice associée
 
A
B
C
D
A
-
inf.
50
90
B
inf.
-
inf.
40
C
50
inf.
-
65
D
90
40
65
-

  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 (S1+S2+Sk = 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 = [ (S1)2 +(S2)2 + (Sk)2 ] / S2
 
 

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 :


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

b = L/S g = L/Lmax = L / [3(S-2)] (dans le cas d'un graphe planaire) Indicateurs de connectivité basé sur le nombre de circuits indépendants m = L-S+C a = m/mmax = (L-S+C) / (2S-5) (dans le cas d'un graphe planaire) Exemple d'application

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


 
 

Sommet 1 2 3 4 5 6 7 8 9 10
CD 1 1 3 4 6 3 3 3 3 3
Dij
1
2
3
4
5
6
7
8
9
10
tot
1
-
2
1
2
3
3
4
4
4
3
26
2
2
-
1
2
3
3
4
4
4
3
26
3
1
1
-
1
2
2
3
3
3
2
18
4
2
2
1
-
1
1
2
2
2
1
14
5
3
3
2
1
-
1
1
1
1
1
14
6
3
3
2
1
1
-
1
2
2
2
17
7
4
4
3
2
1
1
-
1
2
2
20
8
4
4
3
2
1
2
1
-
1
2
20
9
4
4
3
2
1
2
2
1
-
1
20
10
3
3
2
1
1
2
2
2
1
-
17
CE
2.9
2.9
2.0
1.6
1.6
1.9
2.2
2.2
2.2
1.9
2.1
Sommet 1 2 3 4 5 6 7 8 9 10
CM 4 4 3 2 3 3 4 4 4 3
Sommet 1 2 3 4 5 6 7 8 9 10
CI 0 0 15 18 0 0 0 0 0 0



 

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.  

     
     
     

  4. 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 (2e 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