Validateur de séquence de degrés de graphe

Bienvenue sur le validateur de séquence de degrés de graphe, un outil puissant qui utilise l'algorithme de Havel-Hakimi pour déterminer si une séquence donnée d'entiers non négatifs peut former un graphe simple non orienté. Cet outil propose une visualisation animée étape par étape de l'algorithme, un rendu de graphe interactif pour les séquences valides et une matrice d'adjacence complète — ce qui en fait un outil idéal pour les étudiants, les enseignants et les chercheurs en théorie des graphes et en mathématiques discrètes.

Qu'est-ce qu'une séquence de degrés ?

En théorie des graphes, une séquence de degrés est une séquence monotone non croissante des degrés des sommets d'un graphe. Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes. Par exemple, dans un triangle (3 sommets, 3 arêtes), chaque sommet a un degré de 2, la séquence de degrés est donc (2, 2, 2).

Une séquence de degrés est dite graphique s'il existe au moins un graphe simple (sans boucles ni arêtes multiples) dont les degrés des sommets correspondent à cette séquence. Toutes les séquences d'entiers non négatifs ne sont pas graphiques — par exemple, (3, 1, 1) n'est pas graphique car un sommet nécessiterait 3 connexions alors qu'il n'existe que 2 autres sommets.

L'algorithme de Havel-Hakimi

L'algorithme de Havel-Hakimi (nommé d'après Václav Havel et Samuel Louis Hakimi) est un algorithme récursif qui détermine si une séquence finie d'entiers non négatifs donnée est graphique. C'est l'un des algorithmes les plus élégants des mathématiques discrètes.

Étapes de l'algorithme

Théorème de Havel-Hakimi

Le lemme des poignées de main

Une condition préalable fondamentale pour toute séquence de degrés est le lemme des poignées de main :

Ceci implique immédiatement que la somme d'une séquence de degrés doit être paire. Si la somme est impaire, la séquence ne peut absolument pas être graphique — aucune réalisation de graphe n'existe.

Théorème d'Erdős-Gallai

Une caractérisation alternative des séquences graphiques est donnée par le théorème d'Erdős-Gallai :

Bien que le théorème d'Erdős-Gallai donne une caractérisation sous forme fermée, l'algorithme de Havel-Hakimi est souvent préféré en pratique pour sa simplicité et le fait qu'il construit de manière constructive le graphe.

Comment utiliser cet outil

1. Entrez une séquence de degrés : Tapez une liste d'entiers non négatifs séparés par des virgules ou des espaces. Utilisez les exemples rapides pour commencer.
2. Cliquez sur Valider : L'outil vérifie la condition de parité et exécute l'algorithme de Havel-Hakimi.
3. Regardez l'animation : Utilisez les commandes d'étape (Lecture, Suivant, Tout afficher, Réinitialiser) pour visualiser chaque itération de l'algorithme.
4. Explorez le résultat : Pour les séquences graphiques, visualisez un rendu d'exemple du graphe et sa matrice d'adjacence.

Comprendre les résultats

• Verdict : Indique si la séquence est graphique (peut former un graphe simple) ou non.
• Vérification de parité : Indique si la somme des degrés est paire (une condition nécessaire).
• Étapes de l'algorithme : Chaque itération de Havel-Hakimi avec un suivi des éléments par code couleur.
• Visualisation du graphe : Un exemple de graphe simple qui réalise la séquence de degrés (si elle est graphique).
• Matrice d'adjacence : La représentation matricielle 0/1 du graphe d'exemple.

Applications des séquences de degrés

Conception de réseaux

Lors de la conception de réseaux de communication ou de transport, les ingénieurs doivent savoir si un modèle de connectivité souhaité est réalisable. La validation de la séquence de degrés garantit que la topologie du réseau prévue est réalisable avant d'engager des ressources.

Analyse des réseaux sociaux

En sciences sociales, les chercheurs modélisent les réseaux sociaux sous forme de graphes. La séquence de degrés décrit la distribution des connexions. Valider si une distribution de degrés observée peut former un réseau simple aide dans les études de modélisation et de simulation.

Bioinformatique

Les réseaux d'interaction protéique et les réseaux de régulation génique sont modélisés comme des graphes. L'analyse des séquences de degrés aide les chercheurs à comprendre les propriétés des réseaux et à générer des graphes aléatoires avec la même distribution de degrés pour les tests de modèles nuls.

Enseignement de la conception d'algorithmes

L'algorithme de Havel-Hakimi est une pierre angulaire des cours de mathématiques discrètes. Il démontre des concepts clés : algorithmes gloutons, induction et réalisation de graphes. Cet outil aide les étudiants à visualiser et à comprendre chaque étape de l'algorithme.

Foire aux questions

Qu'est-ce qu'une séquence de degrés en théorie des graphes ?

Une séquence de degrés est une liste d'entiers non négatifs qui représente le nombre d'arêtes connectées à chaque sommet d'un graphe. Par exemple, la séquence (3, 2, 2, 1) signifie qu'un sommet a 3 arêtes, deux sommets ont 2 arêtes chacun, et un sommet a 1 arête. Une séquence de degrés valide (graphique) doit avoir une somme paire, puisque chaque arête contribue pour 2 au degré total.

Qu'est-ce que l'algorithme de Havel-Hakimi ?

L'algorithme de Havel-Hakimi est une méthode récursive pour déterminer si une séquence finie d'entiers non négatifs peut être la séquence de degrés d'un graphe simple. Il fonctionne en triant répétitivement la séquence par ordre décroissant, en supprimant le plus grand élément d, puis en soustrayant 1 aux d éléments suivants. Si le processus aboutit à une liste de zéros, la séquence est graphique ; si un nombre négatif apparaît ou si d dépasse le nombre d'éléments restants, elle ne l'est pas.

Que signifie qu'une séquence est graphique ?

Une séquence d'entiers non négatifs est dite graphique s'il existe un graphe simple et non orienté (sans boucles ni arêtes multiples) dont les sommets ont précisément ces degrés. Par exemple, (2, 2, 2) est graphique car elle peut former un triangle, tandis que (3, 1, 1) n'est pas graphique car un sommet ne peut pas se connecter à 3 autres s'il n'existe que 2 autres sommets.

Pourquoi la somme d'une séquence de degrés doit-elle être paire ?

C'est une conséquence du lemme des poignées de main, qui stipule que la somme des degrés de tous les sommets de n'importe quel graphe est égale à deux fois le nombre d'arêtes. Comme le double de n'importe quel entier est pair, la somme de la séquence de degrés doit être paire. C'est une condition nécessaire (mais pas suffisante) pour qu'une séquence soit graphique.

Qu'est-ce que le théorème d'Erdős-Gallai ?

Le théorème d'Erdős-Gallai fournit un ensemble d'inégalités qu'une séquence non croissante d'entiers non négatifs doit satisfaire pour être graphique. Une séquence d1 >= d2 >= ... >= dn est graphique si et seulement si sa somme est paire et si pour chaque k de 1 à n, la somme des k premiers termes est inférieure ou égale à k(k-1) plus la somme des min(dk, k) sur les termes restants. L'algorithme de Havel-Hakimi est souvent préféré en pratique car il est plus simple à implémenter.

Ressources additionnelles

• Théorème d'Erdős–Gallai - Wikipédia
• Algorithme de Havel-Hakimi - Wikipédia