Calculateur de Matrice d'Adjacence

Calculateur de Matrice d'Adjacence

Le Calculateur de Matrice d'Adjacence est un utilitaire de théorie des graphes qui convertit entre les trois représentations de graphes canoniques — matrice d'adjacence, liste d'arêtes et liste d'adjacence — et enrichit le résultat avec une analyse structurelle : séquence de degrés, densité du graphe, composantes connexes et puissances de matrice. Il détecte automatiquement si votre saisie décrit un graphe orienté ou non orienté et affiche une visualisation SVG interactive à côté de chaque résultat.

Qu'est-ce qu'une matrice d'adjacence ?

Étant donné un graphe G = (V, E) à n sommets, sa matrice d'adjacence est la matrice carrée n × n A dont l'entrée A[i][j] est 1 s'il existe une arête du sommet i au sommet j, et 0 sinon.

Pour un graphe non orienté, la matrice d'adjacence est toujours symétrique : chaque arête {u, v} contribue à la fois à A[u][v] = 1 et A[v][u] = 1. Pour un graphe orienté (digraphe), la matrice peut être asymétrique, reflétant la direction de chaque arc.

Trois représentations — Choisissez celle qui convient à votre problème

Métriques clés calculées

Séquence de degrés

Pour les graphes non orientés, le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes (les boucles comptant deux fois). Pour les graphes orientés, chaque sommet a un demi-degré intérieur (arcs entrants) et un demi-degré extérieur (arcs sortants). La liste triée des degrés est un invariant de graphe classique utilisé dans les tests d'isomorphisme et le théorème d'Erdős–Gallai.

Densité du graphe

La densité mesure à quel point un graphe est "rempli" par rapport au nombre maximum d'arêtes possibles sur n sommets.

Une densité de 0 signifie aucune arête, 1 signifie que le graphe est complet, et les valeurs inférieures à 0,1 indiquent généralement un graphe creux où une liste d'adjacence est plus efficace en termes d'espace qu'une matrice.

Composantes connexes

Une composante connexe est un sous-ensemble maximal de sommets tel que chaque paire est reliée par un chemin. Pour les graphes orientés, ce calculateur indique les composantes faiblement connexes (en ignorant la direction des flèches) — les mêmes sous-ensembles que vous obtiendriez en traitant chaque arc comme une arête non orientée.

Puissances de matrice (A², A³ ... )

Un théorème fondamental de la théorie algébrique des graphes stipule que l'entrée (i, j) de A^k est égale au nombre de chemins de longueur exactement k du sommet i au sommet j. Par conséquent :

• A²[i][i] est égal au degré du sommet i (non orienté), car un chemin de longueur 2 de i à lui-même consiste à "aller vers un voisin et revenir".
• La trace de A³ divisée par 6 compte les triangles dans un graphe non orienté.
• Le fait que Aⁿ⁻¹ ait ou non une entrée nulle vous indique si le graphe est connexe.

Formats d'entrée acceptés

1. Liste d'arêtes

Une arête par ligne ou séparée par des virgules. N'importe lequel de ces séparateurs fonctionne : A-B, A B, A,B, A->B, A--B. Utilisez -> si vous souhaitez forcer une interprétation orientée.

2. Liste d'adjacence

Une ligne par sommet, sous la forme sommet: voisin1, voisin2, .... L'ordre n'a pas d'importance ; les sommets manquants sont ajoutés automatiquement à partir des listes de voisins.

3. Matrice d'adjacence

Une ligne par rangée avec des valeurs 0/1 séparées par des espaces ou des virgules. La matrice doit être carrée. Vous pouvez éventuellement fournir des étiquettes personnalisées dans le champ Étiquettes de matrice (sinon A, B, C… sont utilisés).

Comment utiliser ce calculateur

1. Choisissez un format d'entrée à l'aide du sélecteur par onglets : liste d'arêtes, liste d'adjacence ou matrice d'adjacence.
2. Collez ou tapez votre graphe dans la zone de texte. Pour la saisie de matrice, ajoutez des étiquettes facultatives dans le champ Étiquettes de matrice.
3. Sélectionnez le type de graphe — laissez sur Détection automatique et le calculateur déduira l'orientation à partir des flèches (->) ou de la symétrie de la matrice. Forcez sur Orienté ou Non orienté si vous souhaitez passer outre.
4. Cliquez sur Convertir et Analyser le Graphe. La page de résultat affiche la matrice d'adjacence, un rendu SVG interactif, les deux autres représentations textuelles, les statistiques de degrés, les composantes connexes et les matrices de nombre de chemins A² et A³ lorsque le graphe est suffisamment petit.
5. Survolez une ligne de matrice ou un nœud de graphe pour éclairer la ligne/colonne correspondante et les arêtes incidentes — une preuve visuelle instantanée que chaque format code les mêmes informations.

Exemple pratique

Considérons un graphe non orienté sur les sommets {A, B, C, D} avec les arêtes AB, BC, CA, CD. La matrice d'adjacence est :

Faits clés dérivés par le calculateur :

• Symétrique ? Oui — confirme le type non orienté.
• Séquence de degrés : (3, 2, 2, 1) — le sommet C est le moyeu.
• Densité : 2·4 / (4·3) = 0,667 — un graphe modérément dense.
• Connexe ? Oui, composante unique.
• Triangles : exactement un (A–B–C), comme le confirme tr(A³) = 6.

Applications courantes

• Analyse des réseaux sociaux — graphes d'amitié / d'abonnés, centralité.
• Graphes Web et de citation — PageRank et HITS travaillent directement sur A et A^T.
• Routage et réseaux — chemin le plus court, coupe minimale, flux maximal.
• Chimie — graphes moléculaires avec des atomes comme sommets et des liaisons comme arêtes.
• Planification et résolution de dépendances — graphes orientés acycliques (DAG) dans les systèmes de construction.
• Chaînes de Markov — les matrices stochastiques par ligne dérivées de graphes codent les probabilités de transition.

Foire aux questions

Qu'est-ce qu'une matrice d'adjacence ?

Une matrice d'adjacence est une matrice carrée n × n utilisée pour représenter un graphe fini. Chaque cellule A[i][j] est 1 s'il existe une arête du sommet i au sommet j, et 0 sinon. Pour les graphes non orientés, la matrice est symétrique, donc A[i][j] = A[j][i]. La matrice permet de vérifier facilement si deux sommets sont connectés en temps constant, et les puissances de la matrice codent le nombre de chemins entre les sommets.

Comment savoir si un graphe est orienté à partir de sa matrice d'adjacence ?

Si la matrice d'adjacence est symétrique, c'est-à-dire que A[i][j] est égal à A[j][i] pour chaque paire d'indices, le graphe est non orienté. S'il existe au moins une paire où A[i][j] diffère de A[j][i], le graphe est orienté. Ce calculateur effectue automatiquement ce contrôle de symétrie lorsque vous choisissez l'option Détection automatique.

Que représente la k-ième puissance d'une matrice d'adjacence ?

L'entrée (i, j) de A^k compte le nombre de chemins d'une longueur exactement k du sommet i au sommet j. Par exemple, A²[i][j] est le nombre de chemins en 2 étapes, ce qui équivaut au nombre de voisins communs entre i et j dans les graphes non orientés. Cette propriété est utilisée dans les algorithmes de comptage de triangles, d'accessibilité et les calculs de type PageRank.

Qu'est-ce que la densité d'un graphe ?

La densité d'un graphe est le rapport entre le nombre d'arêtes présentes et le nombre maximum d'arêtes possibles. Pour un graphe simple non orienté à n sommets, densité = 2m / (n(n-1)). Pour un graphe orienté, densité = m / (n(n-1)). Une densité proche de 0 signifie un graphe creux ; une densité de 1 signifie un graphe complet.

Quelle est la différence entre une matrice d'adjacence et une liste d'adjacence ?

Une matrice d'adjacence stocke la connectivité pour chaque paire de sommets en utilisant n² bits, ce qui rend la recherche de voisins O(1) mais l'utilisation de la mémoire O(n²). Une liste d'adjacence ne stocke que les voisins réels de chaque sommet, ce qui donne une mémoire O(n + m), bien plus petite pour les graphes creux, mais la recherche de voisins nécessite un balayage linéaire. Les matrices sont préférables pour les graphes denses et les opérations d'algèbre matricielle ; les listes sont préférables pour les graphes creux et les algorithmes de parcours comme BFS/DFS.

Cet outil peut-il gérer les graphes pondérés ?

Le calculateur actuel se concentre sur les matrices d'adjacence non pondérées avec des entrées 0/1. Si vous collez une matrice avec des poids numériques non nuls, chaque cellule non nulle est traitée comme un 1 pour l'analyse structurelle. Pour les calculs de graphes pondérés tels que le chemin le plus court, envisagez un outil dédié aux graphes pondérés.

Lectures complémentaires

• Matrice d'adjacence — Wikipédia
• Séquence de degrés (en anglais) — Wikipedia
• Densité de graphe (en anglais) — Wikipedia
• Composantes connexes — Wikipédia

Opérations mathématiques avancées:

• Calculateur de Matrice d'Adjacence Nouveau
• Calculatrice d'Antilogarithme
• Calculatrice de la fonction bêta
• Calculateur de Coefficient Binomial
• Calculatrice de distribution binomiale
• Calculatrice de Bit Populaire
• Simplificateur d'Algèbre de Boole Nouveau
• Calculateur du Théorème Central Limite
• Calculatrice du Théorème des Restes Chinois
• Calculatrice de Combinaison Populaire
• Calculatrice de Fonction d'Erreur Complémentaire
• Calculatrice de Nombres Complexes
• Calculatrice de fractions continues
• Calculateur de Dérangement (Sous-factorielle)
• Calculateur de plus court chemin de Dijkstra
• Calculatrice d'Entropie
• Calculatrice de fonction d'erreur
• Calculatrice de la fonction indicatrice d'Euler
• Calculatrice de désintégration exponentielle
• Calculatrice de croissance exponentielle
• Calculatrice d'intégrale exponentielle
• Calculatrice des Exposants (Haute Précision) Populaire
• Calculatrice de l'Algorithme Euclidien Étendu
• Calculatrice Factorielle
• Calculatrice de Fonction Gamma
• Calculateur de Nombre d'Or
• Calculateur de Coloration de Graphes Nouveau
• Validateur de séquence de degrés de graphe
• Calculateur d'Ordre en Théorie des Groupes Nouveau
• Calculatrice de demi-vie
• Vérificateur de Chemin Hamiltonien Nouveau
• Calculateur d'Inclusion-Exclusion Nouveau
• Solveur de Tableau de Karnaugh (K-Map) Nouveau
• Solveur de Programmation Linéaire Nouveau
• Calculateur d'état stationnaire de chaîne de Markov
• Calculateur d'arbre couvrant minimum
• Calculateur d'Exponentiation Modulaire Nouveau
• Calculatrice de l'Inverse Multiplicatif Modulaire
• Calculateur de Distribution Binomiale Négative Nouveau
• Calculateur de Flot Maximal dans un Réseau Nouveau
• Calculatrice du Taux de Croissance en Pourcentage Populaire
• Calculatrice de permutation
• Calculateur de Permutations avec Répétition Nouveau
• Calculateur du principe des tiroirs
• Vérificateur de Graphe Planaire Nouveau
• Calculatrice de Distribution de Poisson
• Calculatrice des racines de polynômes avec étapes détaillées
• Calculateur de Racine Primitive
• Calculatrice de probabilité
• Calculatrice de Distribution de Probabilité
• Calculatrice de Proportion
• Calculatrice de Formule Quadratique Populaire
• Calculateur d’Anneaux et de Corps Nouveau
• Calculateur d'Arrondi Nouveau
• Calculatrice Scientifique
• Calculatrice de notation scientifique
• Calculateur de Théorie des Ensembles
• Calculateur de Chiffres Significatifs Nouveau
• Solveur du Problème des Mariages Stables Nouveau
• Calculateur de Nombres de Stirling
• Calculatrice de Somme de Cubes
• Calculatrice de la somme des entiers positifs
• Calculatrice de la somme des carrés
• Calculateur de Tri Topologique Nouveau
• Solveur du Voyageur de Commerce (TSP) Nouveau
• Générateur de table de vérité
• Générateur de Diagramme de Venn (3 Ensembles)