Graphes et matrices

Un graphe $G$ est formellement défini par un couple $(V, E)$, où $V$ est un ensemble de sommets (ou nœuds) et $E$ est un ensemble d'arêtes (ou liens) reliant ces sommets.

• Sommets (ou Nœuds) : Ce sont les "objets" de notre système. On les représente souvent par des points.
  • Exemple : Dans un réseau routier, les villes sont les sommets.
• Arêtes (ou Liens) : Ce sont les "relations" entre les sommets. On les représente par des lignes.
  • Exemple : Dans un réseau routier, les routes sont les arêtes.

Il existe plusieurs types de graphes :

• Graphe non orienté : Les arêtes n'ont pas de direction. La relation est symétrique. Si A est lié à B, alors B est lié à A.
  • Exemple : Une amitié sur Facebook est souvent non orientée : si vous êtes ami avec quelqu'un, cette personne est aussi votre amie.
  • Une arête entre $u$ et $v$ est notée $\{u, v\}$.
• Graphe orienté (ou digraphe) : Les arêtes ont une direction. La relation n'est pas nécessairement symétrique. Si A pointe vers B, B ne pointe pas forcément vers A.
  • Exemple : Les followers sur Instagram : vous pouvez suivre quelqu'un sans que cette personne vous suive en retour.
  • Une arête orientée (ou arc) de $u$ vers $v$ est notée $(u, v)$. $u$ est l'origine et $v$ est l'extrémité.
• Boucle : Une arête qui relie un sommet à lui-même.
  • Exemple : Un site web qui contient un lien vers lui-même.
• Arêtes multiples (ou parallèles) : Plusieurs arêtes reliant la même paire de sommets.
  • Exemple : Deux routes différentes entre deux mêmes villes.

Un graphe est une modélisation de relations entre objets.

Comment représenter un graphe de manière pratique pour l'étudier ou le manipuler informatiquement ?

1. Dessin de graphe : C'est la représentation la plus intuitive. Les sommets sont des points ou des cercles, les arêtes sont des lignes (avec des flèches pour les graphes orientés).

   • Avantage : Très visuel, facile à comprendre.
   • Inconvénient : Difficile à utiliser pour de grands graphes ou pour des calculs.

2. Liste d'adjacence : Pour chaque sommet, on liste les sommets auxquels il est connecté.

   • Pour un graphe non orienté : Chaque sommet $u$ a une liste de ses voisins.
     • Exemple : $V = \{A, B, C, D\}$, $E = \{\{A,B\}, \{A,C\}, \{B,C\}, \{C,D\}\}$
     • $A: [B, C]$
     • $B: [A, C]$
     • $C: [A, B, D]$
     • $D: [C]$
   • Pour un graphe orienté : Chaque sommet $u$ a une liste de ses successeurs (les sommets vers lesquels il y a un arc).
     • Avantage : Efficace pour les graphes "creux" (avec peu d'arêtes).
     • Inconvénient : Vérifier l'existence d'une arête $(u, v)$ nécessite de parcourir la liste de $u$.

3. Matrice d'adjacence : Une matrice carrée $A$ de taille $N \times N$ (où $N$ est le nombre de sommets). L'élément $A_{ij}$ vaut 1 s'il y a une arête (ou un arc) du sommet $i$ vers le sommet $j$, et 0 sinon.

   • Pour un graphe non orienté sans boucles ni arêtes multiples, la matrice est symétrique ($A_{ij} = A_{ji}$).
   • Exemple (graphe non orienté ci-dessus) : $$A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$
   • Avantage : Facile pour les calculs matriciels (nous y reviendrons !), vérification rapide de l'existence d'une arête.
   • Inconvénient : Peut être très grande et contenir beaucoup de zéros pour les graphes creux (peu efficace en mémoire).

4. Matrice d'incidence : Une matrice $M$ de taille $N \times M$ (où $N$ est le nombre de sommets et $M$ le nombre d'arêtes). L'élément $M_{ij}$ vaut 1 si le sommet $i$ est une extrémité de l'arête $j$, et 0 sinon. Pour les graphes orientés, on peut utiliser -1 pour l'origine et 1 pour l'extrémité.

   • Avantage : Utile pour certains problèmes spécifiques (ex: flot).
   • Inconvénient : Moins courante et souvent moins intuitive que la matrice d'adjacence pour les problèmes de base.

La matrice d'adjacence est une représentation clé pour les calculs.

Pour décrire et analyser les graphes, nous utilisons un vocabulaire précis :

• Degré d'un sommet :

  • Pour un graphe non orienté, le degré d'un sommet est le nombre d'arêtes incidentes à ce sommet.
    • Exemple : Dans le graphe précédent, $deg(A)=2$, $deg(B)=2$, $deg(C)=3$, $deg(D)=1$.
  • Pour un graphe orienté, on distingue :
    • Degré entrant (degré intérieur) : Nombre d'arcs ayant ce sommet comme extrémité.
    • Degré sortant (degré extérieur) : Nombre d'arcs ayant ce sommet comme origine.
  • Propriété : La somme des degrés de tous les sommets d'un graphe non orienté est égale à deux fois le nombre d'arêtes (chaque arête relie deux sommets, et est donc comptée deux fois).

• Chemin : Une séquence de sommets connectés par des arêtes. Dans un graphe orienté, on parle de chemin orienté ou chemin.

  • Exemple : Dans le graphe non orienté précédent, $A - C - D$ est un chemin.
  • Un chemin est défini par une suite de sommets $v_0, v_1, \dots, v_k$ telle que $(v_i, v_{i+1})$ est une arête (ou $\{v_i, v_{i+1}\}$ pour un non orienté) pour tout $i$ de $0$ à $k-1$.

• Cycle : Un chemin qui commence et se termine au même sommet, sans repasser deux fois par la même arête. Dans un graphe orienté, on parle de circuit.

  • Exemple : $A - B - C - A$ est un cycle.

• Graphe connexe : Un graphe non orienté est connexe si, pour toute paire de sommets $(u, v)$, il existe un chemin entre $u$ et $v$. En d'autres termes, le graphe est d'un seul tenant.

  • Exemple : Un réseau routier où l'on peut aller de n'importe quelle ville à n'importe quelle autre.

• Composante connexe : Une sous-partie maximale d'un graphe non orienté qui est connexe. Un graphe non connexe est composé de plusieurs composantes connexes.

  • Exemple : Si un pont s'effondre, un pays peut être divisé en deux composantes connexes de villes.

• Chemin (orienté) : Dans un graphe orienté, un chemin est une succession d'arcs $(v_0, v_1), (v_1, v_2), \dots, (v_{k-1}, v_k)$. Il est noté $v_0 \to v_1 \to \dots \to v_k$.
  • Exemple : Si un graphe représente des liens hypertextes, un chemin est une suite de clics.
• Chaîne (non orientée) : Dans un graphe non orienté, une chaîne est une succession d'arêtes $\{v_0, v_1\}, \{v_1, v_2\}, \dots, \{v_{k-1}, v_k\}$. Il est noté $v_0 - v_1 - \dots - v_k$.
  • Exemple : Une suite de routes empruntées entre des villes.
• Longueur d'un chemin/chaîne : C'est le nombre d'arêtes (ou d'arcs) qui le composent.
  • Exemple : Le chemin $A \to C \to D$ a une longueur de 2.
• Chemin simple / Chaîne simple : Un chemin (ou une chaîne) est dit simple s'il ne passe pas deux fois par le même sommet.
  • Attention : S'il ne passe pas deux fois par la même arête, on parle de chemin/chaîne élémentaire. Un chemin simple est toujours élémentaire.

La longueur d'un chemin est le nombre d'arêtes qu'il contient.

• Cycle (non orienté) : Une chaîne simple (ne passant pas deux fois par le même sommet, sauf le premier et le dernier qui sont identiques) dont le premier et le dernier sommet sont identiques.
  • Exemple : $A - B - C - A$ est un cycle de longueur 3.
• Circuit (orienté) : Un chemin simple (ne passant pas deux fois par le même sommet, sauf le premier et le dernier qui sont identiques) dont le premier et le dernier sommet sont identiques.
  • Exemple : Dans un graphe orienté, $A \to B \to C \to A$ est un circuit.
• Graphe acyclique : Un graphe qui ne contient aucun cycle (ni circuit).
  • Exemple : Un organigramme hiérarchique est souvent un graphe orienté acyclique (DAG - Directed Acyclic Graph).
• Arbre : Un graphe non orienté, connexe et acyclique. Un arbre avec $N$ sommets a toujours $N-1$ arêtes. Il n'y a qu'une seule chaîne entre deux sommets quelconques.
  • Exemple : L'arborescence des dossiers sur un ordinateur.

• Distance entre deux sommets : La longueur du plus court chemin (ou de la plus courte chaîne) entre deux sommets $u$ et $v$. Si aucun chemin n'existe, la distance est considérée comme infinie. On la note $d(u, v)$.
  • Exemple : Si $A-B-C-D$ et $A-E-D$, la distance entre $A$ et $D$ est 2 si les arêtes ont un poids de 1.
• Diamètre d'un graphe : C'est la plus grande des distances entre toutes les paires de sommets du graphe.
  • Utilité : Mesure la "taille" ou l'étendue maximale d'un graphe.
• Graphe fortement connexe (pour les graphes orientés) : Un graphe orienté est fortement connexe si pour toute paire de sommets $(u, v)$, il existe un chemin de $u$ vers $v$ ET un chemin de $v$ vers $u$.
  • Attention : Être fortement connexe est une condition beaucoup plus forte qu'être juste connexe pour un graphe orienté (ce dernier signifiant que le graphe sous-jacent non orienté est connexe).
• Graphe connexe par chemins (pour les graphes orientés) : On dit qu'un graphe orienté est connexe par chemins si pour toute paire de sommets $(u, v)$, il existe un chemin de $u$ vers $v$. C'est une définition moins stricte que fortement connexe.

Nous avons déjà introduit la matrice d'adjacence. Revoyons-la en détail.

• Construction de la matrice d'adjacence ($A$) :

  • Pour un graphe à $N$ sommets, c'est une matrice $N \times N$.
  • $A_{ij} = 1$ s'il y a une arête (ou un arc) du sommet $i$ vers le sommet $j$.
  • $A_{ij} = 0$ sinon.
  • Pour les graphes avec arêtes multiples, $A_{ij}$ peut représenter le nombre d'arêtes entre $i$ et $j$.
  • Pour les boucles, $A_{ii}$ peut être 1 (ou le nombre de boucles).

• Interprétation des coefficients :

  • $A_{ij} = 1$ signifie que $j$ est un voisin (ou successeur) direct de $i$.
  • $A_{ij} = 0$ signifie qu'il n'y a pas de connexion directe.

• Propriétés pour graphes orientés/non orientés :

  • Graphe non orienté : La matrice d'adjacence est symétrique, c'est-à-dire $A^T = A$. (Si $A_{ij}=1$, alors $A_{ji}=1$).
  • Graphe orienté : La matrice n'est pas nécessairement symétrique. $A_{ij}=1$ n'implique pas $A_{ji}=1$.
  • La somme des éléments d'une ligne $i$ dans un graphe orienté donne le degré sortant du sommet $i$.
  • La somme des éléments d'une colonne $j$ dans un graphe orienté donne le degré entrant du sommet $j$.
  • Pour un graphe non orienté (sans boucles), la somme des éléments d'une ligne (ou colonne) $i$ donne le degré du sommet $i$.

• Matrice d'adjacence pour graphes pondérés :

  • Dans un graphe pondéré, chaque arête (ou arc) a un poids (ou coût, ou capacité).
  • La matrice d'adjacence $W$ est alors construite en mettant $W_{ij}$ égal au poids de l'arête $(i, j)$ s'il en existe une, et $\infty$ (ou 0 selon le contexte) sinon.
  • Exemple : Les distances entre villes sur un réseau routier.
  • $$W = \begin{pmatrix} 0 & 5 & \infty & \infty \\ \infty & 0 & 2 & \infty \\ 1 & \infty & 0 & 7 \\ \infty & \infty & \infty & 0 \end{pmatrix}$$

La matrice d'adjacence est symétrique pour un graphe non orienté.

C'est ici que la puissance du calcul matriciel se révèle !

• Calcul de $A^n$ : La $n$-ième puissance de la matrice d'adjacence $A$ est obtenue en multipliant $A$ par elle-même $n$ fois ($A \times A \times \dots \times A$).

• Interprétation de $(A^n)_{ij}$ : L'élément $(A^n)_{ij}$ de la matrice $A^n$ représente le nombre de chemins de longueur $n$ allant du sommet $i$ au sommet $j$.

  • Explication intuitive :
    • $A_{ij}$ donne le nombre de chemins de longueur 1 de $i$ à $j$.
    • $(A^2)_{ij} = \sum_k A_{ik} A_{kj}$. Chaque terme $A_{ik} A_{kj}$ vaut 1 si il y a un chemin $i \to k$ ET un chemin $k \to j$, soit un chemin de longueur 2 $i \to k \to j$. La somme compte tous ces chemins de longueur 2 via un sommet intermédiaire $k$.
    • Par récurrence, on peut généraliser cette idée.

• Nombre de chemins de longueur $n$ : C'est l'application directe de l'interprétation ci-dessus. Si vous voulez savoir combien de façons différentes il y a d'aller de la ville A à la ville B en passant par exactement 3 routes, il suffit de regarder l'élément $(A^3)_{AB}$.

• Application à la connexité :

  • Si $(A^n)_{ij} > 0$ pour un certain $n$, cela signifie qu'il existe au moins un chemin de longueur $n$ de $i$ à $j$.
  • Pour savoir si deux sommets $i$ et $j$ sont connectés (c'est-à-dire s'il existe un chemin entre eux de n'importe quelle longueur), on peut calculer la matrice $S = A + A^2 + \dots + A^{N-1}$ (où $N$ est le nombre de sommets). Si $S_{ij} > 0$, alors $i$ et $j$ sont connectés.
  • Pour un graphe non orienté, le graphe est connexe si la matrice $S$ ne contient que des éléments non nuls (hors diagonale, ou en incluant la diagonale si on considère des chemins de $i$ à $i$).

$(A^n)_{ij}$ donne le nombre de chemins de longueur $n$ de $i$ à $j$.

Les graphes probabilistes sont utilisés pour modéliser des systèmes où les transitions entre états sont régies par des probabilités.

• Définition d'un graphe probabiliste : C'est un graphe orienté et pondéré où les poids des arcs représentent des probabilités de transition. Pour chaque sommet, la somme des probabilités des arcs sortants doit être égale à 1.

  • Exemple : Météo (probabilité de passer de "ensoleillé" à "nuageux"), comportement d'un utilisateur sur un site web (probabilité de passer d'une page à une autre).

• Matrice de transition ($M$) : C'est une matrice carrée où $M_{ij}$ représente la probabilité de passer du sommet $i$ au sommet $j$.

  • Chaque ligne de la matrice $M$ doit sommer à 1 (car la somme des probabilités de transition depuis un état donné doit être 1).
  • Exemple : Deux stations de vélos en libre-service A et B. Chaque jour, 70% des vélos de A restent à A, 30% vont à B. De B, 40% vont à A, 60% restent à B. $$M = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix}$$

• Calcul des états successifs : Si $P_k = (p_1^{(k)}, p_2^{(k)}, \dots, p_N^{(k)})$ est un vecteur ligne représentant la distribution de probabilité des états au temps $k$ (où $p_i^{(k)}$ est la probabilité d'être dans l'état $i$ au temps $k$), alors l'état au temps $k+1$ est donné par : $P_{k+1} = P_k \times M$ Où $P_0$ est l'état initial.

• État stable (ou distribution stationnaire) : Pour de nombreux graphes probabilistes, lorsque $k$ tend vers l'infini, la distribution de probabilité $P_k$ converge vers un état stable $P_{stable}$. Cet état stable satisfait l'équation : $P_{stable} = P_{stable} \times M$ Où la somme des éléments de $P_{stable}$ doit être 1. C'est un vecteur propre de la matrice de transition associé à la valeur propre 1.

  • Utilité : Prédire la répartition à long terme des ressources ou des populations dans le système.
  • Exemple : La répartition des vélos entre les stations A et B à long terme.

• Graphes pondérés : Ici, chaque arête a un poids. L'objectif n'est plus seulement de trouver un chemin, mais le "meilleur" chemin selon un critère (généralement le chemin de poids total minimal).

  • Exemple : Le temps de trajet sur une route, le coût d'un vol, la bande passante d'une connexion réseau.

• Problématique du plus court chemin : Trouver le chemin entre deux sommets (ou un sommet et tous les autres) dont la somme des poids des arêtes est minimale.

• Algorithme de Dijkstra (principe) :

  • C'est l'un des algorithmes les plus connus pour trouver le plus court chemin depuis un sommet source donné vers tous les autres sommets dans un graphe pondéré avec des poids d'arêtes positifs.
  • Principe : Il maintient un ensemble de sommets dont la distance la plus courte depuis la source est déjà connue. À chaque étape, il sélectionne le sommet non visité le plus proche de la source et met à jour les distances de ses voisins.
  • Il utilise une structure de données (souvent une file de priorité) pour gérer les sommets à visiter.
  • Application : Logiciels de navigation GPS, routage de paquets sur internet.

• Application aux réseaux : Essentiel pour optimiser les flux dans les réseaux de transport, de communication, ou les réseaux électriques.

Ces algorithmes visent à visiter systématiquement tous les sommets et arêtes d'un graphe.

• Parcours en largeur (BFS - Breadth-First Search) :

  • Principe : Explore le graphe "couche par couche". Il visite d'abord tous les voisins du sommet de départ, puis tous leurs voisins, et ainsi de suite.
  • Utilise une file (queue) pour stocker les sommets à visiter.
  • Applications : Trouver le plus court chemin en nombre d'arêtes (graphe non pondéré), détecter la connexité, trouver les composantes connexes.

• Parcours en profondeur (DFS - Depth-First Search) :

  • Principe : Explore le graphe "aussi profondément que possible" le long de chaque branche avant de revenir en arrière.
  • Utilise une pile (stack) (ou la récursion) pour stocker les sommets à visiter.
  • Applications : Détection de cycles, tri topologique, trouver des composantes fortement connexes (pour les graphes orientés).

• Applications (détection de connexité, cycles) :

  • BFS peut vérifier si un graphe est connexe en partant d'un sommet et en comptant les sommets atteignables. Si tous les sommets sont atteints, le graphe est connexe.
  • DFS peut détecter la présence de cycles en vérifiant si un sommet déjà visité est rencontré avant de "remonter" dans la pile.

• Complexité des algorithmes :

  • La performance d'un algorithme est mesurée par sa complexité temporelle (combien d'opérations en fonction de la taille du graphe) et sa complexité spatiale (combien de mémoire il utilise).
  • Pour un graphe avec $N$ sommets et $M$ arêtes :
    • BFS et DFS ont une complexité de $O(N+M)$ en utilisant une liste d'adjacence, ou $O(N^2)$ avec une matrice d'adjacence.
    • Dijkstra a une complexité de $O(M \log N)$ avec une file de priorité efficace.

De nombreux problèmes réels peuvent être modélisés comme des problèmes d'optimisation sur les graphes.

• Problème du voyageur de commerce (TSP - Traveling Salesperson Problem) : Trouver le plus court chemin qui visite chaque sommet exactement une fois et revient au sommet de départ.

  • C'est un problème NP-difficile : il n'existe pas d'algorithme efficace connu pour le résoudre pour un grand nombre de sommets. On utilise souvent des heuristiques.
  • Application : Optimisation des tournées de livraison.

• Problème de couverture (Vertex Cover Problem) : Trouver le plus petit ensemble de sommets tel que chaque arête du graphe est incidente à au moins un sommet de cet ensemble.

  • Aussi NP-difficile.

• Coloration de graphes : Attribuer une couleur à chaque sommet de telle sorte que deux sommets adjacents n'aient jamais la même couleur, en utilisant le minimum de couleurs possible.

  • Applications : Planification d'emploi du temps (éviter les conflits), allocation de fréquences radio.

• Notion de complexité algorithmique : Ces problèmes illustrent la classification des problèmes en "faciles" (polynomiaux, P) et "difficiles" (NP-complets, NP-difficiles) en termes de temps de calcul.

• Réseaux sociaux :
  • Les personnes sont des sommets, les amitiés/relations sont des arêtes.
  • Analyse de l'influence, détection de communautés, recommandation d'amis.
  • Exemple : L'algorithme PageRank de Google est basé sur un graphe des pages web.
• Réseaux de transport :
  • Villes/arrêts sont des sommets, routes/lignes sont des arêtes (souvent pondérées par le temps, la distance ou le coût).
  • Calcul d'itinéraires, optimisation du trafic.
• Organigrammes (hiérarchies) :
  • Employés/départements sont des sommets, relations hiérarchiques sont des arcs.
  • Représentation de la structure d'une organisation.
• Flux de données / Réseaux informatiques :
  • Ordinateurs/routeurs sont des sommets, connexions sont des arêtes (avec capacités).
  • Routage de l'information, détection de pannes.

Nous avons déjà abordé les graphes probabilistes et les matrices de transition. Leur application principale est la modélisation des chaînes de Markov.

• Processus stochastiques : Une chaîne de Markov est un processus stochastique qui satisfait la propriété de Markov : l'état futur du système ne dépend que de son état actuel, et non de la séquence d'événements qui l'ont précédé.
• Matrice de transition : Décrit les probabilités de passer d'un état à un autre.
• Distribution de probabilité : Le vecteur ligne $P_k$ représente la probabilité d'être dans chaque état au temps $k$.
• Convergence vers un état stable : Pour de nombreuses chaînes de Markov (irréductibles et apériodiques), la distribution de probabilité converge vers une distribution stationnaire unique, indépendante de l'état initial.
  • Application : Modélisation de la météo, du comportement des utilisateurs, de la dynamique des populations.

• Intelligence artificielle (IA) :
  • Représentation des connaissances (ontologies, réseaux sémantiques).
  • Algorithmes de recherche dans des espaces d'états (ex: jeux comme les échecs).
  • Réseaux neuronaux (bien que de nature différente, les connexions peuvent être vues comme un graphe).
• Bio-informatique :
  • Réseaux de régulation génique, réseaux d'interactions protéiques.
  • Alignement de séquences d'ADN/protéines.
• Logistique :
  • Optimisation des tournées de livraison (TSP), gestion des stocks.
  • Planification des chaînes d'approvisionnement.
• Cryptographie :
  • Certains algorithmes de chiffrement utilisent des structures de graphes.
  • Analyse de réseaux pour la détection de fraudes.

Ce chapitre vous a donné les bases solides des graphes et des matrices. Vous avez appris à les définir, à les représenter, à les manipuler avec des outils matriciels et à comprendre les principes des algorithmes qui les exploitent. Ces connaissances sont un atout majeur pour aborder des problèmes complexes dans de nombreux domaines !