Permettant de relier plusieurs points entre eux, les graphes sont utilisés depuis des siècles pour simplifier la compréhension de tous types de réseaux. Et justement, il est possible d’étudier ces différentes représentations visuelles à travers la théorie des graphes.
La théorie des graphes ou l’étude des graphiques
La théorie des graphes consiste à étudier les graphes. Autrement dit, des représentations visuelles permettant de relier des objets entre eux.
D’un point de vue mathématique, le graphique G correspond à un couple de sommets V (également appelé de nœuds ou de points) et d’arêtes E (également appelées lignes ou liens). Ces arêtes permettent alors de relier plusieurs sommets entre eux et les sommets reliés par une arête sont qualifiés de voisins ou adjacents.
Voici la traduction mathématique de ces graphes : G = (V, E)
La théorie des graphes étant une sous discipline des mathématiques, elle regroupe un ensemble de théorèmes et d’algorithmes visant à résoudre divers problèmes liés aux réseaux. Mais avant de voir quelques-unes de ces applications théoriques, il convient de bien comprendre les graphes.
Les graphes, plusieurs modèles pour des intérêts multiples
Les différents types de graphes
- Le graphe non orienté : les arêtes peuvent se lire dans un sens comme dans l’autre. On dit qu’elles sont associées à une paire {u, v} où “u” et “v” représentent chacun un sommet.
- Le graphe orienté : les arêtes vont dans un sens précis (de u vers v). Dans ce cas, elles sont associées à un couple {u, v} et sont qualifiées d’arcs.
- Le graphe mixte : il contient à la fois des arêtes non orientées et des arêtes orientées (ou arc). Contrairement aux graphiques “traditionnels”, sa formulation mathématique se traduit comme suit : G = (V, E, A).
- Le graphe simple : il ne comporte aucune boucle où un sommet pourrait être relié à lui-même à travers une suite d’arêtes.
- Le graphe pondéré (ou graphe valué) : chaque arête est associée à un poids, que ce soit une distance, un coût, une taille, etc.
- Le graphe structuré homogène : l’ensemble des arêtes et sommets reproduit un schéma régulier. Il se présente généralement comme un carré ou un rectangle quadrillé.
- Le graphe structuré hiérarchique : les sommets s’organisent de manière pyramidale.
- Le graphe structuré cyclique : tous les points sont interconnectés (comme un cercle)
- Le graphe structuré centralisé : tous les points sont connectés à un seul sommet (appelé le pôle).
- Le graphe multipolaire : il est à la fois centralisé et décentralisé. Dans ce cas, les arêtes émanant du pôle sont appelées les liens forts, et celles réunissant d’autres sommets sont appelées les liens faibles. Ce modèle est particulièrement utilisé pour étudier les réseaux de types Internet et les réseaux de neurones.
- Le graphe quelconque : aucune des propriétés susmentionnées ne se dégage du graphique.
Dans la théorie des graphes, il est possible d’associer différentes familles de graphes entre eux. Par exemple, un graphe peut être non orienté, pondéré et acyclique.
L’utilité des graphes
- Les réseaux routiers : les villes sont alors considérées comme des sommets, et les routes comme des arêtes ou des arcs.
- Le web : les pages sont considérées comme les sommets, et les liens hypertextes sont les arêtes.
- Les réseaux sociaux : les individus sont les sommets, et leurs connexions sont les arêtes.
- Les bases de données relationnelles : les relations correspondent aux sommets alors que les dépendances correspondent aux arêtes. Dans ce cas, il s’agit d’un graphe orienté.
- La programmation informatique : les instructions de code à exécuter ou les données sont les sommets. Quant aux arêtes, il s’agit des relations de dépendance temporelle (l’ordre dans lequel les instructions ou les données s’exécutent).
Il ne s’agit que de quelques exemples concrets qui ont permis le développement et l’enrichissement de la théorie des graphes.
Les éléments de la théorie des graphes
Les graphes eulériens
La théorie des graphes a vu le jour pour la première fois en 1735 grâce au mathématicien suisse Leonhard Euler. Celui-ci devait alors résoudre le problème des sept ponts de Königsberg. Il s’agissait d’identifier une promenade permettant de partir d’un point A et d’y revenir en passant par les sept ponts de la ville de Königsberg. Et ce, tout en passant une seule fois sur chaque pont. Cette promenade donna ainsi naissance au chemin eulérien (ou circuit eulérien). Dès lors, tout circuit permettant d’arriver au point où il a commencé, sans passer plusieurs fois par la même arête est qualifié de chemin eulérien. Et cela se transpose à tous les graphes qui reprennent les mêmes propriétés.
La matrice d’adjacence
Très utilisée en théorie des graphes, la matrice d’adjacence est une structure de données permettant de représenter un graphe. L’idée est alors d’identifier les relations entre les sommets du graphe (qui sont représentés sur les lignes et les colonnes de la matrice). S’il existe une connexion, l’élément correspondant est égal à 1. À défaut de connexion, il est égal à 0.
Bien souvent, elle représente les graphes non orientés. Mais elle peut aussi être utilisée dans les graphes orientés.
L’algorithme de Kruskal
Il s’agit alors de trouver l’arbre recouvrant le poids minimal dans un graphe connexe, pondéré et non orienté. Autrement dit, l’objectif est d’identifier un chemin où le poids des arêtes connectant l’ensemble des sommets est le plus léger possible.
Il ne s’agit que de quelques exemples. En réalité, il existe en effet de nombreux autres algorithmes et théorèmes utilisant la théorie des graphes. Pour mieux les connaître et les appliquer au machine learning, mieux vaut se former à la science des données avec DataScientest.
Ce qu’il faut retenir
- La théorie des graphes permet d’étudier les graphes. Autrement dit, des représentations visuelles permettant de relier des points entre eux par l’intermédiaire d’arêtes.
- Il existe une multitude de graphes pour analyser tous types de réseaux. La théorie des graphes permet justement de tous les étudier.
- Elle a vu le jour en 1735 à travers les graphes eulériens. Aujourd’hui, les concepts mathématiques utilisant cette théorie se comptent par dizaines.
