Graphes et Matrices

Un graphe est constitué d'un ensemble fini de sommets et d'un ensemble d'arêtes, chaque arête reliant deux sommets. Deux sommets reliés par une arête sont dits adjacents.

• L'ordre du graphe est son nombre de sommets.
• Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes.
• Un graphe est complet si deux sommets quelconques sont toujours adjacents.
• Une chaîne est une suite de sommets consécutivement adjacents ; sa longueur est son nombre d'arêtes. Un graphe est connexe si deux sommets quelconques sont toujours reliés par une chaîne.

Dans un graphe orienté, les arêtes (appelées arcs) ont un sens ; dans un graphe pondéré, chaque arête porte un nombre (distance, coût, probabilité...).

Une matrice de taille $n\times p$ est un tableau de nombres réels à $n$ lignes et $p$ colonnes. On note $a_{ij}$ le coefficient situé à la ligne $i$ et la colonne $j$. Une matrice est carrée si $n=p$, ligne si $n=1$, colonne si $p=1$. La matrice identité $I_n$ est la matrice carrée avec des $1$ sur la diagonale et des $0$ ailleurs.

• Somme (matrices de même taille) et multiplication par un réel : coefficient par coefficient.
• Produit : si $A$ est de taille $n\times p$ et $B$ de taille $p\times q$, le produit $AB$ est la matrice $n\times q$ de coefficients :

$$(AB{)}_{ij}=\sum _{k=1}^p{a}_{ik}{b}_{kj}$$

(ligne $i$ de $A$ « contre » colonne $j$ de $B$). Attention : en général $AB\ne BA$.

• Puissances d'une matrice carrée : $A^n=A\times A\times \cdots \times A$ ($n$ facteurs), avec $A^0=I$.

Une matrice carrée $A$ est inversible s'il existe une matrice $A^{-1}$ (l'inverse) telle que :

$$A{A}^{-1}=A^{-1}A=I$$