Thème 1

Les graphes

Structures relationnelles

Introduction

Pourquoi les graphes ?

Dans le cours sur les réseaux, nous avions représenté les routeurs par des cercles et les connexions entre eux par des traits.

Cette représentation correspond à un graphe.

Il existe de nombreuses autres applications : réseaux informatiques, réseaux urbains, circuits électroniques, liaisons moléculaires, réseaux sociaux...

Les ponts de Königsberg (1736) — Euler

Premières définitions

Arête et sommet

Un graphe est un ensemble de points nommés sommets, dont certains sont connectés par des arêtes.

Remarque

La position des sommets et la longueur des arêtes n'ont pas d'importance : seule compte la manière dont ils sont connectés les uns aux autres.

Les arêtes peuvent même se croiser et n'ont pas besoin d'être droites.

Graphe orienté et arc

Dans certains graphes, les arêtes ont un sens et sont modélisées par des flèches. On les appelle des arcs.

Ce type de graphe est appelé graphe orienté.

Graphe pondéré

Dans certains graphes, les arêtes portent un nombre. Ces graphes sont appelés graphes pondérés.

Le nombre figurant sur une arête s'appelle le poids de l'arête.

Graphe non connexe

Certains graphes sont constitués de plusieurs groupes de sommets qui ne sont pas connectés les uns aux autres. Ces graphes sont dits non connexes.

Vocabulaire

Chaîne

Dans un graphe non orienté, une suite finie d'arêtes consécutives reliant deux sommets.

Chemin

Dans un graphe orienté, une suite finie d'arcs consécutifs reliant deux sommets.

Cycle

Dans un graphe non orienté, une suite d'arêtes consécutives distinctes dont les deux sommets extrémités sont identiques.

Circuit

La notion équivalente à celle d'un cycle mais dans un graphe orienté.

Métriques sur les graphes

Ordre

L'ordre d'un graphe est le nombre de sommets qu'il possède.

Degré

Le degré d'un sommet est le nombre d'arêtes qui se rencontrent à ce sommet.

Exercice

Déterminer l'ordre et le degré de chaque sommet :

Autres métriques

  • La longueur d'une chaîne est le nombre d'arêtes qui la composent.
  • La distance entre deux sommets est la longueur de la plus courte chaîne.
  • Le diamètre d'un graphe est la plus grande distance entre deux sommets.
  • Le centre est le sommet qui minimise la distance maximale aux autres.
  • Le rayon est la distance maximale entre le centre et les autres sommets.

Adjacence

Sommets adjacents

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

Voisinage

Le voisinage d'un sommet est l'ensemble des sommets qui lui sont adjacents.

Graphe complet

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

Exercice

Parmi les graphes ci-dessous, lequel est complet ?

Matrice d'adjacence

Matrice d'adjacence

Une matrice d'adjacence est un tableau à deux dimensions qui représente les relations d'adjacence entre les sommets d'un graphe.

Exemple


\begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix}

Exercice

Déterminer la matrice d'adjacence du graphe ci-dessous :

Titre du popup

Message du popup !