Chapitre 5: Graphes*

Ce chapitre ne pourra pas faire l'objet d'une évaluation lors de l'épreuve terminale écrite et pratique de l'enseignement de spécialité. [BO MENE2121274N]{.cite-source}

Les graphes : une structure de données non linéaire

Vous êtes déjà habitués à manipuler des listes, n-uplets ou encore les piles et les files, qui sont des exemples de structures de données linéaires, c'est-à-dire à une dimension, on peut les parcourir du début à la fin en suivant un seul chemin.

Dans le chapitre précédent, nous avons vu les arbres, un exemple structure de données non linéaire très utilisée pour représenter une hiérarchie entre des données comme des liens de descendance dans un arbre généalogique.

En fait, les arbres sont des graphes avec bien particuliers tels que tous les sommets sauf la racine ont un unique parent(on parle de graphe acyclique orienté).

Maintenant que nous parlons de graphe, il n'existe plus aucune restriction, il n'y a plus de racine, plus de restriction sur les parents, les enfants, ou quoi que ce soit.

graphe

Un graphe est une structure de données composée d'objets: les sommets dans laquelle certaines paires d'objets sont reliées par des arêtes (ou arcs dans le cas de graphes orientés).

[Lexique de la théorie des graphes]{.cite-source}

Graphe orienté

On distingue les graphes non orientés, où les arêtes relient deux sommets de manière symétrique et les graphes orientés, où les arêtes, alors appelés arcs, relient deux sommets de manière asymétrique.

Lexique de la théorie des graphes

Graphe pondéré

Un graphe pondéré ou un réseau est un graphe où chaque arête porte un nombre (son poids).

Ces poids peuvent représenter par exemple des coûts, des longueurs ou des capacités, en fonction du problème traité. Ces graphes sont fréquents dans divers contextes, comme le problème de plus court chemin ou le problème du voyageur de commerce.

Vocabulaire des graphes

Sommets adjacents

Deux sommets reliés par une arête sont dits adjacents.

Graphe complet

Un graphe est dit complet lorsque tous ses sommets sont adjacents.

Ordre d'un graphe

L'ordre d'un graphe est le nombre de sommets de ce graphe.

Degré d'un sommet

Le degré d'un sommet est le nombre d'arêtes dont ce sommet est une extrémité.

Lexique de la théorie des graphes

Quelques exemples de graphes

En fait les graphes sont omniprésents, car il est rare que l'information puisse être réduite à une structure linéaire comme les listes ou encore à un arbre dans lequel la descendance est parfaitement établie.

Internet

Réseaux sociaux

Prenons l'exemple des réseaux sociaux tels sur Facebook ou son alternative libre Diaspora.

Dans ce type de réseau social:

• les sommets sont les utilisateurs
• les arêtes sont les liens d'amitié entre ces utilisateurs.

[A gentle introduction to graph theory]{.cite-source}

L'amitié se veut être un lien bidirectionnel, on ne peut être ami de quelqu'un qui n'est pas votre ami: C'est un graphe non-orienté.

Au contraire dans les réseaux de microblogging comme Twiter ou son alternative libre Mastodon, les liens ne sont pas de la même nature.

On peut suivre une personne, mais il n'est pas obligatoire que cette personne vous suivre en retour.

[A gentle introduction to graph theory]{.cite-source}

Le suivi est un lien directionnel : C'est un graphe non-orienté.

Graphes routiers

Comment implémenter un graphe?

Il existe deux façons d'implémenter un graphe:

• La matrice d'adjacence,
• la liste de successeurs/prédécesseurs.

Nous allons voir comment réaliser ces deux implémentations, et comment passer de l'une à l'autre.

La liste de successeurs/prédécesseurs

Liste d'adjacence

La liste d'adjacence d'un graphe non orienté, est la liste des voisins de chaque sommet.

[Article Wikipédia sur la liste d'adjacence]{.cite-source}

La matrice d'adjacence

Matrice d'adjacence

On représente les liens entre les $n$ sommets du graphe par une matrice de dimension $n$ dont l'élément non diagonal $a_{ij}$ est le nombre d'arêtes (ou son poids pour un graphe pondéré) liant le sommet $i$ au sommet $j$.

L'élément diagonal $a_{ii}$ est le nombre de boucles au sommet i.

Dans le cas d'un graphe non orienté, la matrice d'adjacence est symétrique.

Pour un graphe orienté, elle est quelconque.

[Article Wikipédia sur les matrices d'adjacence]{.cite-source}

Implémentations en Python

Le créateur de Python Guido Von Rossum, proposa une implémentation de graphe en Python utilisant la liste d'adjacence(https://www.python.org/doc/essays/graphs/):

Few programming languages provide direct support for graphs as a data type, and Python is no exception. However, graphs are easily built out of lists and dictionaries. For instance, here's a simple graph (I can't use drawings in these columns, so I write down the graph's arcs):

A -> B
A -> C
B -> C
B -> D
C -> D
D -> C
E -> F
F -> C

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

En ce qui concerne les matrices, on les représente généralement sous forme de tableaux de tableaux, comme vu en première.

M = [[1, 2, 3],
     [4, 5, 6],
     [7, 8, 9]]