Ce cours comporte plusieurs pages:

Graphes

Les graphes et les arbres permettent de construire des schémas qui mettent en évidence une structure sur des données.

modelisation reseau social — graphe modelisant un reseau social

Complexité et morphologie d’un graphe - définitions

On appelle graphe la donnée d’un ensemble fini V de points (ou sommets du graphe, vertices en anglais) et d’un ensemble E de liens entre ces points.

$$G = (V,E)$$

L’ensemble E de liens peut être vu comme une relation R sur V × V. Il peut être représenté par une matrice d’adjacence.

Lorsque cette relation est symétrique (c’est à dire que l’existence d’un lien entre un sommet s1 et un sommet s2 est réciproque) le graphe est dit non orienté. Un lien est appelé une arête.
Lorsque cette relation n’est pas symétrique, le graphe est dit orienté. On parle alors d’arc entre deux sommets.

Un chemin C est une suite consécutive d’arêtes: C = {s0s1, s1s2, …, sk-1sk} avec C ⊂ E.

Des poids peuvent être associés aux liens d’un graphe, par exemple pour représenter la distance. Il s’agit alors d’un graphe pondéré.

Un graphe peut servir à modéliser un reseau d’ordinateurs, un reseau social, les distances entre villes par la route…

Lorsqu’un graphe non orienté est en un seul morceau, c’est à dire lorsqu’il existe pour tous sommets s1 et s2 un chemin les reliant, le graphe est dit connexe.

Et lorsqu’un chemin mène d’un sommet s à lui-même, on parle de cycle.

Des poids peuvent être associés aux liens d’un graphe, par exemple pour représenter la distance. Il s’agit alors d’un graphe pondéré.

Et lorsqu’un chemin mène d’un sommet s à lui-même, on parle de cycle.

Mesures sur un graphe

Ordre: le nombre de ses sommets
taille : le nombre de ses arêtes
degré d’un sommet s: nombre d’arêtes qui relient ce sommet à d’autres sommets.
un graphe est dit complet si tous ses sommets sont connectés entre eux deux-à-deux. Pour N sommets, cela correspond à un nombre d’arcs egal à: N * (N-1). Et si le graphe est non orienté:

$$\tfrac{N \times (N-1)}{2}$$

La densité D d’un graphe est une indication générale de sa connectivité et indique s’il y a beaucoup ou peu d’arêtes. C’est le rapport entre le nombre d’arêtes existantes et leur nombre possible:

$$D = \tfrac{A}{N \times (N-1)}$$

Le graphe est creux si sa densité est proche de zero, et dense si elle se rapproche de 1.

Diamètre d’un graphe: plus longue distance entre sommets du graphe. Voir plus loin.

Application: Choisir la structure de donnée adaptée

Question: Pour chacun des exemples suivants, choisir le type de graphe adapté parmi: graphe orienté/non orienté, pondéré, non connexe, sans cycle. Précisez également ce que représentera un sommet, et ce qui sera une arête.

un reseau de villes reliées par des routes, comportant l’information de leur longueur (en km). Toutes les villes sont supposées être reliées par au moins une route. Ces routes sont toutes en double sens.
un reseau social de type Facebook, où les participants ont des liens d'amitié entre-eux. Ce lien est réciproque (si Marcel est ami avec Justine, alors Justine est aussi amie avec Marcel). Les sous-reseaux ne sont pas tous reliés entre eux. (Il existe au moins deux groupes A et B complètement indépendants: aucune des personnes de A n’est amie avec celles de B).
un reseau social de type Twitter: les participants ont des folowers. Cette relation n’est pas réciproque. Les folowers suivent les participants qui partagent les même centres d’intérêt.
une partie de jeu de morpion (tic-tac-toe), où les états de la partie sont liés aux états suivants possibles.

Implémentations

Plusieurs modes de représentation sont possibles pour stocker des graphes: matrices d’adjacence, listes des voisins, des successeurs ou des prédécesseurs.

Liste de voisins et matrice d’adjacence

Liste de voisins

Un exemple simple présente ici un graphe créé à partir d’une liste de voisins: [[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]]

La première sous-liste correspond aux liens que forme le sommet 0. Ici, c’est donc avec les sommets 1 et 2.

Liste d’adjacence

Cette liste L peut aussi être mise sous forme d’une matrice M:

M = [[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 0]]

ce qui forme une matrice, en présentant les sous-listes l’une sous l’autre:

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

Avec la premiere sous-liste [0, 1, 1, 0] le sommet 0 est lié aux sommets 1 et 2, ce qui est signifié par le 1 aux index 1 et 2.

Cette représentation en matrice est particulièrement adaptée aux graphes pondérés. On remplace alors le 1 dans la matrice par le poids de l’arête.

Question: représenter le graphe pondéré dont la matrice d’adjacence est donnée ci-dessous:

$$\begin{pmatrix} 0 & 10 & 10 & 9 \\ 10 & 0 & 5 & 10 \\ 10 & 5 & 0 & 10 \\ 9 & 10 & 10 & 0 \end{pmatrix}$$

Matrice de distance entre sommets

Une matrice d’adjacence peut aussi indiquer la distance entre sommets. Soit le reseau social ci-dessous:

Exemple issu de la page PythonLycee - auteur Franck CHEVRIER

Simplifions la représentation de ce reseau social en un Graphe:

Et utilisons la matrice d’adjacence pour indiquer le plus cours chemin d’un sommet à l’autre.

Ainsi, une fois la matrice établie, nous pouvons en déduire le diamètre de ce graphe (plus grande longueur entre 2 sommets du graphe). Ici, cette distance vaut 3.

Dans un graphe plus grand, la détermination du plus chemin necessite une méthode basée sur un algorithme. Par exemple, l’algorithme BFS ou bien l’agorithme de Dijkstra.

Graphe avec étiquette

On utilisera un dictionnaire comme structure de données. Les clés étant les étiquettes des sommets, et les valeurs, la liste des sommets adjacents:

D = {‘a’: [ ‘b’, ‘c’], ‘b’: [ ‘a’, ‘c’, ’d'], ‘c’: [ ‘a’, ‘b’, ’d'], ’d' : [ ‘b’, ‘c’]}

Question: Représenter la matrice d’adjacence équivalente.

Liste de successeurs

Cette représentation est particulièrement adaptée aux graphes orientés.

On peut représenter un graphe avec une liste chaînée des successeurs:

sommet => liste de sommets liés suivants

0 => 1, 2
1 => ...
2 => ...
3 => ...

Le sommet 0 aura alors 2 successeurs, les noeuds 1 et 2.

Question: Compléter la liste de successeurs

L’implémentation utilise le même principe que pour une liste chainée linéaire. Sauf qu’ici, le nombre de successeur est supposé être supérieur à 1.

Il y aura alors plus d’un attribut suiv. Supposons que le degré sortant maximum est égal à 3:

class Sommet:
	def __init__(self,val,suiv1=None,suiv2=None,suiv3=None):
		self.val = val # etiquette du sommet
		self.suiv1 = suiv1
		self.suiv2 = suiv2
		self.suiv3 = suiv3

S2 = Sommet(2)
S1 = Sommet(1)
S0 = Sommet(0,1,2)

Liste de predecesseurs

Il peut être necessaire d’établir aussi, pour chaque sommet, une liste de predecesseurs:

sommet => liste de sommets liés précédents

0 => None
1 => 0 
2 => ... 
3 => ...

Question: Compléter la liste de prédécesseurs

Modéliser le réseau internet

Lien vers la page: réseau internet

Cas particulier d’un arbre: un graphe hierarchique

Lien vers la page arbres

Liens

Exercices simples sur la morphologie des graphes avec corrections: hmalherbe.fr
Algorithmes et structure de données utilisant la programmation orientée objets : https://notebooks.lecluse.fr/python/nsi/terminale/graphes/algorithmique/poo/tp/2020/08/17/nsi_t_algo_graphes.html#Exemples-de-graphes
Notebook: PythonLycee - auteur Franck CHEVRIER
Cours GLasius - ac-Bdx

Allophysique