Introduction à la théorie des graphes

Comment modéliser les connexions par paires entre des objets ?

À l’aide d’une structure mathématique appelée graphe. C’est là tout l’objet de la théorie des graphes : l’étude des graphes.  

Les éléments fondamentaux de la théorie des graphes sont les sommets (ou nœuds) et les arêtes (ou liens). Un sommet représente une entité ou un point dans un graphe, tandis qu’une arête désigne une connexion ou une relation entre deux sommets. Ensemble, ces composants forment la structure d’un graphe, qui peut être orienté ou non orienté, pondéré ou non pondéré, selon la nature des relations modélisées.

En informatique, la théorie des graphes sous-tend de nombreux algorithmes et structures de données utilisées pour représenter des réseaux tels qu’internet, les réseaux sociaux et les systèmes de communication. Elle fournit aussi des outils pour résoudre des problèmes de connectivité, de recherche de chemin et d’optimisation, et constitue un socle pour comprendre diverses structures et notions mathématiques comme les arbres, les cycles et les graphes plans.

Dans cet article, nous allons vous donner les clés pour bien démarrer avec la théorie des graphes.  

Créé par l’auteur avec Midjourney

Qu’est-ce que la théorie des graphes ?

La théorie des graphes est une branche des mathématiques qui étudie les propriétés et les applications des graphes. Un graphe définit un ensemble d’objets appelés sommets (ou nœuds) reliés par des arêtes (ou liens). 

L’objectif principal est de comprendre la structure de ces graphes et d’explorer des problèmes de connectivité, de recherche de chemin et d’optimisation de réseaux.

En analysant ces relations, la théorie des graphes permet d’éclairer de nombreux problèmes concrets, dans des domaines très variés.

D’où vient la théorie des graphes ?

Les origines de la théorie des graphes remontent au XVIII^e siècle avec les travaux du mathématicien suisse Leonhard Euler. Sa solution au problème des ponts de Königsberg, en 1736, est considérée comme l’un des premiers problèmes de théorie des graphes. Il s’agissait de trouver un parcours dans la ville de Königsberg qui franchisse exactement une fois chacun de ses sept ponts. L’approche d’Euler a jeté les bases de ce qui deviendra plus tard l’étude formelle des graphes.

Aux XIX^e et XX^e siècles, la théorie des graphes s’est considérablement développée grâce aux contributions de mathématiciens comme Carl Friedrich Gauss, qui a étudié les polyèdres, puis de chercheurs ayant formalisé des concepts et mis au point des algorithmes pour les problèmes liés aux graphes. 

L’essor de l’informatique au milieu du XX^e siècle a encore accéléré cette progression, aboutissant à une large utilisation de la théorie des graphes dans les algorithmes, l’analyse de réseaux et les structures de données.

Notions fondamentales de théorie des graphes

Comprendre les fondamentaux de la théorie des graphes est indispensable pour aborder des sujets plus avancés. Pour commencer, posons quelques bases… 

Graphes comme paires ordonnées

Un graphe se définit formellement comme une paire ordonnée G = (V, E), où :

• V est l’ensemble des sommets (ou nœuds), représentant les entités individuelles du graphe.
• E est l’ensemble des arêtes (ou liens), représentant les connexions entre paires de sommets.

Sommets (V) et arêtes (E)

• Sommets (V) : unités ou points fondamentaux d’un graphe. Chaque sommet représente une entité ou un emplacement dans la structure modélisée.

• Arêtes (E) : connexions ou relations entre des paires de sommets. Chaque arête relie deux sommets et indique une relation ou un chemin entre eux.

Types d’arêtes

• Arêtes orientées : dans un graphe orienté (ou digraphe), les arêtes ont une direction, d’un sommet vers un autre spécifique. Cette direction est souvent matérialisée par une flèche. Les arêtes orientées servent à modéliser des relations asymétriques, comme un flux de trafic ou des contraintes d’antériorité dans un planning.

• Arêtes non orientées : dans un graphe non orienté, les arêtes n’ont pas de direction et relient simplement deux sommets. Ce type de graphe représente des relations symétriques, comme l’amitié réciproque ou des connexions dans un réseau où le sens n’a pas d’importance.

Terminologie et concepts de base

Définissons maintenant quelques notions essentielles : 

Sommet (nœud)

Un sommet représente une entité ou un point dans la structure du graphe. Par exemple, dans un graphe de réseau social, chaque personne peut être représentée par un sommet.

Degré d’un sommet

Le degré d’un sommet correspond au nombre d’arêtes qui lui sont incidentes. Cela renseigne sur sa connectivité et son importance dans le graphe. Pour mieux l’imaginer, pensez à une personne, représentée par un sommet, dans un réseau social. Si de nombreuses arêtes partent de ce sommet, on dira qu’il a un « degré élevé », signe d’une personne très influente. Dans un réseau de transport, un nœud de degré élevé indique un hub central du réseau, connecté directement au plus grand nombre d’autres lieux.   

Chemin

Un chemin est une séquence de sommets où chaque paire consécutive est reliée par une arête. Les chemins peuvent être simples (sans répétition de sommets) ou généraux (avec répétitions). Par exemple, dans un graphe avec les sommets A, B, C et D, un chemin possible est A → B → C → D, chaque sommet étant relié au suivant par une arête.

Cycle

Un cycle est un chemin qui commence et se termine au même sommet, sans autre répétition de sommets ou d’arêtes. Les cycles peuvent être simples (pas de répétition sauf le point de départ/arrivée) ou généraux. Exemple : dans un graphe avec A, B, C et D, un cycle simple est A → B → C → D → A.

Graphes connexes

Un graphe est connexe s’il existe un chemin entre chaque paire de sommets. Autrement dit, dans un graphe connexe, tout sommet peut rejoindre n’importe quel autre par une suite d’arêtes. Un bon exemple est un réseau social où chacun est accessible depuis n’importe qui.

Types de graphes

La théorie des graphes recouvre divers types de graphes, adaptés à des usages et analyses différents. Dans cette section, nous présentons ces types, leurs structures de base et des exemples d’applications. Vous saurez ainsi quand utiliser chaque type pour résoudre un problème précis et modéliser fidèlement des situations réelles.

Graphe simple

Visualisation d’un graphe simple Source : Wikipedia

Un graphe simple ne comporte ni arêtes multiples (plus d’une arête entre une même paire de sommets) ni boucles (arêtes reliant un sommet à lui-même). Chaque arête relie deux sommets distincts.

Exemples :

• Un réseau social de base où chaque amitié est représentée par un seul lien entre deux personnes.
• Une carte de villes reliées par des routes directes uniques, sans itinéraires multiples ni auto-connexions.

Multigraphes

Visualisation d’un multigraphe avec arêtes multiples en rouge et plusieurs boucles en bleu Source : Wikipedia

Un multigraphe autorise plusieurs arêtes (arêtes parallèles) entre la même paire de sommets et peut aussi comporter des boucles. Ce type de graphe représente des situations où plusieurs interactions ou connexions existent entre des entités.

Exemples :

• Un réseau de transport où plusieurs compagnies aériennes opèrent des vols entre les mêmes villes.
• Un réseau de communication avec plusieurs canaux reliant la même paire de nœuds.

Graphes pondérés

Visualisation d’un graphe pondéré Source : Hyperskill

Dans un graphe pondéré, chaque arête porte un poids ou un coût associé, représentant une mesure quantitative comme une distance, un temps ou une capacité. Les graphes pondérés servent à modéliser des problèmes où les arêtes ont des intensités ou des coûts différents.

Applications :

• Sur une carte de villes reliées par des routes, les poids peuvent représenter des distances ou des temps de trajet.
• Dans un problème d’optimisation de réseau, les poids peuvent représenter la bande passante ou le coût des liens de communication.

Graphes orientés (digraphes)

Visualisation d’un graphe orienté Source : Wikipedia

Un graphe orienté, ou digraphe, possède des arêtes dirigées, c’est-à-dire que chaque arête va d’un sommet vers un autre sommet distinct. La direction, souvent indiquée par une flèche, représente un flux ou une relation à sens unique.

Cas d’usage :

• Un diagramme de flux où des tâches doivent être réalisées dans un ordre précis.
• La structure de liens d’un site web, où des hyperliens pointent d’une page vers une autre, illustrant une connexion unidirectionnelle.

Graphes non orientés

Visualisation d’un graphe non orienté Source : Baeldung

Dans un graphe non orienté, les arêtes n’ont pas de direction. Une arête relie simplement deux sommets et la relation est mutuelle ou bidirectionnelle. L’ordre des sommets dans une arête n’a pas d’importance.

Exemples :

• Un réseau d’amis où l’amitié est réciproque et les connexions bidirectionnelles.
• Un plan routier non orienté où les routes relient les villes dans les deux sens sans préciser de direction.

Théorie des graphes d’arbres

Un arbre est un type de graphe connexe et acyclique, c’est-à-dire sans cycle. Un arbre à $$n$$ sommets possède exactement $$n−1$$ arêtes. Toute paire de sommets est reliée par un unique chemin, garantissant l’unicité du parcours entre deux sommets.

Voici un récapitulatif des propriétés d’un arbre : 

• Connexe. Il existe un chemin entre toute paire de sommets.
• Acyclique. Aucun cycle, donc aucun circuit fermé.
• Chemin unique. Il existe exactement un chemin entre deux sommets, ce qui implique une connectivité minimale.
• Nombre d’arêtes. Un arbre à $$n$$ sommets a $$n−1$$ arêtes.
• Sous-arbre : tout sous-ensemble d’un arbre, y compris un seul sommet, est lui-même un arbre, dit sous-arbre.
• Feuilles. Les sommets de degré 1 sont appelés feuilles (ou nœuds feuilles). Ce sont les extrémités de l’arbre.

En quoi les arbres diffèrent-ils des autres graphes ?

Contrairement aux graphes généraux, les arbres ne contiennent pas de cycles. Ainsi, tout graphe comportant des cycles ne peut pas être classé comme un arbre. 

Un arbre à $$n$$ sommets possède exactement $$n−1$$ arêtes, alors que les graphes généraux peuvent avoir un nombre variable d’arêtes, y compris des arêtes multiples et des boucles. Autre différence : les arbres sont toujours connexes, tandis que les graphes généraux peuvent être disconnexes et se composer de plusieurs composantes, dont certaines peuvent être des arbres. 

De plus, dans un arbre, il existe exactement un seul chemin entre deux sommets, contrairement à d’autres graphes où plusieurs chemins peuvent exister, notamment en présence de cycles ou d’arêtes multiples.

Applications

Les arbres sont fondamentaux, tant en théorie qu’en pratique, pour l’informatique et l’organisation des données. Ils offrent des solutions très efficaces à de nombreux problèmes structurels et algorithmiques. Par exemple : 

Structures de données

• Arbres binaires : utilisés pour organiser les données de manière hiérarchique. Exemples : arbres de recherche binaires, qui facilitent la recherche et le tri rapides.
• Tas (heaps) : type d’arbre binaire utilisé dans les files de priorité pour gérer et extraire efficacement l’élément maximum ou minimum.
• B-trees : utilisés dans les bases de données et systèmes de fichiers pour un stockage et une recherche efficaces, avec prise en charge des insertions, suppressions et requêtes.

Conception de réseaux

• Routage : les arbres sont utilisés dans les protocoles de routage (comme les arbres couvrants) pour déterminer le chemin le plus efficace de transmission des données dans un réseau.
• Diffusion : en conception de réseaux, les structures en arbre facilitent une diffusion efficace des données, en réduisant les redondances.

Représentation hiérarchique

• Systèmes de fichiers : les systèmes de fichiers utilisent souvent des arbres pour représenter répertoires et sous-répertoires, reflétant l’organisation hiérarchique des fichiers.
• Organigrammes : les arbres modélisent les hiérarchies organisationnelles, en montrant les lignes de reporting et les relations entre rôles.

Analyse syntaxique

• Arbres de syntaxe abstraite (AST) : utilisés dans les compilateurs et interprètes pour représenter la structure syntaxique du code source, faciliter la vérification et l’optimisation.

Applications de la théorie des graphes

La théorie des graphes s’applique largement à de nombreux domaines. Elle joue un rôle clé pour résoudre des problèmes complexes et optimiser des systèmes. En voici quelques exemples : 

Informatique : réseaux, algorithmes et structures de données

La théorie des graphes est fondamentale pour concevoir et analyser des systèmes de réseau, développer des algorithmes et structurer des données. Par exemple, la mise en réseau s’appuie fortement sur la théorie des graphes pour modéliser et gérer les connexions entre dispositifs. Les topologies de réseau sont représentées par des graphes afin d’optimiser la transmission des données et le routage. 

Des algorithmes comme Dijkstra et Kruskal résolvent respectivement les problèmes de plus court chemin et d’arbre couvrant minimal. La théorie des graphes fonde également des structures de données comme les listes d’adjacence et les matrices, essentielles pour manipuler et interroger efficacement les données.

Biologie : modélisation des réseaux biologiques

La théorie des graphes est aussi déterminante en biologie pour modéliser et analyser des réseaux complexes, tels que : 

• Réseaux d’interactions protéine-protéine
• Voies métaboliques
• Réseaux de régulation génique

Ces réseaux sont représentés par des graphes où les sommets désignent des entités biologiques (p. ex. protéines, gènes) et les arêtes représentent des interactions ou des relations entre elles. 

Cette approche aide les chercheurs à comprendre les relations au sein des systèmes biologiques, à prédire des effets fonctionnels et à identifier des cibles potentielles pour le développement de médicaments.

Sciences sociales : analyse des réseaux sociaux

En sciences sociales, la théorie des graphes sert à analyser les réseaux sociaux, où les individus sont des sommets et leurs interactions ou relations sont des arêtes. 

Cette analyse aide à comprendre les structures sociales, les schémas d’influence et la dynamique des communautés. En mobilisant des concepts comme la centralité et la connectivité, les chercheurs identifient des relais d’influence, étudient la diffusion de l’information et analysent les comportements sociaux.

Transports : flux de trafic et urbanisme 

On l’ignore souvent, mais routes, intersections et lignes de transport sont modélisées sous forme de graphes afin de : 

• Optimiser les flux de circulation
• Réduire les embouteillages
• Améliorer la planification d’itinéraires. 

Les algorithmes basés sur les graphes aident à concevoir des réseaux de transport efficaces, à gérer les systèmes de transports publics et à planifier les infrastructures urbaines. L’analyse de ces réseaux permet aux urbanistes de prendre des décisions éclairées pour renforcer la mobilité et la connectivité au sein des villes.

Pas à pas : construire et analyser un graphe simple

Vous maîtrisez les bases et vous voyez les applications concrètes de la théorie des graphes. 

Passons à la pratique en créant et en analysant votre propre graphe simple. Pour aller à l’essentiel, ce guide est découpé en deux parties : 

• Construction 
• Analyse

Logiquement, commençons par la construction : c’est parti… 

Construire un graphe simple

Étape 1 : définir le problème. 

Supposons que nous voulions modéliser un petit réseau d’amis dans un réseau social. 

Nous pouvons utiliser la bibliothèque NetworkX en Python, conçue pour l’analyse de réseaux, pour le modéliser. 

Commençons par créer un graphe : 

# Import libraries 
import networkx as nx # Network analysis
import matplotlib.pyplot as plt # Data visualization
import pydot # Python interface to Graphviz
from networkx.drawing.nx_pydot import graphviz_layout
# Create a graph
graph = nx.Graph() 

Étape 2 : identifier les sommets. 

Dans notre réseau social fictif, nous avons quatre personnes : Alice, Bob, Carol et Dave. Elles seront représentées par des sommets dans notre graphe – rappelez-vous, cela représente une entité ou un emplacement dans la structure modélisée.

Voici comment créer les sommets en Python :

# Add the nodes 
# graph.add_node("Alice") --> Add one node per time
graph.add_nodes_from([
    "Alice","Bob", "Carol", "Dave"
]) # Add multiple nodes

Étape 3 : déterminer les arêtes. 

Supposons que les relations d’amitié soient les suivantes :

• Alice est amie avec Bob et Carol.
• Bob est ami avec Alice et Dave.
• Carol est amie avec Alice.
• Dave est ami avec Bob.

Ces relations forment donc les arêtes suivantes :

• Alice–Bob
• Alice–Carol
• Bob–Dave

Voici comment définir les arêtes en Python : 

# Add the edges
# graph.add_edge("Alice", "Bob") --> Add one edge per time
graph.add_edges_from([("Alice", "Bob"), 
                      ("Alice", "Carol"),
                      ("Bob", "Dave"),
                      ("Bob", "Alice")  # Ensuring all described edges are included
                     ]) # Add multiple edges

Étape 4 : dessiner le graphe.

Une fois les sommets et arêtes définis, on peut tracer le graphe pour visualiser les relations. Le code ci-dessous crée une représentation graphique du réseau avec les sommets et arêtes étiquetés :

# Visualize the plot
pos = graphviz_layout(graph, prog="dot")
nx.draw(graph, 
        pos, 
        with_labels=True, 
        node_size=1000, 
        node_color=["pink", "yellow", "tan", "orange"])
plt.show()

Résultat : un graphe montrant les connexions entre Alice, Bob, Carol et Dave, comme décrit.

Ce code produit le graphe suivant : 

Un graphe simple modélisant un réseau social [créé par l’auteur]

Pour modéliser votre propre réseau social, copiez ce DataLab Notebook et adaptez-le à vos besoins. 

Analyser le graphe simple

Étape 1 : vérifier la connectivité. 

Puisqu’on peut aller de n’importe quel sommet à n’importe quel autre par une suite d’arêtes, le graphe est connexe. 

Pour mieux l’appréhender, voici un chemin entre chaque paire de sommets : 

• Alice → Bob : arête directe.
• Alice → Carol : arête directe.
• Alice → Dave : via Bob.
• Bob → Carol : via Alice.
• Bob → Dave : arête directe.
• Carol → Dave : via Alice et Bob.

Étape 2 : déterminer le degré de chaque sommet. 

Rappel : nous avons défini le degré d’un sommet comme « le nombre d’arêtes qui lui sont incidentes ». En l’appliquant à notre exemple, on obtient : 

• Alice = degré 2 (connectée à Bob et Carol)
• Bob = degré 2 (connecté à Alice et Dave)
• Carol = degré 1 (connectée à Alice)
• Dave = degré 1 (connecté à Bob)

Chaque degré est obtenu en comptant les arêtes associées à chaque sommet, d’après les amitiés données.

Étape 3 : identifier chemins et cycles.

Un chemin entre Alice et Dave peut être : Alice → Bob → Dave.

Le graphe ne contient aucun cycle, car il n’existe pas de chemin revenant au sommet de départ sans repasser par une arête.

Étape 4 : trouver la centralité.

Alice et Bob sont centraux dans ce réseau, car chacun est connecté à deux autres sommets. Carol et Dave sont moins centraux, chacun étant connecté à un seul autre sommet.

Conclusion

La théorie des graphes offre un cadre robuste pour examiner et résoudre des relations et structures complexes présentes dans de nombreux domaines. En comprenant les notions clés comme les sommets, les arêtes et les différents types de graphes, puis en explorant leurs applications, vous pouvez optimiser des systèmes et résoudre des problèmes concrets.

À mesure que vous approfondissez le sujet, gardez en tête que ces principes ne sont pas qu’académiques : ils sont essentiels pour relever des défis réels, renforcer la connectivité et améliorer l’efficacité des systèmes. Une bonne maîtrise de la théorie des graphes développera vos capacités de résolution de problèmes et vous donnera un regard plus fin sur l’interconnexion des systèmes qui nous entourent.

Pour aller plus loin, explorez ces ressources avancées qui prolongent ce que nous avons couvert dans cet article : 

• Introduction complète aux Graph Neural Networks (GNNs) 
• Optimisation de graphes avec NetworkX en Python
• Tutoriel : classification par arbres de décision en Python