Qu'est-ce qu'un graphe ?

Un graphe est un ensemble de sommets reliés par des arêtes. Il modélise des relations du quotidien : amis sur un réseau social, villes reliées par des routes, pages web liées par des hyperliens. L'ordre d'un graphe est son nombre de sommets ; le degré d'un sommet est le nombre d'arêtes qui en partent. Une chaîne est une suite d'arêtes consécutives reliant des sommets.

📖 Définition

Un graphe non orienté est constitué de sommets et d'arêtes non orientées reliant deux sommets.

🔍 Exemple

Dans un réseau social, chaque personne est un sommet et chaque amitié est une arête.

💡 À retenir : Un graphe transforme une relation binaire en un dessin lisible et exploitable mathématiquement.

🔢

Coder le graphe

La matrice d'adjacence

Pour un graphe d'ordre n, on numérote les sommets de 1 à n. La matrice d'adjacence M est une matrice carrée n×n où le coefficient m_{ij} vaut 1 si les sommets i et j sont reliés par une arête, et 0 sinon. Pour un graphe non orienté, cette matrice est symétrique car la relation est réciproque. La somme des coefficients d'une ligne donne le degré du sommet correspondant.

⭐ À retenir

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

📢 Rappel

Une matrice carrée n×n possède n lignes et n colonnes.

💡 À retenir : La matrice d'adjacence code toutes les connexions d'un graphe sous forme de 0 et de 1.

🔁

Puissances et chemins

Compter les chaînes avec M^k

En multipliant la matrice d'adjacence par elle-même, on obtient des informations sur les chaînes de longueur donnée. Le coefficient (i,j) de M^k est égal au nombre de chaînes de longueur k reliant le sommet i au sommet j. Par exemple, M^2 compte les chaînes de longueur 2, c'est-à-dire les chemins passant par exactement deux arêtes. Cette propriété permet de répondre à des questions concrètes : combien de trajets en deux étapes relient deux villes ?

⭐ À retenir

Pour trouver le nombre de chaînes de longueur k, on calcule M^k et on lit le coefficient voulu.

🔍 Exemple

Si (M^2)_{13}=4, il existe 4 chaînes de longueur 2 reliant le sommet 1 au sommet 3.

💡 À retenir : La puissance k-ième de la matrice d'adjacence compte les chaînes de longueur k.

🎲

Évolutions et probabilités

Graphes orientés et matrices de transition

Un graphe orienté possède des arcs avec un sens, comme des rues à sens unique ou des liens hypertextes. Sa matrice de transition T est carrée : le coefficient t_{ij} est la probabilité de passer du sommet j au sommet i en une étape. Si P_n est l'état probabiliste à l'étape n, alors P_{n+1} = T P_n. On peut ainsi modéliser l'évolution d'un système : météo, parts de marché, navigation sur un site.

📖 Définition

Une matrice de transition est une matrice carrée dont chaque colonne a une somme égale à 1 et dont les coefficients sont des probabilités.

🔍 Exemple

Si la probabilité qu'il fasse beau demain sachant qu'il pleut aujourd'hui est 0,3, ce nombre apparaît dans la matrice de transition météo.

💡 À retenir : Une matrice de transition permet de prévoir l'évolution d'un système probabiliste étape par étape.

Fiche de révision Exercices

Connecte-toi pour donner ton avis sur ce cours.