$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Matrice d'adjacence d'un graphe

Graphe non-orienté
  Soit G un graphe non-orienté qui possède n sommets numérotés de 1 à n. On appelle matrice d'adjacence du graphe la matrice A=(ai,j) où ai,j est le nombre d'arêtes joignant le sommet i au sommet j.

Exemple : Voici un graphe, et la matrice d'adjacence correspondante :
On peut remarque que cette matrice est symétrique. C'est le cas pour toutes les matrices d'adjacence d'un graphe non-orienté. Le résultat principal concernant les matrices d'adjacence est le théorème suivant :
Théorème : Soit G un graphe non-orienté de matrice d'adjacence A. Le nombre de chaines de longueur n joignant le sommet i au sommet j est donné par le terme d'indice i,j de la matrice An.
Graphe orienté
  On peut également définir la matrice d'adjacence d'un graphe orienté. Cette fois, le coefficient ai,j désigne le nombre d'arcs d'origine i et d'extrémité j.

Exemple : Pour le graphe suivant,
on trouve la matrice d'adjacence
$$\left( \begin{array}{cccc} 0& 0& 1& 1\\ 1& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 1& 0& 0 \end{array} \right).$$
Cette matrice n'est plus symétrique. En revanche, le terme d'indice (i,j) de la matrice An compte toujours le nombre de chemins allant de i vers j.
Consulter aussi...