Théorie des graphes
Cours · mathématiques appliquées (ECG 1re année), chapitre 3 · prépa ECG, 1re année · le début du chapitre, la suite sur Adloun
Un graphe fini est un outil de modélisation simple et redoutablement efficace : il représente des objets et les liens entre eux. Les sciences sociales s'en servent pour les réseaux d'individus, l'économie pour des modèles d'évolution, l'informatique pour le réseau des pages web — celui-ci compte plusieurs dizaines de milliards de sommets, et c'est un calcul de graphe qui décide de l'ordre des résultats d'une recherche.
L'intérêt de ce chapitre, placé juste après le calcul matriciel, tient en une phrase : un graphe se range dans une matrice, et les puissances de cette matrice répondent à des questions qu'on ne saurait pas traiter autrement.
3.1 Vocabulaire
Un graphe est la donnée d'un ensemble fini de sommets et d'un ensemble d'arêtes reliant certains couples de sommets. Deux sommets reliés par une arête sont dits adjacents. Le graphe est orienté lorsque ses arêtes ont un sens (on parle alors d'arcs), non orienté sinon.
Un réseau d'amitiés est naturellement non orienté : si est ami avec , l'est avec . Un réseau d'abonnements ne l'est pas : peut suivre sans réciproque. Le choix d'orienter ou non n'est pas technique, il traduit la nature du lien modélisé.
Dans un graphe non orienté, le degré d'un sommet est le nombre d'arêtes qui en partent.
Dans un graphe non orienté à arêtes, la somme des degrés de tous les sommets vaut :
Démonstration
Comptons les couples (sommet, arête issue de ce sommet). En regroupant par sommet, ce nombre vaut . En regroupant par arête, chaque arête a exactement deux extrémités et fournit donc deux couples : le total vaut . Les deux comptages portent sur le même ensemble.
Dans une assemblée, chaque poignée de main engage deux personnes : le nombre total de mains serrées est donc le double du nombre de poignées. Il en découle qu'un graphe a toujours un nombre pair de sommets de degré impair, car une somme d'entiers valant ne peut contenir un nombre impair de termes impairs.
3.2 Matrice d'adjacence
Soit un graphe dont les sommets sont numérotés de à . Sa matrice d'adjacence est la matrice définie par
Exercices du chapitre
- Une liste de degrés impossible corrigé
- La matrice de corrigé
- Deux sommets ont toujours le même degré corrigé
- Ce que dit un coefficient diagonal corrigé
- Le graphe complémentaire corrigé
- Compter les chaînes par les puissances corrigé