Graphes orientés et matrices d'adjacence

Graphes et matrices — Terminale Maths Expertes

Graphes orientés et matrices d'adjacence

Introduction

Les graphes sont des structures mathématiques permettant de modéliser des relations entre objets. En combinant la théorie des graphes avec l'algèbre linéaire, on peut utiliser des matrices pour représenter et analyser ces structures de manière efficace.


1. Définition d'un graphe orienté

Graphe orienté : Un graphe orienté (ou digraphe) G = (S, A) est constitué de :

  • Un ensemble fini S de sommets (ou nœuds)
  • Un ensemble A de arcs (ou arêtes orientées), où un arc est un couple ordonné (sᵢ, sⱼ) de sommets

On dit que l'arc (sᵢ, sⱼ) part du sommet sᵢ et arrive au sommet sⱼ.

Exemple : Considérons un graphe avec S = {A, B, C, D} et les arcs :

  • (A, B) : arc de A vers B
  • (B, C) : arc de B vers C
  • (C, A) : arc de C vers A
  • (A, D) : arc de A vers D

Ce graphe peut être représenté par un diagramme avec des flèches indiquant la direction des arcs.

Vocabulaire :

  • Arc : relation orientée entre deux sommets
  • Sommet initial : sommet de départ d'un arc
  • Sommet terminal : sommet d'arrivée d'un arc
  • Boucle : arc (sᵢ, sᵢ) reliant un sommet à lui-même
  • Graphe simple : graphe sans boucle et sans arcs multiples entre deux mêmes sommets

2. Matrice d'adjacence

Matrice d'adjacence : Soit G = (S, A) un graphe orienté avec S = {s₁, s₂, …, sₙ}.

La matrice d'adjacence de G, notée M, est la matrice carrée d'ordre n définie par :

M = (mᵢ,ⱼ) où mᵢ,ⱼ = 1 si (sᵢ, sⱼ) ∈ A | 0 sinon

Autrement dit, mᵢ,ⱼ = 1 s'il existe un arc de sᵢ vers sⱼ, et mᵢ,ⱼ = 0 sinon.

Exemple : Considérons le graphe avec S = {A, B, C} et les arcs : (A, B), (B, C), (C, A).

En numérotant les sommets : s₁ = A, s₂ = B, s₃ = C, la matrice d'adjacence est :

M = (0 , 1 , 0 ; 0 , 0 , 1 ; 1 , 0 , 0)

  • m₁,₂ = 1 car il y a un arc de A vers B
  • m₂,₃ = 1 car il y a un arc de B vers C
  • m₃,₁ = 1 car il y a un arc de C vers A
  • Tous les autres coefficients sont 0

Propriétés de la matrice d'adjacence :

  1. La matrice d'adjacence est une matrice binaire (coefficients 0 ou 1)
  2. La somme de la ligne i donne le nombre d'arcs partant de sᵢ (degré sortant)
  3. La somme de la colonne j donne le nombre d'arcs arrivant à sⱼ (degré entrant)
  4. La matrice d'adjacence d'un graphe non orienté est symétrique ; celle d'un graphe orienté l'est exactement quand chaque arc a son arc retour

3. Interprétation des puissances de la matrice d'adjacence

Puissances de la matrice d'adjacence : Soit M la matrice d'adjacence d'un graphe orienté G.

Le coefficient (Mᵏ)ᵢ,ⱼ de la matrice Mᵏ donne le nombre de chemins de longueur k allant du sommet sᵢ au sommet sⱼ.

Exemple : Reprenons le graphe précédent avec M = (0 , 1 , 0 ; 0 , 0 , 1 ; 1 , 0 , 0).

Calculons M² :

M² = (0 , 1 , 0 ; 0 , 0 , 1 ; 1 , 0 , 0)² = (0 , 0 , 1 ; 1 , 0 , 0 ; 0 , 1 , 0)

  • (M²)₁,₃ = 1 signifie qu'il existe 1 chemin de longueur 2 de A à C : A → B → C
  • (M²)₂,₁ = 1 signifie qu'il existe 1 chemin de longueur 2 de B à A : B → C → A

Chemin : Un chemin de longueur k dans un graphe orienté est une séquence de k+1 sommets sᵢ_₀, sᵢ_₁, …, sᵢ_ₖ telle que (sᵢ_ⱼ, sᵢ_ⱼ₊₁) est un arc pour tout j = 0, …, k-1.


4. Graphe pondéré et matrice de poids

Graphe pondéré : Un graphe orienté pondéré est un graphe où chaque arc (sᵢ, sⱼ) est associé à un poids (ou coût) wᵢ,ⱼ, généralement un nombre réel positif.

Matrice de poids : Pour un graphe pondéré, la matrice de poids (ou matrice d'adjacence pondérée) W est définie par :

W = (wᵢ,ⱼ) où wᵢ,ⱼ = poids de l'arc (sᵢ, sⱼ) si (sᵢ, sⱼ) existe | 0 sinon

Exemple : Considérons un réseau routier avec des distances :

  • De A à B : 5 km
  • De B à C : 3 km
  • De C à A : 4 km

La matrice de poids est :

W = (0 , 5 , 0 ; 0 , 0 , 3 ; 4 , 0 , 0)


5. Application : réseaux et flux

Les graphes orientés sont utilisés pour modéliser de nombreux problèmes réels.

Applications :

  1. Réseaux de transport : sommets = villes, arcs = routes orientées
  2. Réseaux informatiques : sommets = serveurs, arcs = connexions
  3. Flux de données : sommets = processus, arcs = transferts de données
  4. Dépendances : sommets = tâches, arcs = relations de dépendance

6. Matrice d'incidence

Matrice d'incidence : Soit G = (S, A) un graphe orienté avec |S| = n sommets et |A| = m arcs.

La matrice d'incidence I est une matrice de taille n × m définie par :

Iᵢ,ₖ = +1 si l'arc aₖ part de sᵢ | -1 si l'arc aₖ arrive à sᵢ | 0 sinon

Exemple : Pour un graphe avec 3 sommets et 3 arcs : a₁ = (s₁, s₂), a₂ = (s₂, s₃), a₃ = (s₃, s₁).

La matrice d'incidence est :

I = (+1 , 0 , -1 ; -1 , +1 , 0 ; 0 , -1 , +1)


7. Propriétés combinatoires

Nombre de chemins : Soit M la matrice d'adjacence d'un graphe orienté.

  • Le nombre total de chemins de longueur k dans le graphe est la somme de tous les coefficients de Mᵏ
  • Le nombre de chemins de longueur k partant d'un sommet sᵢ est la somme de la ligne i de Mᵏ
  • Le nombre de chemins de longueur k arrivant à un sommet sⱼ est la somme de la colonne j de Mᵏ

À retenir

Résumé :

  1. Graphe orienté : G = (S, A) où S est l'ensemble des sommets et A l'ensemble des arcs

  2. Matrice d'adjacence : M où mᵢ,ⱼ = 1 s'il existe un arc de sᵢ vers sⱼ, 0 sinon

  3. Puissances : (Mᵏ)ᵢ,ⱼ donne le nombre de chemins de longueur k de sᵢ à sⱼ

  4. Graphe pondéré : chaque arc a un poids, représenté par une matrice de poids W

  5. Matrice d'incidence : relie sommets et arcs avec coefficients +1, -1 ou 0

Méthode : Pour analyser un graphe orienté :

  1. Construire la matrice d'adjacence M
  2. Calculer M², M³, etc. pour trouver les chemins de différentes longueurs
  3. Utiliser les propriétés des matrices pour obtenir des informations sur la structure du graphe

La représentation matricielle des graphes permet d'utiliser les outils de l'algèbre linéaire pour analyser efficacement ces structures complexes.