Graphes

Vidéo : les graphes, vocabulaire et représentations (7 min 56)

Objectifs et prérequis

Prérequis : dictionnaires pour les représentations, notions de base en mathématiques (ensembles, couples)

À l’issue de ce chapitre, vous saurez :

définir un graphe et utiliser le vocabulaire associé (sommet, arête, arc, degré, chaîne, cycle, connexité) ;
distinguer graphes orientés et non orientés, pondérés et non pondérés ;
représenter un graphe par une matrice d’adjacence ;
appliquer le théorème de la somme des degrés (et, en complément hors programme, la condition d’Euler pour les chaînes eulériennes).

Premières définitions

Définitions

Définitions (suite)

Un graphe est la donnée d’un ensemble de sommets et d’un ensemble d’arêtes qui relient deux sommets.
L’ordre du graphe est le nombre de ses sommets.
Une boucle est une arête reliant un sommet à lui-même (la rue 4 ci-dessus).
Deux sommets reliés par une arête sont dits adjacents.
Un graphe simple est un graphe sans boucle et tel qu’entre deux sommets, il y a au plus une arête.

Définitions (suite)

Un graphe orienté est un graphe tel que ses arêtes ont un sens de parcours. On parle aussi d’arcs au lieu d’arêtes dans un graphe orienté.
Un graphe complet est un graphe dont tous les sommets sont reliés deux à deux par une unique arête.
Le degré d’un sommet est égal au nombre de fois où le sommet est l’extrémité d’une arête.

Remarque 1

Lorsque le graphe est simple, le degré d’un sommet est plus simplement égal au nombre d’arêtes issues de ce sommet.
Lorsque le graphe n’est pas simple, alors une arête qui forme une boucle sur un sommet compte pour deux dans le degré de ce sommet.

Théorème 1

La somme des degrés de tous les sommets d’un graphe est égale au double du nombre total d’arêtes : \[\sum_{S\text{ sommet}} deg(S)=2\times\text{Nombre d’arêtes.}\]

Remarque 2

Dans un graphe complet d’ordre $n$ (avec $n$ sommets), le degré d’un sommet est égal à $n-1$. Le graphe complet d’ordre 5 est donné ci-dessus.

Chaînes sur un graphe

Définitions

Dans un graphe, une chaîne (ou un chemin) est une suite d’arêtes mise bout à bout. La longueur d’une chaîne est le nombre d’arêtes constituant la chaîne. Dans le cas, où les arêtes ont été prises une seule fois et que les extrémités coïncident, la chaîne est un cycle.

Définitions (suite)

Un graphe est connexe lorsque, pour chaque paire de sommets, il existe au moins une chaîne reliant les deux sommets. En d’autres termes, lorsque un graphe est connexe, il est « d’un seul tenant ».
Complément hors programme. Une chaîne eulérienne est une chaîne composée de toutes les arêtes du graphe, chacune prise une seule fois. Si, de plus, la chaîne revient à son sommet d’origine, la chaîne eulérienne est un cycle eulérien.

Exemple 1

Le graphe donné en introduction de ce chapitre admet une chaîne eulérienne. La voici : Piscine - Lycée - Lycée - Boulangerie - Maison - Boulangerie - Centre commercial - Maison - Piscine - Centre commercial. Elle part de la Piscine et arrive au Centre commercial, les deux seuls sommets de degré impair (degré 3).

Théorème 2

Un graphe admet une chaîne eulérienne si, et seulement si, ce graphe est connexe et il a exactement aucun ou deux sommets de degré impair. Dans le cas d’un graphe connexe ayant aucun sommet de degré impair, la chaîne eulérienne est, plus précisément, un cycle eulérien.

Remarque 3

L’hypothèse « le graphe est connexe » est aussi très importante ! En plus de l’étude des degrés des sommets, il faudra vérifier à chaque fois cette hypothèse.

Matrice d’adjacence

Définition

Soit $G$ un graphe d’ordre $n$ dont les sommets sont numérotés de 1 à $n$. La matrice d’adjacence du graphe $G$ est la matrice carrée $A$ de taille $n$, où $a_{ij}$, le coefficient sur la $i-\text{ième}$ ligne et $j-\text{ième}$ colonne, est égal au nombre d’arêtes reliant les sommets $i$ et $j$. Lorsque $i$ et $j$ ne sont pas adjacents, alors $a_{ij} = 0$. Si le graphe $G$ est orienté, $a_{ij}$ est le nombre d’arêtes allant du sommet $i$ vers le sommet $j$.

Exemple 2

Exemple 2 (suite)

Remarque 4

Dans un graphe non orienté et simple, la somme des coefficients d’une ligne (ou d’une colonne) de la matrice d’adjacence est égale au degré du sommet associé à la ligne (ou colonne).
La matrice d’adjacence d’un graphe non orienté est symétrique par rapport à la première diagonale.
La matrice composée de 1, sauf la diagonale composée de 0, est la matrice d’un graphe complet.
Soit G un graphe orienté, alors la somme des coefficients de la matrice d’adjacence est égale au nombre d’arêtes.

Théorème 3

Complément hors programme. Soit $G$ un graphe et $A$ sa matrice d’adjacence et $p$ un entier. Soit $M=A^p$ la matrice « puissance $p-\text{ième}$ de A » : $A^p=A\times\cdots\times A$. Le coefficient $m_{ij}$ de la matrice $A^p$ est égal au nombre de chaînes de longueur $p$ reliant le sommet $i$ au sommet $j$.

Vérifiez votre compréhension

Un graphe non orienté a 5 sommets et chaque sommet est de degré 2. Combien d’arêtes possède-t-il ?
Réponse
D'après le théorème de la somme des degrés : somme = 5 × 2 = 10 = 2 × nombre d'arêtes. Donc le graphe possède 5 arêtes. (C'est un cycle à 5 sommets.)
Comment reconnaît-on qu’un graphe est non orienté en regardant sa matrice d’adjacence ?
Réponse
La matrice est symétrique par rapport à la diagonale : \$a_{ij} = a_{ji}\$ pour tout \$i, j\$.
Un graphe connexe à 6 sommets possède-t-il au minimum combien d’arêtes ?
Réponse
Au minimum 5 arêtes (il forme alors un arbre). En effet, un graphe connexe à \$n\$ sommets possède au moins \$n - 1\$ arêtes.

Graphes pondérés - Recherche du plus court chemin

Définitions

Un graphe est dit étiqueté lorsque ses arêtes sont affectées d’étiquettes. Elles peuvent être des nombres, des symboles, des lettres, etc.
Un graphe pondéré est un graphe étiqueté dont les étiquettes sont des nombres positifs, appelés poids de cette arête.
Le poids d’une chaîne d’un graphe pondéré est la somme des poids des arêtes qui la composent.
Une plus courte chaîne (ou chemin) entre deux sommets est, parmi toutes les chaînes qui les relient, une chaîne de poids minimal. Le poids de cette plus courte chaîne définit la distance entre les deux sommets.

Exemple 3

Le graphe du début de ce cours peut être modifié pour indiquer les distances (en km) plutôt que les noms des rues. Il devient un graphe pondéré. Le plus court chemin de la maison au lycée est alors celui passant par la boulangerie.

Exemple 3 (suite)

Exemple 3 (suite)

Attention. On verra qu’une plus courte chaine ne passe pas nécessairement par le moins d’arêtes possibles. Il faut bien distinguer le poids d’une chaîne (la somme des étiquettes) et sa longueur (le nombre d’arêtes parcourues).

L'essentiel à retenir

Un graphe est défini par un ensemble de sommets et un ensemble d’arêtes (non orienté) ou d’arcs (orienté).
Le degré d’un sommet est le nombre d’arêtes incidentes ; la somme de tous les degrés vaut deux fois le nombre d’arêtes.
La matrice d’adjacence est un tableau $n \times n$ ; elle est symétrique pour un graphe non orienté. Le coefficient $(i,j)$ de $A^p$ donne le nombre de chaînes de longueur $p$ entre $i$ et $j$ (complément hors programme).

L'essentiel à retenir (suite)

Un graphe pondéré associe un poids à chaque arête ; le poids d’une chaîne est la somme des poids, et ne correspond pas forcément à la chaîne la plus courte en nombre d’arêtes.
Les parcours de graphes (en profondeur et en largeur) et les algorithmes de plus court chemin s’appuient sur ces représentations.

Exercices

Exercice 1 : vocabulaire et propriétés

Soit le graphe non orienté $G$ suivant :

Exercice 1 : vocabulaire et propriétés (suite)

Déterminer le degré de chaque sommet.
Vérifier le théorème de la somme des degrés sur ce graphe.
Le graphe est-il connexe ? Justifier.
(Complément hors programme.) Le graphe admet-il une chaîne eulérienne ? Justifier à l’aide du théorème d’Euler.

Solution

deg(A) = 2, deg(B) = 3, deg(C) = 2, deg(D) = 3, deg(E) = 3, deg(F) = 1.
Somme des degrés = 2 + 3 + 2 + 3 + 3 + 1 = 14 = 2 × 7 arêtes. ✓
Oui, il existe un chemin entre toute paire de sommets (par exemple A–B–D–E–F et A–C–D).
Les sommets de degré impair sont B (3), D (3), E (3) et F (1), soit quatre sommets. Or une chaîne eulérienne n’existe que s’il y a exactement 0 ou 2 sommets de degré impair. Ici il y en a 4 : le graphe n’admet pas de chaîne eulérienne.

Exercice 2 : matrice d’adjacence

On considère la matrice d’adjacence suivante :

$$M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}$$

Les sommets sont numérotés $S_0, S_1, S_2, S_3$.

Exercice 2 : matrice d’adjacence (suite)

Dessiner le graphe correspondant.
Le graphe est-il orienté ? Justifier en observant la matrice.
Déterminer le degré de chaque sommet.
Donner toutes les chaînes de longueur 2 reliant $S_0$ à $S_3$.

Solution

Le graphe correspondant :
Non orienté car la matrice est symétrique ($M = M^T$).
deg($S_0$) = 2, deg($S_1$) = 2, deg($S_2$) = 2, deg($S_3$) = 2.
Chaînes de longueur 2 de $S_0$ à $S_3$ : $S_0 \to S_1 \to S_3$ et $S_0 \to S_2 \to S_3$.

Exercice 3 : implémentation Python

On représente un graphe par un dictionnaire d’adjacence :

graphe = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["B", "D", "F"],
    "F": ["E"]
}

Exercice 3 : implémentation Python (suite)

Écrire une fonction degre(graphe, sommet) qui renvoie le degré d’un sommet.
Écrire une fonction nb_aretes(graphe) qui renvoie le nombre d’arêtes du graphe.
Écrire une fonction voisins_communs(graphe, s1, s2) qui renvoie la liste des voisins communs à deux sommets.

Solution

def degre(graphe, sommet):
    return len(graphe[sommet])

def nb_aretes(graphe):
    total = 0
    for sommet in graphe:
        total = total + len(graphe[sommet])
    return total // 2

def voisins_communs(graphe, s1, s2):
    communs = []
    for s in graphe[s1]:
        if s in graphe[s2]:
            communs.append(s)
    return communs