Introduction aux graphes

Notions de base

Qu’est-ce qu’un graphe ?

Un graphe permet de modéliser des relations ou des connexions entre objets. C’est un outil puissant pour représenter des situations complexes de manière visuelle et abstraite.

Exemples :

• Un réseau social (utilisateurs et leurs connexions)
• Un plan de métro (stations et lignes)
• Une carte routière (villes et routes)
• Un organigramme (personnes et relations hiérarchiques)
• Une structure de fichiers (dossiers et sous-dossiers)
• Un réseau informatique (ordinateurs et connexions)
• Un jeu vidéo (zones reliées entre elles, intelligence artificielle)

Les graphes sont très utilisés en informatique, en mathématiques, en logistique, et dans bien d’autres domaines où il faut représenter des objets interconnectés.

Composants d’un graphe

Un graphe est généralement noté G = (V, E), où :

• V est l’ensemble des sommets (ou nœuds, ou points). Chaque sommet représente une entité ou un objet du système modélisé (ex : une personne, une ville, un fichier…).
• E est l’ensemble des arêtes (ou liens, ou connexions). Chaque arête représente une relation ou une interaction entre deux sommets.

Les arêtes peuvent être de plusieurs types

• Orientée : l’arête possède une direction. Exemple : (A → B) signifie que la relation va de A vers B, mais pas nécessairement l’inverse. Cela convient bien à des systèmes comme les réseaux de livraison ou les flux de données.

• Non orientée : l’arête n’a pas de direction. Exemple : (A — B) signifie que la relation est réciproque entre A et B. Cela s’applique à des connexions bidirectionnelles, comme une amitié ou une route.

• Pondérée : l’arête est associée à une valeur numérique appelée poids (ou coût). Exemple : une distance entre deux villes, un temps de trajet, un coût financier… On écrit alors (A — B, 15) pour indiquer un poids de 15.

• Non pondérée : toutes les arêtes sont considérées comme équivalentes, sans notion de valeur ou de coût.

Types de graphes

Les graphes peuvent être classés selon plusieurs critères, en fonction de la nature des arêtes et de la structure globale du graphe.

Exemple visuel

• Graphe orienté : A → B → C
• Graphe non orienté : A — B — C
• Graphe pondéré : A —(5)— B —(2)— C

Le cas particulier des DAG (Directed Acyclic Graph)

Un graphe orienté acyclique — ou DAG (Directed Acyclic Graph) — est un graphe orienté qui ne contient aucun cycle.

Cela signifie qu’on ne peut jamais revenir en arrière en suivant le sens des flèches. Les DAG sont particulièrement utiles pour modéliser des relations de dépendance où l’ordre est important.

Représenter un graphe

Un graphe peut être représenté de différentes façons, selon les besoins : stockage en mémoire, visualisation, ou traitement algorithmique. Chaque représentation met en valeur un aspect particulier de la structure du graphe.

1. Liste d’adjacence

La liste d’adjacence consiste à associer à chaque sommet la liste des sommets voisins avec lesquels il est directement connecté par une arête.

Cette forme est économe en mémoire pour les graphes peu connectés (c’est-à-dire avec peu d’arêtes par rapport au nombre total de sommets). Elle permet aussi de parcourir rapidement les voisins d’un sommet.

Exemple — Graphe non orienté avec les sommets A, B, C, D et les connexions suivantes :

• A connecté à B et D
• B connecté à A et C
• C connecté à B et D
• D connecté à A et C

Liste d’adjacence :

A : B, D
B : A, C
C : B, D
D : A, C

Lecture : le sommet A est relié à B et D, etc.

2. Matrice d’adjacence

La matrice d’adjacence est une table de correspondance carrée de taille n × n (où n est le nombre de sommets). Chaque case (i, j) de la matrice contient :

• 1 (ou un poids si le graphe est pondéré) si une arête existe entre le sommet i et le sommet j ;
• 0 si aucune arête ne relie ces deux sommets.

Cette méthode permet de savoir immédiatement s’il existe un lien entre deux sommets, mais elle consomme plus de mémoire, surtout si le graphe est peu dense.

Exemple avec le même graphe (non orienté) :

Lecture : la case (A, B) contient 1 → il existe une arête entre A et B ; la case (A, C) contient 0 → A et C ne sont pas connectés.

3. Représentation graphique (ou schéma visuel)

C’est la représentation la plus intuitive : chaque sommet est un point (ou cercle), et chaque arête est une ligne (ou flèche si le graphe est orienté) qui relie deux sommets.

Elle est très utile pour :

• comprendre la structure générale d’un graphe,
• repérer visuellement les cycles, branches, connexions isolées,
• présenter le graphe à d'autres personnes.

Exemple visuel :

     A —— B
     |    |
     D —— C

Lecture : A est relié à B et D, etc.

Exemple simple de graphe

Voici un graphe non orienté entre 4 villes, où chaque sommet représente une ville, et chaque arête représente une route bidirectionnelle entre deux villes :

A —— B
|    |
D —— C

• Sommets : A, B, C, D Chaque sommet correspond à une ville.

• Arêtes : (A, B), (A, D), (B, C), (C, D) Chaque arête correspond à une route directe entre deux villes. Étant donné que le graphe est non orienté, on peut circuler dans les deux sens entre les villes reliées.

Ce graphe peut modéliser un petit réseau routier

Par exemple :

• La ville A est reliée directement à B et D.
• La ville B est reliée à A et C.
• La ville C est reliée à B et D.
• La ville D est reliée à A et C.

Ce graphe permet de visualiser les connexions possibles et de raisonner sur les trajets.

Représentation sous différentes formes

1. Liste d’adjacence :

A : B, D
B : A, C
C : B, D
D : A, C

2. Matrice d’adjacence :

3. Représentation pondérée (facultative) : Si on veut ajouter des distances, on peut imaginer :

• (A, B, 5 km)
• (A, D, 3 km)
• (B, C, 4 km)
• (C, D, 2 km)

Dans ce cas, le graphe devient pondéré. On peut alors l’utiliser pour calculer des trajets optimaux (le plus court chemin, par exemple).

Glossaire

Éléments de base du graphe

Types de graphes

Représentations d’un graphe

Propriétés et parcours