🕸️
Vocabulaire et représentationUn 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 graphePour 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 cheminsEn 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ésUn 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.