$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

La diabolique efficacité de la théorie des graphes

Voici deux petits exercices, à l'énoncé très semblable.

  1. Tracer sur une feuille 7 segments de sorte que chaque segment en coupe exactement trois autres.
  2. Tracer sur une feuille 8 segments de sorte que chaque segment en coupe exactement trois autres.

Si vous prenez une feuille et réfléchissez un peu, vous arriverez très vite à un blocage avec le premier exercice. En revanche, voici une solution pour le deuxième exercice :

Il se trouve qu'en fait, le premier exercice est impossible à résoudre... Cela dit, si on essaie de se prouver que c'est impossible à résoudre, ce n'est pas si facile!

Tout devient beaucoup plus facile si on modélise cette situation à l'aide d'un graphe... Un graphe, c'est un objet mathématique qui comprend des sommets, qu'on représente par des "ronds", et des arêtes, qui sont les liens entre ces sommets, et qu'on représente en traçant un trait entre ces sommets. Dans le problème qui nous intéresse, le graphe est construit de la façon suivante. Les segments sont les sommets du graphe, et il y a une arête entre deux sommets si les deux segments correspondants se coupent. Voici par exemple le graphe correspondant à la solution donnée ci-dessus du deuxième problème :

Expliquons maintenant, à l'aide de la théorie des graphes, pourquoi le premier problème n'a pas de solutions. Dans un graphe, on peut définir le degré d'un sommet : il s'agit du nombre d'arêtes qui partent de ce sommet. Le degré du graphe est la somme des degrés.

Si notre premier problème a une solution, le degré de chaque sommet est égal à 3 (chaque sommet en coupe 3 autres), et donc le degré total du graphe est 7×3=21.

Maintenant, le degré d'un graphe vérifie une propriété très simple : c'est un nombre pair! Il est égal au double du nombre d'arêtes. Chaque arête augmente en effet de 1 le degré de deux sommets (ses extrémités), donc de 2 le degré total du graphe. Or, 21 est un nombre impair... Le premier problème n'a donc pas de solutions!

De nombreux problèmes pratiques (optimisation d'occupation d'une salle, ordonnancement de tâche, recherche d'un plus court chemin entre deux villes,...) peuvent être modélisés par des graphes. On modélise ainsi un problème réel par un objet mathématique déjà très étudié, et pour lequel on dispose d'outils puissants pour obtenir une solution.

En savoir plus...