Cours d'informatique pour le lycée

Graphes

Définition

Un graphe est un objet mathématique très simple avec lequel on peut faire des choses extrêmement compliquées. Il est constitué de sommets (ou nœuds) reliés par des arêtes (ou liens). Si les arêtes sont fléchées, on parle de graphe orienté sinon on parle de graphe non-orienté. Dans un graphe orienté, on appelle parents d'un nœud, les nœuds qui pointent vers lui. On appelle fils d'un nœud, les nœuds vers lesquels il pointe.

Un graphe peut représenter un réseau social, des liens d'amitié, un réseau routier.

1) Pour le graphe ci-dessous, dire s'il est orienté ou non, donner le nombre de sommets et le nombre d'arêtes.

2) Pour le graphe ci-dessous, dire s'il est orienté ou non, donner le nombre de sommets et le nombre d'arêtes.

On utilisera parfois des graphes pondérés pour représenter par exemple des distances sur une carte. Dans un tel graphe, les arêtes sont associées à un poids :

Propriétés

Les propriété les plus communes pour parler d'un graphe sont les suivantes :

3) Pour le graphe ci-dessous, trouvez deux cycles. Donnez également la distance entre A et D.

Représentation

Nous avons utilisé intuituvement une représentation visuelle d'un graphe. Mais nous aurions pû utiliser une description textuelle d'un graphe. Par exemple pour celui de la question 2 :

4) Dessinez le graphe correspondant à la description ci-dessous :

5) Dessinez le graphe correspondant à la description ci-dessous :

Implémentations

On parle d'implémentation lorsqu'il s'agit de « représenter » un graphe dans un système informatique. Même si nous ne verrons pas directement comment on implémente un graphe en Python nous allons parler des deux principales implémentations d'un graphe.

Matrice d'adjacence

Une matrice n'est qu'un tableau à double entrée :

Nous avons ci-dessus une matrice à 3 lignes et 4 colonnes. En mathématiques on utilise les matrices pour effectuer des calculs, nous les utiliserons ici simplement comme des tableaux à deux dimensions.

Une matrice d'adjacence est une matrice carrée (même nombre de lignes que de colonnes) où chaque ligne et chaque colonne représentent un sommet. Pour un graphe non-orienté on mettra un « 1 » sur la case [i][j] s'il y a une arête entre le sommet i et le sommet j, et un « 0 » sinon. Pour un graphe orienté on mettra un « 1 » sur la case [i][j] s'il y a une arête du sommet i vers le sommet j, et un « 0 » sinon. Pour un graphe pondéré on mettra sur la case [i][j] le poids du lien entre le sommet i et le sommet j.

6) Donnez la matrice d'adjacence du graphe ci-dessous.

7) Donnez la matrice d'adjacence du graphe ci-dessous.

8) Donnez la matrice d'adjacence du graphe ci-dessous.

Listes d'adjacence

Pour un graphe non orienté, une liste d'adjacence associe à chaque sommet la liste de ses voisins. Par exemple, pour le graphe ci-dessous

La liste d'adjacence serait :

Pour un graphe orienté, une liste d'adjacence associe à chaque sommet la liste de ses successeurs. C'est à dire les sommets vers lesquels il pointe. Il est également possible de faire une liste d'adjacence des prédécesseurs, ou même les deux pour des raisons de symétrie.

9) Donnez la liste d'adjacence du graphe ci-dessous.

10) Donnez la liste d'adjacence des successeurs du graphe ci-dessous.

Choix d'implémentation

On utilisera une matrice d'adjacence dans le cas d'un graphe avec beaucoup de liens (on parle de graphe dense) et une liste d'adjacence dans le cas contraire. Cela permettera de gagner de la mémoire. Le choix peut aussi dépendre de l'utilité du graphe. En fonction de l'algorithme utilisé, on pourra préférer une implémentation à l'autre.