Les Graphes

Le programme

Qu'est-ce qu'un graphe ?

Imaginez un réseau social ayant 6 abonnés (A, B, C, D, E et F) où :
* A est ami avec B, C et D * B est ami avec A et D * C est ami avec A, E et D * D est ami avec tous les autres abonnés * E est ami avec C, D et F * F est ami avec E et D

On peut représenter ce réseau social par un schéma où : * Chaque abonné est représenté par un cercle avec son nom. * Chaque relation "X est ami avec Y" par un segment de droite reliant X et Y ("X est ami avec Y" et "Y est ami avec X" étant représenté par le même segment de droite).

Voici ce que cela donne avec le réseau social décrit ci-dessus :

graphe_1

Ce genre de figure s'appelle un graphe. Les graphes sont des objets mathématiques très utilisés, notamment en informatique. Les cercles sont appelés des sommets et les segments de droites des arêtes.

Définitions et terminologie

On appelle graphe un ensemble de points appelés sommets associés à un ensemble de lignes appelées arêtes qui relient certains sommets entre eux.

Ordre d’un graphe :
L’ordre d’un graphe est le nombre de sommets du graphe.

Adjacents (ou voisins)
Deux sommets sont dits adjacents s’ils sont reliés entre eux par une arête.

Degré d’un sommet
Le degré d’un sommet est le nombre d’arêtes issues de ce sommet.

Sommet isolé
Un sommet qui n’est adjacent à aucun autre sommet du graphe est dit isolé.

Graphe complet
Un graphe est dit complet si deux sommets quelconques distincts sont toujours adjacents. Autrement dit, tous les sommets sont reliés deux à deux par une arête.

Exemples:

graphe_2

Le graphe ci dessus est d’ordre 5 car il possède 5 sommets.
Les sommets A et B sont adjacents.
Les sommets D et E ne sont pas adjacents.
Le sommet C est isolé.

Le graphe ci dessous est complet d’ordre 3.
Chaque sommet est de degré 2.

graphe_3

Le graphe de dessous est complet d’ordre 4.
Chaque sommet est de degré 3

graphe_4

Exercice 1:

1°) Donner le degré des sommets du graphe sur le réseau social de l'introduction.
2°) Donner son ordre.
3°) Ce graphe est-il complet ?

Différents types de graphes

Un graphe peut être orienté ou non-orienté.

graphe_5

Dans un graphe non-orienté, chaque arête peut être parcourue dans les deux sens.

graphe_6

Dans un graphe orienté, chaque arête ne peut être parcourue que dans un seul sens indiqué par une flèche.

Un graphe (orienté ou non-orienté) peut contenir des boucles c’est-à-dire une arête dont l’origine et l’extrémité correspondent au même sommet (on a par exemple une boucle B sur la représentation précédente).

Propriété de la somme des degrés

Propriété:
Le nombre d'arêtes est égal à la moitié de la somme des degrés de sommets.
On peut voir ça aussi comme dans la vidéo, la somme des degrés des sommets est égal au double du nombre d'arêtes.

Ce résultat s'explique assez facilement:
En ajoutant les degrés de chaque sommet (c'est à dire le nombre d'arêtes issues de ce sommet), on comptabilise deux fois chaque arête (une fois avec le sommet d'une extrémité et une seconde fois avec le sommet de l'autre extrémité de l'arête). D'où le résultat.
Il découle de cette propriété que la somme des degrés des sommets est nécessairement paire et donc que le nombre de sommets de degré impair est pair.

Matrice d'adjacence

\[ n \in \mathbb{N}^* \]

Définition:
On appelle matrice d'adjacence associée à ce graphe la matrice \( A \) dont le terme \( a_{ij} \) vaut 1 si les sommets \( i \) et \( j \) sont reliés par une arête et 0 sinon.
\( i \) et \( j \) variant de \( 1 \) à \( n \).

En numérotant les sommets de ce graphe par ordre alphabétique, sa matrice d’adjacence s’écrit:

Matrice d'adjacence :

	A	B	C	D	E
A	0	1	1	0	1
B	1	0	1	1	0
C	1	1	0	1	0
D	0	1	1	0	0
E	1	0	0	0	0

graphe_7

Remarque:
Dans le cas d’un graphe non orienté, les coefficients \(a_{ij}\) et \(a_{ji}\) sont égaux pour tout i et tout j compris entre 1 et n.

Autrement dit, la matrice d’adjacence est symétrique.

Dans le cas d’un graphe orienté, la matrice d’adjacence n’est pas a priori symétrique.

Remarque 2:
Une matrice peut se coder en python par une liste de listes ou avec l'objet "matrix" de la bibliothèque numpy.

A = [
    [0, 1, 1, 0, 1],
    [1, 0, 1, 1, 0],
    [1, 1, 0, 1, 0],
    [0, 1, 1, 0, 0],
    [1, 0, 0, 0, 0]
    ]

A = np.matrix(A)

Exercice 2:

Ecrire la matrice d'adjacence du réseau social de l'introduction

Chaine et cycle

Définition:
On appelle chaîne toute succession d'arêtes dont l'extrémité de l'une (sauf la dernière) est l'origine de la suivante.

Le nombre d’arêtes qui composent une chaîne est appelé longueur de la chaîne.
On appelle chaîne fermée toute chaîne dont l’origine et l’extrémité coïncident.
On appelle cycle toute chaîne fermée dont les arêtes sont toutes distinctes.

Exemple:
Dans le graphe ci-dessous:
E-A-C-B est une chaîne de longueur 3.

E-A-C-B-A-E est une chaîne fermée de longueur 5. Ce n’est pas un cycle car l’arête A-E est parcourue deux fois.

D-B-A-C-D est un cycle de longueur 4.

graphe_8

Pour aller plus loin

Les graphes sont une structure fondamentale en informatique. Dans les cours suivants, nous verrons :

Les parcours de graphes (BFS et DFS) → voir PARCOURS.md
L'implémentation en POO → voir POO.md
Les algorithmes de plus court chemin (Dijkstra, Bellman-Ford) → voir le chapitre Routage

Résumé

Notion	Définition
Graphe	Ensemble de sommets reliés par des arêtes
Ordre	Nombre de sommets
Degré	Nombre d'arêtes issues d'un sommet
Adjacents	Deux sommets reliés par une arête
Chaîne	Succession d'arêtes consécutives
Cycle	Chaîne fermée sans répétition d'arêtes
Matrice d'adjacence	Représentation matricielle du graphe

Auteur : Florian Mathieu

Licence CC BY NC

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.