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_i, s_j) de sommets

On dit que l'arc (s_i, s_j) part du sommet s_i et arrive au sommet s_j.

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_i, s_i) 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_1, s_2, , s_n}.

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

[formule]

Autrement dit, m_{i,j} = 1 s'il existe un arc de s_i vers s_j, et m_{i,j} = 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_1 = A, s_2 = B, s_3 = C, la matrice d'adjacence est :

[formule]

  • m_{1,2} = 1 car il y a un arc de A vers B
  • m_{2,3} = 1 car il y a un arc de B vers C
  • m_{3,1} = 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_i (degré sortant)
  3. La somme de la colonne j donne le nombre d'arcs arrivant à s_j (degré entrant)
  4. La matrice d'adjacence d'un graphe simple est symétrique si et seulement si le graphe est non orienté

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^k)_{i,j} de la matrice M^k donne le nombre de chemins de longueur k allant du sommet s_i au sommet s_j.

Exemple : Reprenons le graphe précédent avec M = pmatrix 0 & 1 & 0 0 & 0 & 1 1 & 0 & 0 pmatrix.

Calculons M^2 :

[formule]

  • (M^2)_{1,3} = 1 signifie qu'il existe 1 chemin de longueur 2 de A à C : A B C
  • (M^2)_{2,1} = 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_{i_0}, s_{i_1}, , s_{i_k} telle que (s_{i_j}, s_{i_{j+1}}) 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_i, s_j) est associé à un poids (ou coût) w_{i,j}, 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 :

[formule]

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 :

[formule]

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 :

[formule]

Exemple : Pour un graphe avec 3 sommets et 3 arcs : a_1 = (s_1, s_2), a_2 = (s_2, s_3), a_3 = (s_3, s_1).

La matrice d'incidence est :

[formule]

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^k
  • Le nombre de chemins de longueur k partant d'un sommet s_i est la somme de la ligne i de M^k
  • Le nombre de chemins de longueur k arrivant à un sommet s_j est la somme de la colonne j de M^k

À 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_{i,j} = 1 s'il existe un arc de s_i vers s_j, 0 sinon

  3. Puissances : (M^k)_{i,j} donne le nombre de chemins de longueur k de s_i à s_j

  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^2, M^3, 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.