• 12 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 03/02/2020

Appréhendez le concept de graphe

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Définissez un graphe et le degré d'un sommet

Nous allons poser quelques définitions des notions de graphe utiles pour les réseaux.

Un graphe, c’est :

  • un ensemble d’éléments qui sont mis en relation binaire les uns avec les autres ;

  • éventuellement un bon modèle mathématique pour représenter l’interconnexion d’éléments d’un réseau ;

  • la représentation d'une relation considérée, qui peut être éventuellement orientée ou pondérée. Nous verrons cela dans la suite.

Plus formellement, ces éléments sont appelés les « sommets » du graphe. L’ensemble des sommets est souvent noté V pour « vertices » en anglais.

Ici A, B, C et D.

A, B, C et D sont les sommets du graphe
A, B, C et D sont les sommets du graphe

Chaque sommet est relié à certains autres, ses voisins : on dit que les sommets reliés sont « adjacents ».

Ici, A est adjacent à B, C et D. C est voisin de A et D mais pas de B. On dit qu’il existe une « arête » entre A et B. L’arête {AB} est dite « incidente » à A et à B. L’ensemble des arêtes est souvent noté E pour « edges ».

On peut alors définir le degré d’un sommet comme le nombre de sommets auquel il est adjacent, soit le nombre de ses voisins, ou, de manière équivalente, le nombre d’arêtes qui lui sont incidentes.

En effet, une arête est incidente à ses deux extrémités, elle est donc comptée deux fois dans la somme des degrés. Une conséquence immédiate est que le nombre de sommets de degré impair est nécessairement pair.

Nous allons ensuite aborder des concepts permettant d’appréhender le routage dans les réseaux, notamment la notion de chemin.

Appréhendez le concept de chemin dans un graphe

Si on considère qu’une arête modélise la possibilité de transmettre de l’information entre deux éléments d’un réseau, ici C peut communiquer avec A et D, mais pas avec B.

Supposons que chaque sommet représente un routeur, comme dans un réseau IP, avec sa capacité à recevoir de l’information d’un voisin et la retransmettre à un autre voisin. 

C peut alors communiquer avec B en passant par l’intermédiaire de D.

Communication entre C et B
Communication entre C et B

On dit qu’on utilise le chemin C-D-B. On aurait pu utiliser le chemin C-A-B ou passer par D puis A pour rejoindre B.

Formellement, un chemin est un ensemble d’arêtes successives, chacune étant incidente à un même sommet que la précédente. On le représente par la suite des arêtes qui constituent le chemin, (v0,v1), (v1,v2), etc. (vk-1,vk), où k est la longueur du chemin.

Alternativement, on peut considérer la suite des sommets qui sont utilisés, donc v0, v1, … vk, mais sous-entendant qu’un sommet est adjacent au sommet suivant.

Si on considère que les arêtes ont un poids ou une longueur, le poids d’un chemin est la somme des poids des arêtes qui le composent.

Ce poids peut être un péage par exemple, un coût d’utilisation, un temps de traversée, ou l’énergie à dépenser pour la traversée, en fait toute métrique additive.

Un chemin peut former une boucle, et passer plusieurs fois par le même sommet : par exemple le chemin ABCDAE. Cela reste un chemin mais dans le cas du routage dans les réseaux, on chercher à les éviter à tout prix.

On utilise souvent les plus courts chemins entre deux sommets, c’est l’ensemble des chemins qui ont la plus petite longueur possible, le plus petit poids possible.

Définissez le diamètre d'un graphe

La notion de chemin est au cœur des problématiques de routage dans les réseaux. Nous verrons plus tard comment les calculer. Néanmoins, ils permettent déjà de définir une caractéristique importante d’un graphe : le diamètre.

Au cœur, il y a la distance entre chaque paire de sommets, qui est donnée par la longueur ou le poids d’un plus court chemin.

Le diamètre est une notion globale au graphe, et c’est la plus grande distance nécessaire à parcourir pour passer d’un sommet à un autre.

Par définition, le diamètre borne la distance entre deux sommets.

Définissez des graphes particuliers

Pour clore ce chapitre introductif, nous allons voir quelques graphes particuliers que l’on retrouve souvent dans les réseaux.

On a déjà vu ce qu’est un chemin, une suite de sommets adjacents ou d’arêtes incidentes. Un chemin de N sommets est constitué de N-1 arêtes. En réseau, on cherche souvent à éviter les chemins avec boucle.

Il y a toutefois un chemin avec boucle qui est très utile, le cycle.

C’est un chemin dont le dernier sommet rejoint le premier. Cela permet d’avoir 2 possibilités de router de l’information. C’est au cœur de nombreuses solutions de tolérance aux pannes dans les réseaux.

Il y a aussi :

  • les graphes extrêmes tels que le graphe vide, sans arête, qui n’est plus vraiment un réseau ;

  • le graphe complet qui, lui, a, par contre, toutes les arêtes possibles. C’est le graphe qui a la plus grande densité et c’est le seul de diamètre 1.

Nous allons terminer par les arbres.

Exemple d'arbre
Exemple d'arbre

Cette structure apparaît partout en réseau :

  • arbre de routage ;

  • arbre couvrant ;

  • etc.

Pour N sommets, il y a N-1 arêtes. Impossible d’être moins dense sans déconnecter un sommet. On peut identifier une racine de l’arbre comme une sorte de « point de départ ». Chaque nœud sauf la racine a alors un ancêtre. Les autres voisins « en bas » sont des descendants. Les sommets qui n’ont pas de descendants sont appelés des feuilles.

La profondeur de l’arbre, c’est la plus grande distance d’une feuille à la racine (pas loin de la moitié du diamètre).

Les arbres sont très pratiques pour router car il n’y a, entre deux sommets, qu’un seul chemin possible : il part du premier, remonte jusqu’au plus petit ancêtre commun et redescend. Du coup, il n’y a jamais de boucle dans un arbre.

Un arbre particulier, c’est l’étoile dont le centre est la racine, le degré est le nombre de feuilles et le diamètre 2. Cela modélise bien un système centralisé ou la topologie d’un réseau local autour d’un routeur.

Passons au chapitre suivant pour aborder le parcours en largeur.

Exemple de certificat de réussite
Exemple de certificat de réussite