Introduction aux graphes

Comprendre ce qu’est un graphe.
Identifier les composants d’un graphe (sommets, arêtes).
Découvrir les types de graphes (orienté, non orienté, pondéré…).
Comprendre les applications concrètes des 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.

Le graphe contient trois sommets (A, B, C) et deux arêtes : l’une relie A à B, l’autre relie B à C.

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.

| Type de graphe | Caractéristiques | | ------------------ | ----------------------------------------------------------------------------------------- | | Orienté | Les arêtes ont un sens (on parle alors d’arc). L’ordre des sommets est important. | | Non orienté | Les arêtes n’ont pas de sens : la relation est réciproque entre les deux sommets. | | Pondéré | Chaque arête possède une valeur numérique appelée poids (distance, coût, temps…). | | Non pondéré | Les arêtes ne comportent aucun poids : toutes les connexions sont équivalentes. | | Cyclique | Le graphe contient au moins un cycle : on peut revenir à un sommet déjà visité. | | Acyclique | Le graphe ne contient aucun cycle : on ne repasse jamais par le même sommet. |

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é) :

| | A | B | C | D | | ----- | --- | --- | --- | --- | | A | 0 | 1 | 0 | 1 | | B | 1 | 0 | 1 | 0 | | C | 0 | 1 | 0 | 1 | | D | 1 | 0 | 1 | 0 |

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

Liste d’adjacence :

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

Matrice d’adjacence :

| | A | B | C | D | | ----- | --- | --- | --- | --- | | A | 0 | 1 | 0 | 1 | | B | 1 | 0 | 1 | 0 | | C | 0 | 1 | 0 | 1 | | D | 1 | 0 | 1 | 0 |

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

| Mot-clé | Définition rapide | | -------------------- | -------------------------------------------------------------------------------------------- | | Graphe | Structure composée de sommets et arêtes représentant des relations entre objets. | | Sommet (ou nœud) | Élément représentant une entité dans le graphe (ex : ville, utilisateur, tâche). | | Arête | Connexion entre deux sommets. Peut être orientée, non orientée, pondérée ou non. | | Arc | Terme spécifique pour une arête orientée. | | Boucle | Arête qui relie un sommet à lui-même. |

Types de graphes

| Mot-clé | Définition rapide | | -------------------------------- | -------------------------------------------------------------------------------- | | Graphe orienté | Les arêtes ont un sens (ex : A → B). | | Graphe non orienté | Les arêtes n'ont pas de sens, la relation est symétrique entre sommets. | | Graphe pondéré | Les arêtes ont une valeur ou poids (ex : distance, temps, coût). | | Graphe non pondéré | Toutes les arêtes sont égales (aucune valeur particulière). | | Graphe simple | Graphe sans boucles ni arêtes multiples entre les mêmes sommets. | | Multigraphe | Graphe autorisant plusieurs arêtes entre une même paire de sommets. | | Graphe complet | Tous les sommets sont reliés entre eux. | | Graphe cyclique | Contient au moins un cycle. | | Graphe acyclique | Ne contient aucun cycle. | | DAG (Directed Acyclic Graph) | Graphe orienté sans cycle, souvent utilisé pour représenter des dépendances. |

Représentations d’un graphe

| Mot-clé | Définition rapide | | ---------------------------- | ----------------------------------------------------------------------- | | Liste d’adjacence | Pour chaque sommet, on indique la liste de ses voisins. | | Matrice d’adjacence | Tableau indiquant l’existence d’une arête entre deux sommets. | | Matrice d’incidence | Tableau indiquant les liens entre sommets et arêtes. | | Représentation graphique | Dessin visuel avec points (sommets) et traits/flèches (arêtes). |

Propriétés et parcours

| Mot-clé | Définition rapide | | -------------------------------- | ------------------------------------------------------------------------------------------------ | | Chemin | Suite de sommets reliés successivement par des arêtes. | | Cycle | Chemin fermé qui revient au point de départ sans repasser deux fois par la même arête. | | Composante connexe | Ensemble de sommets connectés entre eux par des chemins. | | Parcours en profondeur (DFS) | Exploration récursive : on suit un chemin jusqu’au bout avant de revenir en arrière. | | Parcours en largeur (BFS) | Exploration par niveaux : on visite les voisins en priorité. | | Degré d’un sommet | Nombre d’arêtes liées à un sommet. En graphe orienté, on distingue degré entrant et sortant. |