Le cours

Résumé en cinq points

Un graphe est un ensemble de sommets et de liaisons, arêtes si non orienté, arcs si orienté, et sa matrice d'adjacence contient des 1 aux positions correspondantes.
La matrice d'adjacence d'un graphe non orienté est symétrique, et la somme d'une ligne donne le degré du sommet.
Le coefficient en position $(i, j)$ de $A^d$ est le nombre de chemins de longueur $d$ de $i$ vers $j$ , ce qui se démontre par récurrence.
Tout sommet est accessible depuis tout autre si et seulement si $I_n + A + \cdots + A^{n-1}$ a tous ses coefficients strictement positifs.
La somme des degrés vaut deux fois le nombre d'arêtes, donc le nombre de sommets de degré impair est pair.

Pourquoi ce chapitre

Un graphe est un outil de modélisation économique : on dessine des points et on relie ceux qui sont en relation. Cela suffit à représenter :

un réseau social, où les sommets sont des comptes et les arêtes des liens d'amitié ou d'abonnement ;
le graphe du web, où les sommets sont des pages et les arcs les liens hypertexte ;
un réseau de transport, un circuit de distribution ;
les relations de dépendance entre secteurs d'une économie.

L'intérêt pour un étudiant d'ECG est double :

la modélisation : savoir passer d'une situation décrite en français à un graphe et à sa matrice ;
le calcul : le chapitre est la première application sérieuse du produit matriciel.

Le résultat central dit que le coefficient de la puissance $d$ -ième de la matrice d'adjacence compte les chemins de longueur $d$ . Un calcul de puissance devient un dénombrement.

Ordres de grandeur à citer à l'oral : un graphe de réseau social réel comporte des centaines de millions de sommets, le graphe du web plusieurs dizaines de milliards de pages. La matrice d'adjacence correspondante est immense et presque entièrement remplie de zéros, ce qui explique pourquoi en informatique on préfère souvent les listes d'adjacence.

1Vocabulaire

1.1Graphe non orienté

Définition 1.1Graphe non orienté

Un graphe non orienté est la donnée d'un ensemble fini de sommets et d'un ensemble d'arêtes, chaque arête reliant deux sommets.

Deux sommets reliés par une arête sont adjacents, ou voisins.
Une arête reliant un sommet à lui-même est une boucle.

Sauf mention contraire, on considère des graphes simples, sans boucle et avec au plus une arête entre deux sommets.

Définition 1.2Degré

Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes, c'est-à-dire le nombre de ses voisins dans un graphe simple.

1.2Graphe orienté

Définition 1.3Graphe orienté

Dans un graphe orienté, les liaisons sont des arcs, munis d'un sens. Un arc va d'un sommet vers un autre. La relation n'est plus symétrique.

C'est le modèle adapté au web, où une page peut pointer vers une autre sans réciprocité, ou à un réseau d'abonnements asymétriques.

Définition 1.4Degrés sortant et entrant

Dans un graphe orienté, le degré sortant d'un sommet est le nombre d'arcs partant du sommet, le degré entrant est le nombre d'arcs y arrivant.

1.3Chaînes et chemins

Définition 1.5Chaîne, chemin, longueur

Une chaîne dans un graphe non orienté est une suite de sommets telle que deux sommets consécutifs sont adjacents. Dans un graphe orienté, on parle de chemin, et il faut suivre le sens des arcs.

La longueur d'une chaîne ou d'un chemin est le nombre d'arêtes ou d'arcs parcourus, donc le nombre de sommets de la suite moins un.

Une chaîne peut repasser plusieurs fois par le même sommet. Quand on veut l'interdire, on parle de chaîne élémentaire. Le résultat central de la section suivante compte toutes les chaînes, y compris celles qui repassent par un sommet.

Définition 1.6Cycle

Un cycle est une chaîne dont le sommet de départ et le sommet d'arrivée coïncident.

1.4Connexité

Définition 1.7Graphe connexe

Un graphe non orienté est connexe quand deux sommets quelconques sont toujours reliés par une chaîne. Un graphe non connexe se décompose en composantes connexes.

Intuitivement, le dessin est en un seul morceau.

Attention

Dans un graphe orienté, la même propriété avec des chemins orientés est plus forte, car un chemin de $i$ vers $j$ n'assure pas l'existence d'un chemin de $j$ vers $i$ .

1.5Deux exemples de référence

Définition 1.8Graphe complet

Le graphe complet à $n$ sommets est celui où toute paire de sommets distincts est reliée.

Chaque sommet y est de degré $n - 1$ , et le nombre d'arêtes vaut $\frac{n(n-1)}{2}.$ Sa matrice d'adjacence a des 1 partout sauf sur la diagonale.

Définition 1.9Graphe eulérien

Un graphe est eulérien quand il possède un cycle passant une fois et une seule par chaque arête.

Remarque

Résultat classique, à citer comme culture : un graphe connexe possède un tel cycle si et seulement si tous ses sommets sont de degré pair. Ce critère n'est pas un attendu du programme, qui demande seulement de savoir donner des exemples et leurs matrices.

2Matrice d'adjacence

2.1Définition

Définition 2.1Matrice d'adjacence

Numérotons les sommets de 1 à $n$ . La matrice d'adjacence $A$ du graphe est la matrice carrée d'ordre $n$ dont le coefficient en ligne $i$ et colonne $j$ vaut 1 s'il existe une arête entre $i$ et $j$ (un arc de $i$ vers $j$ dans le cas orienté), et 0 sinon.

Pour un graphe simple sans boucle, la diagonale est nulle.

Propriété 2.2Symétrie

Pour un graphe non orienté, la matrice d'adjacence est symétrique, puisque la relation d'adjacence l'est. Pour un graphe orienté, elle ne l'est pas en général.

C'est la remarque explicitement demandée par le programme.

Remarque

La matrice dépend de la numérotation choisie. Changer l'ordre des sommets change la matrice, mais pas le graphe.

2.2Lecture des degrés

Propriété 2.3Degrés et sommes de lignes

Dans un graphe non orienté, le degré du sommet $i$ est la somme des coefficients de la ligne $i$ , qui est aussi celle de la colonne $i$ .
Dans un graphe orienté, la somme de la ligne $i$ donne le degré sortant de $i$ , la somme de la colonne $i$ donne son degré entrant.

2.3Exemple filé

Exemple 2.4Graphe à quatre sommets

Prenons quatre sommets numérotés de 1 à 4, avec les arêtes reliant 1 et 2, 1 et 3, 2 et 3, puis 3 et 4. La matrice d'adjacence est $A = \begin{pmatrix} 0 & 1 & 1 & 0\\ 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 \end{pmatrix}.$ Elle est bien symétrique.

Les degrés se lisent en sommant les lignes : 2 pour le sommet 1, 2 pour le sommet 2, 3 pour le sommet 3, 1 pour le sommet 4. Le sommet 3 est le mieux connecté, le sommet 4 est périphérique.

3Puissances de la matrice d'adjacence

3.1Le résultat central

Théorème 3.1Chemins et puissances de $A$

Hypothèses

$A$ est la matrice d'adjacence d'un graphe à $n$ sommets ;
$d$ est un entier naturel non nul.

Alors le coefficient de $A^d$ situé à la ligne $i$ et à la colonne $j$ est égal au nombre de chemins de longueur $d$ allant du sommet $i$ au sommet $j$ .

Démonstration

Idée, par récurrence sur $d$ . Pour $d = 1$ c'est la définition de la matrice d'adjacence. Supposons le résultat au rang $d$ . Un chemin de longueur $d + 1$ de $i$ vers $j$ se décompose de façon unique en un chemin de longueur $d$ de $i$ vers un sommet intermédiaire $k$ , suivi d'un arc de $k$ vers $j$ . En sommant sur tous les sommets intermédiaires possibles, on obtient la somme des produits du coefficient de $A^d$ en position $(i, k)$ par le coefficient de $A$ en position $(k, j)$ , c'est-à-dire le coefficient de $A^d A$ en position $(i, j)$ .

La définition du produit matriciel, qui peut sembler arbitraire, est celle qui compte les compositions de chemins.

3.2Sur l'exemple

Avec la matrice de l'exemple filé, la première ligne de $A^2$ est $(2, 1, 1, 1)$ .

Exemple 3.2Interprétation des coefficients de $A^2$

Le coefficient en position $(1, 1)$ vaut 2. Il y a deux chemins de longueur 2 de 1 vers 1 : aller en 2 et revenir, ou aller en 3 et revenir.
Le coefficient en position $(1, 4)$ vaut 1. Il y a un seul chemin de longueur 2 de 1 vers 4, celui qui passe par 3. Les sommets 1 et 4 ne sont pas voisins, mais ils ont un voisin commun.

Propriété 3.3Coefficient diagonal de $A^2$

Dans un graphe non orienté simple, le coefficient diagonal de $A^2$ en position $(i, i)$ est égal au degré du sommet $i$ .

Dans un réseau social, la lecture par voisin commun correspond à la notion d'ami commun, et une plateforme s'en sert pour proposer des suggestions de contacts.

3.3Conséquence sur la connexité

Théorème 3.4Critère de connexité

Hypothèses

$A$ est la matrice d'adjacence d'un graphe à $n$ sommets.

Alors deux sommets quelconques sont reliés par un chemin si et seulement si la matrice $I_n + A + A^2 + \cdots + A^{n-1}$ a tous ses coefficients strictement positifs.

Démonstration

Idée. Le coefficient en position $(i, j)$ de cette somme compte tous les chemins de $i$ vers $j$ de longueur au plus $n - 1$ . Il est strictement positif exactement quand il existe au moins un tel chemin. S'il existe un chemin de $i$ vers $j$ , il en existe un qui ne repasse jamais par un même sommet, donc de longueur au plus $n - 1$ , puisqu'il visite au plus $n$ sommets distincts. Il est inutile d'aller au-delà de l'exposant $n - 1$ .

Pour un graphe non orienté, ce critère caractérise la connexité.
Pour un graphe orienté, il caractérise le fait que tout sommet soit accessible depuis tout autre en suivant le sens des arcs, propriété plus forte que la connexité du graphe non orienté sous-jacent.

Le terme $I_n$ sert uniquement à assurer la positivité des coefficients diagonaux, un sommet étant relié à lui-même par le chemin vide.

4Formule des poignées de main

Théorème 4.1Formule des poignées de main

Dans un graphe non orienté, la somme des degrés de tous les sommets est égale au double du nombre d'arêtes.

Démonstration

Chaque arête possède deux extrémités, elle est donc comptée une fois dans le degré de chacune d'elles.

Deux conséquences immédiates :

la somme des degrés est toujours paire ;
le nombre de sommets de degré impair est pair.

Exemple 4.2Sur l'exemple filé

La somme des degrés vaut $2 + 2 + 3 + 1 = 8$ , ce qui correspond bien aux quatre arêtes.

Version imagée : dans une réunion, le nombre total de mains serrées, compté personne par personne, vaut deux fois le nombre de poignées de main échangées.

5Analyse des réseaux sociaux

Le programme demande d'introduire quelques mesures sur des exemples simples, en précisant qu'elles ne sont pas exigibles.

Définition 5.1Degré de centralité

Le degré de centralité d'un sommet est son degré, éventuellement rapporté au nombre maximal possible de voisins.

Un sommet de fort degré est directement connecté à beaucoup d'autres. C'est la mesure la plus simple pour repérer un compte influent.

Définition 5.2Degré d'intermédiarité

Le degré d'intermédiarité d'un sommet mesure la fréquence à laquelle il se trouve sur les chemins les plus courts entre deux autres sommets.

Un sommet de forte intermédiarité joue un rôle de pont entre communautés. Il peut avoir un degré modeste et pourtant être critique, car sa disparition coupe le graphe.

Exemple 5.3Sur l'exemple filé

Le sommet 3 a le plus fort degré et il est aussi le seul passage vers le sommet 4. Il est central pour les deux mesures.

Une mesure unique ne suffit jamais à caractériser l'influence, c'est le discours critique attendu.

6Lien avec l'informatique

En Python, un graphe se représente par sa matrice d'adjacence sous forme de tableau numpy construit avec np.array.

Le produit se calcule avec np.dot.
Les puissances se calculent avec la fonction matrix_power de numpy.linalg.
Le degré d'un sommet s'obtient en sommant une ligne avec np.sum.

MéthodeTester la connexité par le critère matriciel

Initialiser une matrice $S$ à l'identité et une matrice $P$ à l'identité.
Pour $k$ allant de 1 à $n - 1$ , remplacer $P$ par le produit de $P$ et de $A$ , et $S$ par la somme de $S$ et de $P$ .
Parcourir tous les coefficients de $S$ et renvoyer faux dès qu'on en trouve un nul.

Cette méthode est simple mais coûteuse, car elle multiplie des matrices de taille $n$ . Un parcours de graphe fait le même travail bien plus vite, sujet traité au second semestre.

Méthodes

MéthodeRéflexes du chapitre

Commencer par numéroter les sommets et écrire la matrice, en vérifiant la symétrie dans le cas non orienté.
Pour compter des chemins de longueur donnée, calculer la puissance correspondante de la matrice d'adjacence, puis lire le bon coefficient, en faisant attention à l'ordre ligne puis colonne.
Pour interpréter un coefficient diagonal de $A^2$ , penser au degré.
Pour tester la connexité à la main sur un petit graphe, parcourir le dessin est plus rapide que calculer les puissances. Le critère matriciel sert surtout à justifier proprement ou à programmer.
Vérifier tout calcul de degrés avec la formule des poignées de main.

Ce qu'il faut savoir refaire en khôlle

Passer d'un dessin de graphe à sa matrice d'adjacence, et réciproquement.
Dire pourquoi la matrice d'adjacence d'un graphe non orienté est symétrique.
Énoncer le résultat sur les coefficients de la puissance $d$ -ième et donner l'idée de la récurrence.
Interpréter les coefficients de $A^2$ sur un exemple à quatre ou cinq sommets.
Justifier que le coefficient diagonal de $A^2$ en position $(i, i)$ est le degré du sommet $i$ .
Énoncer le critère de connexité par la matrice somme et expliquer pourquoi l'exposant s'arrête à $n - 1$ .
Démontrer la formule des poignées de main et en déduire que le nombre de sommets de degré impair est pair.
Donner la matrice d'adjacence du graphe complet à $n$ sommets et son nombre d'arêtes.

Méthodes et exercices

Les résultats à connaître

Graphe non orienté, sommets et arêtes, sommets adjacents, degré d'un sommet égal au nombre d'arêtes incidentes : exigible.
Graphe orienté, arcs munis d'un sens, degré sortant et degré entrant : exigible.
Matrice d'adjacence A, coefficient 1 s'il existe une arête ou un arc entre les deux sommets, 0 sinon. Symétrique pour un graphe non orienté : exigible, remarque explicitement demandée.
Chaîne dans un graphe non orienté, chemin dans un graphe orienté, longueur égale au nombre d'arêtes ou d'arcs parcourus : exigible.
Graphe non orienté connexe, deux sommets quelconques reliés par une chaîne : exigible.
Graphe complet à n sommets, degré n−1 partout, n(n−1)/2 arêtes, graphe eulérien à citer en exemple avec sa matrice, le critère par les degrés n'est pas exigible en démonstration : exigible pour les exemples, critère mentionné.
Résultat central, le coefficient en position i, j de Aᵈ est le nombre de chemins de longueur d du sommet i au sommet j : exigible avec démonstration, par récurrence.
Dans un graphe non orienté simple, le coefficient diagonal de A² en position i, i est égal au degré du sommet i : exigible, conséquence directe.
Critère de connexité, si A est la matrice d'adjacence d'un graphe orienté à n sommets, tout sommet est accessible depuis tout autre si et seulement si Iₙ + A + … + Aⁿ⁻¹ a tous ses coefficients strictement positifs : exigible avec justification de l'exposant.
Formule des poignées de main, la somme des degrés vaut le double du nombre d'arêtes : exigible avec démonstration.
Conséquences, la somme des degrés est toujours paire, le nombre de sommets de degré impair est pair : exigible.
Degré de centralité et degré d'intermédiarité, introduits sur des exemples simples pour l'analyse de réseaux sociaux : mentionné, non exigible d'après le programme.

Clés de démonstration

Résultat central sur les puissances de A. On raisonne par récurrence sur d. Pour d = 1, c'est la définition. À l'ordre d+1, un chemin de longueur d+1 de i vers j se décompose de façon unique en un chemin de longueur d de i vers un sommet intermédiaire k, suivi d'un arc de k vers j. Sommer sur tous les k possibles reconstitue exactement le coefficient du produit Aᵈ fois A. L'astuce : la définition du produit matriciel est celle qui compte les compositions de chemins.

Exposant n−1 dans le critère de connexité. Si un chemin relie i à j, il en existe un qui ne repasse jamais par le même sommet, donc de longueur au plus n−1, puisqu'il visite au plus n sommets distincts. Il est donc inutile de sommer au-delà de cet exposant. L'astuce : un chemin simple ne peut pas dépasser n−1 arêtes dans un graphe à n sommets.

Formule des poignées de main. Chaque arête possède exactement deux extrémités, elle est donc comptée une fois dans le degré de chacune d'elles. En sommant tous les degrés, chaque arête contribue donc deux fois au total. L'astuce : compter les contributions arête par arête plutôt que sommet par sommet.

Coefficient diagonal de A². (A²)_i,i = Σ_k A_i,k A_k,i. Pour un graphe non orienté, A_k,i = A_i,k, donc chaque terme vaut A_i,k au carré, égal à A_i,k lui-même puisque les coefficients valent 0 ou 1. La somme compte donc exactement le nombre de voisins de i, c'est-à-dire son degré. L'astuce : reconnaître que la symétrie transforme un produit croisé en carré.

Exemples et contre-exemples à connaître

Le graphe complet à n sommets a pour matrice des 1 partout sauf sur la diagonale, chaque sommet est de degré n−1, il y a n(n−1)/2 arêtes : référence à citer immédiatement.
Un graphe eulérien possède un cycle passant une fois par chaque arête, le critère par la parité des degrés se cite comme culture, sans démonstration exigée.
Sur un graphe à quatre sommets avec les arêtes 1-2, 1-3, 2-3, 3-4, la matrice est symétrique, les degrés valent 2, 2, 3, 1, et leur somme, 8, vaut bien deux fois le nombre d'arêtes.
Sur ce même graphe, le coefficient (1,4) de A² vaut 1, il existe un seul chemin de longueur 2 entre les sommets 1 et 4, qui passe par leur voisin commun 3 : c'est la notion d'ami commun dans un réseau social.
Changer la numérotation des sommets change la matrice d'adjacence, mais pas le graphe : ne pas croire que deux matrices différentes représentent forcément deux graphes différents.
Dans un graphe orienté, un chemin de i vers j n'assure pas l'existence d'un chemin de j vers i : l'accessibilité orientée n'est pas symétrique comme la connexité non orientée.
Le nombre de sommets de degré impair est toujours pair, conséquence de la formule des poignées de main, utile pour détecter une erreur de calcul de degrés.
Un sommet de degré modeste peut avoir une forte intermédiarité et jouer un rôle de pont critique entre deux communautés, malgré un degré de centralité qui n'est pas maximal.
Une chaîne peut repasser plusieurs fois par le même sommet, contrairement à une chaîne élémentaire, et le résultat sur Aᵈ compte toutes les chaînes, y compris celles qui repassent.
Un coefficient nul de Aᵈ en position (i,j) ne signifie pas qu'aucun chemin ne relie i à j, seulement qu'aucun chemin n'a exactement la longueur d.

Techniques du chapitre

Technique 1, passer d'un dessin à la matrice d'adjacence en vérifiant la symétrie dans le cas non orienté. Mini-exercice : pour un triangle à trois sommets tous reliés deux à deux, la matrice a des 1 partout sauf sur la diagonale, chaque sommet est de degré 2.

Technique 2, lire un degré en sommant une ligne, ou une colonne si le graphe est orienté. Mini-exercice : si la ligne 2 d'une matrice non orientée est (1,0,1,1), le sommet 2 est de degré 3.

Technique 3, compter des chemins de longueur d en calculant Aᵈ et en lisant le bon coefficient. Mini-exercice : pour compter les chemins de longueur 3 entre les sommets 1 et 4, on calcule A³ et on lit le coefficient en position (1,4).

Technique 4, interpréter un coefficient diagonal de A² comme un degré. Mini-exercice : si (A²) en position (3,3) vaut 4, le sommet 3 est de degré 4.

Technique 5, sur un petit graphe, vérifier la connexité en parcourant le dessin plutôt qu'en calculant les puissances. Mini-exercice : pour un graphe à 3 sommets, il suffit de vérifier que Iₙ + A + A² a tous ses coefficients strictement positifs, l'exposant s'arrêtant à n−1 = 2.

Technique 6, vérifier tout calcul de degrés avec la formule des poignées de main. Mini-exercice : pour des degrés 3, 3, 2, 1, 1 sur 5 sommets, la somme vaut 10, soit 5 arêtes, et le nombre de sommets de degré impair, 4, est bien pair.

Technique 7, distinguer graphe orienté et non orienté avant tout calcul. Mini-exercice : une matrice d'adjacence non symétrique indique nécessairement un graphe orienté.

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

Exercice 1

Classiques de khôlle et concours · Khôlle

Un graphe a 5 sommets numérotés de 1 à 5, avec les arêtes 1-2, 1-3, 2-3, 3-4, 4-5. Écrire sa matrice d'adjacence et calculer les degrés.

Technique construction de la matrice, vérification par la formule des poignées de main.

Voir le corrigé

Matrice A, lignes 1 à 5 : (0,1,1,0,0), (1,0,1,0,0), (1,1,0,1,0), (0,0,1,0,1), (0,0,0,1,0).
A est symétrique, cohérent avec un graphe non orienté.
Degrés en sommant les lignes : 2, 2, 3, 2, 1.
Somme des degrés = 10 = 2 × 5 arêtes, cohérent avec la formule des poignées de main.

piège : Oublier une arête en construisant la matrice, erreur que la vérification finale permet justement de repérer.

Exercice 2

Classiques de khôlle et concours · Khôlle

Sur le graphe de l'exercice 1, calculer le coefficient de A² en position (1,4) et le coefficient diagonal en position (3,3), et les interpréter.

Technique calcul de produit matriciel, interprétation par chemins et par degré.

Voir le corrigé

(A²)_1,4 = Σ_k A₁,k A_k,4. Seul k = 3 contribue, car A₁,3 = 1 et A₃,4 = 1. Donc (A²)_1,4 = 1.
Il existe donc exactement un chemin de longueur 2 entre 1 et 4, celui qui passe par 3.
(A²)_3,3 = A₃,1² + A₃,2² + A₃,4² = 1 + 1 + 1 = 3, par symétrie de A.
Ce coefficient diagonal égale bien le degré du sommet 3, calculé à l'exercice précédent.

piège : Oublier de sommer sur tous les indices intermédiaires possibles, en n'examinant qu'un seul chemin plausible.

Exercice 3

Classiques de khôlle et concours · Khôlle

Un graphe non orienté a pour suite de degrés 3, 3, 3, 3, 2. Est-ce compatible avec la formule des poignées de main ? Combien d'arêtes cela représente-t-il ?

Technique vérification de parité, dénombrement des arêtes.

Voir le corrigé

Somme des degrés = 3+3+3+3+2 = 14, qui est paire, compatible avec la formule des poignées de main.
Cela correspond à 14/2 = 7 arêtes.
Avec 5 sommets, le nombre maximal d'arêtes, celui du graphe complet, vaut 5×4/2 = 10, donc 7 arêtes reste possible en nombre.
Une parité correcte est une condition nécessaire, pas automatiquement suffisante pour garantir l'existence d'un graphe réalisant exactement cette suite de degrés.

piège : Croire qu'une somme paire des degrés suffit à elle seule à garantir l'existence d'un graphe, sans vérifier qu'une configuration explicite la réalise.

Exercice 4

Classiques de khôlle et concours · Khôlle vers écrit

Un graphe orienté à 3 sommets a pour matrice A, ligne 1 = (0,1,0), ligne 2 = (0,0,1), ligne 3 = (1,0,0), soit un cycle orienté 1→2→3→1. Tout sommet est-il accessible depuis tout autre ?

Technique critère matriciel, calcul jusqu'à l'exposant n−1.

Voir le corrigé

A² : ligne 1 = (0,0,1), ligne 2 = (1,0,0), ligne 3 = (0,1,0), en suivant le cycle deux crans plus loin.
I₃ + A + A² : chaque ligne devient (1,1,1), la somme des trois matrices reconstituant tous les décalages possibles du cycle.
Tous les coefficients sont strictement positifs, donc tout sommet est accessible depuis tout autre.
C'est cohérent avec la structure du cycle orienté, où l'on atteint n'importe quel sommet en suivant le cycle un nombre suffisant de fois.

piège : S'arrêter au calcul de A seul et conclure trop vite, sans sommer jusqu'à l'exposant n−1 exigé par le critère.

Exercice 5

Classiques de khôlle et concours · Khôlle

Le graphe complet à 6 sommets modélise un tournoi où chaque joueur rencontre tous les autres une fois. Combien de matchs au total ? Un septième joueur ajoute combien de matchs ?

Technique formule du nombre d'arêtes du graphe complet.

Voir le corrigé

Le nombre d'arêtes du graphe complet à n sommets vaut n(n−1)/2.
Pour n = 6, 6×5/2 = 15 matchs.
Pour n = 7, 7×6/2 = 21 matchs, soit 6 matchs supplémentaires.
Ce résultat est cohérent, le septième joueur ajoute exactement une arête vers chacun des 6 joueurs déjà présents.

piège : Recalculer le total pour n = 7 sans remarquer que la différence correspond simplement au degré du nouveau sommet, ici 6.

Exercice 6

Classiques de khôlle et concours · Type écrit EDHEC

Un réseau social compte 6 comptes numérotés 1 à 6, avec les abonnements orientés 1→2, 2→3, 3→1, 3→4, 4→5, 5→6, 6→4. Le compte 2 est-il accessible depuis le compte 6 ? Le compte 1 est-il accessible depuis le compte 5 ?

Technique suivi direct des arcs plutôt que calcul matriciel complet, adapté à un petit graphe.

Voir le corrigé

Depuis 6, les arcs mènent à 4, puis 4 mène à 5, puis 5 mène à 6 : on tourne dans le cycle {4,5,6} sans jamais atteindre 1, 2 ou 3.
Le compte 2 n'est donc pas accessible depuis 6.
Depuis 5, le même raisonnement s'applique, on ne quitte jamais le cycle {4,5,6}.
Le compte 1 n'est donc pas accessible depuis 5. Le seul lien entre les deux cycles {1,2,3} et {4,5,6} est l'arc 3→4, à sens unique.

piège : Conclure à l'accessibilité générale parce que le graphe paraît bien connecté visuellement, sans vérifier qu'aucun arc ne revient de {4,5,6} vers {1,2,3}.

Exercice 7

Classiques de khôlle et concours · Type écrit EDHEC ou ESSEC

Trois secteurs économiques, agriculture A, industrie I, services S, sont reliés par des arcs de dépendance A→I, A→S, I→S, I→A, S→I. Écrire la matrice d'adjacence et calculer sa ligne correspondant à A dans le carré de la matrice, pour dénombrer les chaînes d'approvisionnement de longueur 2 partant de A.

Technique produit matriciel, lecture économique d'un coefficient diagonal.

Voir le corrigé

Matrice M, ordre A, I, S : ligne A = (0,1,1), ligne I = (1,0,1), ligne S = (0,1,0).
Colonnes de M : colonne A = (0,1,0), colonne I = (1,0,1), colonne S = (1,1,0).
(M²)_A,A = 0×0+1×1+1×0 = 1, (M²)_A,I = 0×1+1×0+1×1 = 1, (M²)_A,S = 0×1+1×1+1×0 = 1.
La ligne A de M² vaut (1,1,1), il existe une chaîne d'approvisionnement de longueur 2 de A vers chacun des trois secteurs, y compris vers lui-même, via A→I→A.

piège : Ignorer le sens réel d'un coefficient diagonal, une boucle de dépendance indirecte d'un secteur vers lui-même, en le traitant comme une simple curiosité de calcul.

Exercice 8

Classiques de khôlle et concours · Type écrit ESSEC ou HEC, plus délicat

Montrer que dans tout graphe non orienté simple à n ≥ 2 sommets, il existe toujours au moins deux sommets de même degré.

Technique principe des tiroirs, après avoir exclu la coexistence des deux valeurs extrêmes de degré.

Voir le corrigé

Chaque sommet a un degré compris entre 0 et n−1, ce qui donne a priori n valeurs possibles pour n sommets.
Un graphe ne peut pas contenir à la fois un sommet de degré 0, isolé, et un sommet de degré n−1, relié à tous les autres, y compris à ce sommet isolé : c'est contradictoire.
Les degrés effectivement possibles se répartissent donc sur seulement n−1 valeurs parmi {0, …, n−1}, jamais les deux extrêmes simultanément.
Avec n sommets à répartir parmi n−1 valeurs possibles, le principe des tiroirs garantit qu'au moins deux sommets partagent le même degré.

piège : Appliquer le principe des tiroirs directement avec n valeurs possibles, ce qui ne suffit pas, sans avoir d'abord exclu la coexistence des deux valeurs extrêmes.

Erreurs fréquentes

Croire qu'une somme paire des degrés suffit à garantir l'existence d'un graphe, alors que c'est une condition nécessaire, pas toujours suffisante.
Oublier de vérifier la symétrie de la matrice d'adjacence pour un graphe non orienté, ce qui permet pourtant de repérer une erreur de construction.
Conclure à l'accessibilité générale d'un graphe orienté sur la seule impression visuelle, sans suivre rigoureusement le sens de chaque arc.
Lire un coefficient nul de Aᵈ comme signifiant qu'aucun chemin ne relie deux sommets, alors que cela signifie seulement qu'aucun n'a exactement la longueur d.
Confondre le degré de centralité, simple compte de voisins, et le degré d'intermédiarité, rôle de pont entre communautés, deux mesures non exigibles mais régulièrement questionnées à l'oral.

Fiche de cours rédigée à partir du programme officiel d'ECG, mathématiques appliquées de première année, premier semestre, partie III « Théorie des graphes ». Le programme traite le sujet par le calcul matriciel et l'informatique. Les algorithmes de plus court chemin, dont celui de Dijkstra, relèvent du second semestre et ne sont pas traités ici.