Matrice d'adjacence

En mathématiques, une matrice d'adjacence pour un graphe fini G à n sommets est une matrice de dimension n × n dont l'élément non-diagonal a ij est le nombre d'arêtes liant le sommet i au sommet j.



Catégories :

Structure de données en théorie des graphes - Matrice remarquable - Probabilités

Page(s) en rapport avec ce sujet :

  • Un élément de la matrice d'adjacence est 1 si l'arc existe et 0 sinon. Pour des graphes dont les arcs sont valués la valeur à l'intersection d'i et j est ... (source : brassens.upmf-grenoble)
  • La représentation par matrice d'adjacence consiste en l'utilisation d'une matrice carré ayant pour taille le nombre de sommets du graphe.... (source : rperrot.developpez)

En mathématiques, une matrice d'adjacence pour un graphe fini G à n sommets est une matrice de dimension n × n dont l'élément non-diagonal aij est le nombre d'arêtes liant le sommet i au sommet j. L'élément diagonal aii est le nombre de boucles au sommet i (ou deux fois ce nombre, selon certains usages).

Cet outil mathématique est particulièrement utilisé en informatique, mais intervient aussi naturellement dans les chaînes de Markov. Surtout, la probabilité limite s'interprète comme un vecteur propre.

Définition

Supposez que G = (V, E) est un graphe simple, où \left|V\right|=n. Supposez aussi que les sommets de G sont , arbitrairement, v_1,\ldots,v_n. La matrice d'adjacence A de G se rapportant à cet ensemble de sommets est la matrice n\times n booléenne A avec

a_{ij}=\left\{\begin{array}{rl}
	1 & \mbox{si } (v_i,v_j)\in E \\
        0 & \mbox{sinon.}
\end{array}\right.

Une matrice d'adjacence d'un graphe est fondée sur la relation d'ordre établie pour les sommets.

Donc, il existe (au plus) n! matrices d'adjacences différentes pour un graphe comportant n sommets dans la mesure où il y a n! possibilités d'ordonner ces sommets.

Propriétés

Une fois qu'on fixe l'ordre des sommets, il existe une matrice d'adjacence unique pour chaque graphe. Celle-ci n'est la matrice d'adjacence d'aucun autre graphe. Dans le cas spécifique d'un graphe simple et fini, la matrice d'adjacence est une matrice binaire avec des zéros sur la diagonale. Si le graphe n'est pas orienté, la matrice d'adjacence est symétrique, ce qui veut dire que aij = aji.

Exemple

La matrice d'adjacence du graphe étiqueté suivant

6n-graph2.svg

est

\begin{pmatrix}
1 & 1 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1\\
1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
\end{pmatrix}.

Remarque

Si A est la matrice d'adjacence d'un graphe fini G dont les sommets sont numérotés de 1 à n, le nombre de chemins de longueur précisément k allant de i à j est le cœfficient en position (i, j) de la matrice Ak — ceci si chaque arrête entre deux sommets a une longueur égale à 1.

Voir aussi

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Matrice_d%27adjacence.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu