Vidéo pop :: La formule d’Euler et la dualité des graphes

Transcription de la vidéo

Dans ma vidéo sur le problème de la division du cercle, j’ai fait référence à la formule caractéristique d’Euler. Et ici, je voudrais partager une preuve particulièrement intéressante de ce fait. C’est très différent de la preuve inductive généralement donnée, mais je n’essaie pas de dire qu’elle est en quelque sorte meilleure ou plus facile à comprendre que d’autres preuves. Au lieu de cela, j’ai choisi ce sujet pour illustrer un exemple de l’incroyable notion de la dualité, et de la façon dont elle produit des calculs très raffinés.

Voyons d’abord ce que dit le théorème. Si vous tracez des points avec des droites entre eux, c’est-à-dire un graphe, et si aucune de ces droites ne se croise, c’est-à-dire que vous avez un graphe planaire, et si votre graphe est connexe, alors la formule d’Euler nous indique que le nombre de points moins le nombre de droites plus le nombre de régions où ces droites coupent le plan, y compris cette région extérieure, sera toujours égal à deux.

Parce qu’Euler parlait à l’origine de polyèdres tridimensionnels lorsqu’il a trouvé cette formule, qui n’a été redéfinie que plus tard en fonction de graphes planaires, alors au lieu de points, nous disons sommets ; au lieu de dire des droites, nous parlons d’arêtes ; et au lieu de dire régions, nous disons faces. Par conséquent, nous écrivons la découverte d’Euler comme suit : 𝑠 moins 𝑎 plus 𝑓 égale deux.

Avant de décrire la preuve, je dois passer en revue trois éléments de la terminologie de la théorie des graphes : les cycles, les arbres couvrants et les graphes duals. Si vous connaissez déjà certains de ces sujets et ne vous intéressez pas à voir comment je les décris, n’hésitez pas à cliquer sur l’annotation appropriée pour avancer.

Imaginez une petite créature assise sur l’un des sommets. Appelons-la Randolph. Si nous considérons les arêtes comme quelque chose le long de laquelle Randolph peut se déplacer, d’un sommet à l’autre, nous pouvons raisonnablement parler d’un « chemin » comme étant une suite d’arêtes que Randolph pourrait suivre, sans lui permettre de revenir en arrière sur la même arête.

Un cycle est simplement un chemin qui se termine sur le même sommet où il commence. Vous pourrez peut-être deviner à quel point les cycles seront importants pour nos objectifs, puisqu’ils entoureront toujours un ensemble de faces.

Imaginons maintenant que Randolph souhaite accéder à tous les autres sommets, mais que les arêtes coûtent cher, il n’achètera donc l’accès à une arête que si cela lui donne un chemin vers un sommet intact. Cette frugalité le laissera avec un ensemble d’arêtes sans cycles, car une arête bouclant un cycle serait toujours inutile.

En général, un graphe connexe sans cycles est appelé un arbre, ainsi nommé car nous pouvons le déplacer et le faire ressembler à un système de branches, et tout arbre à l’intérieur d’un graphe qui touche tous les sommets est appelé un arbre couvrant.

Avant de définir le graphe dual, qui risque d’être confus, il est important de rappeler pourquoi les gens s’intéressent vraiment aux graphes en premier lieu.

J’étais en train de mentir tout à l’heure quand j’ai dit qu’un graphe est un ensemble de points et de droites ; en fait c’est un ensemble de n’importe quoi avec n’importe quelle notion de connexion, mais nous représentons généralement ces choses par des points, et ces connexions par des droites.

Par exemple, Facebook entretient un graphe énorme, où les sommets sont des comptes et les arêtes, des amitiés. Bien que nous puissions utiliser des dessins pour représenter ce graphe, le graphe lui-même est l’ensemble abstrait de comptes et d’amitiés, complètement distinct du dessin.

Toutes sortes de choses sont des graphes non dessinés: l’ensemble des mots anglais, considérés connexes quand ils diffèrent d’une lettre; des mathématiciens, considérés comme connexes s’ils ont écrit un document ensemble; des neurones connectés par des synapses, ou peut-être, pour ceux d’entre nous qui raisonnons à propos du tracé réel d’un graphe sur le plan, nous pouvons prendre l’ensemble des faces que ce graphe coupe dans le plan, et en considérer deux qui partagent une arête comme connexes.

En d’autres termes, si vous pouvez tracer un graphe sur le plan sans croiser les arêtes, vous obtenez automatiquement un deuxième graphe non encore dessiné, dont les sommets sont les faces et dont les arêtes sont les arêtes du graphe d’origine. Nous appelons cela le dual du graphe d’origine.

Si vous voulez représenter le graphique dual avec des points et des droites, commencez par insérer un point dans chacune des faces. Personnellement, j’aime bien visualiser le point pour cette région extérieure comme un point situé quelque part à l’infini, où vous pouvez vous déplacer dans n’importe quelle direction pour vous y rendre.

Ensuite, reliez ces nouveaux points à de nouvelles droites qui passent par les centres des anciennes droites, où les droites connectées au point à l’infini peuvent disparaître de l’écran dans n’importe quelle direction, à condition que toutes les droites se rencontrent au même point.

Mais gardez à l’esprit que ceci n’est qu’un dessin du graphe dual, tout comme la représentation des comptes Facebook et des amitiés par des points et des droites n’est qu’un dessin du graphe social ; le graphe dual lui-même est la collection des faces et des arêtes.

La raison pour laquelle j’insiste sur ce point est de souligner que les arêtes du graphe d’origine et les arêtes du graphe dual ne sont pas juste liées ; elles sont la même chose.

Vous voyez, ce qui rend le graphe dual si impressionnant, ce sont les nombreuses façons dont il est lié au graphe d’origine. Par exemple, les cycles du graphe d’origine correspondent aux composantes connexes du graphique dual, et de même, les cycles du graphe dual correspondent aux composantes connexes du graphe d’origine.

Maintenant pour la partie amusante. Supposons que notre ami Randolph ait un alter égo, Mortimer, vivant dans le graphe dual, se déplaçant de face à face au lieu de sommet en sommet, passant ainsi sur les arêtes.

Disons que Randolph a acheté toutes les arêtes d’un arbre couvrant et qu’il est interdit à Mortimer d’y passer. Il s’avère que les arêtes auxquelles Mortimer a droit sont garanties de former un arbre couvrant du graphe dual.

Pour voir pourquoi, il suffit de vérifier les deux propriétés qui définissent les arbres couvrants : ils doivent permettre à Mortimer d’accéder à toutes les faces, et il ne peut y avoir de cycles.

La raison pour laquelle il a toujours accès à toutes les faces est qu’il faudrait un cycle dans l’arbre couvrant de Randolph pour l’isoler d’une face, mais les arbres ne peuvent pas avoir de cycles.

La raison pour laquelle Mortimer ne peut pas traverser un cycle dans le graphe dual est totalement symétrique. S’il le pouvait, il séparerait un ensemble des sommets de Randolph du reste, de sorte que l’arbre couvrant dont il est banni n’aurait pas pu couvrir tout le graphe.

Ainsi, non seulement le graphe planaire a un graphe dual, mais tout arbre couvrant de ce graphe a toujours un arbre couvrant dual dans le graphe dual.

Voici le hic : le nombre de sommets dans un arbre est toujours un de plus que le nombre d’arêtes. Pour voir cela, notez qu’après avoir commencé avec le sommet racine, chaque nouvelle arête donne exactement un nouveau sommet.

Dans notre récit, vous pouvez également penser que Randolph commence avec un sommet et en gagne exactement un de plus pour chaque arête qu’il achète dans ce qui deviendra un arbre couvrant. Puisque cet arbre couvre tous les sommets de notre graphe, alors le nombre de sommets est égal à un de plus que le nombre d’arêtes appartenant à Randolph.

De plus, comme les arêtes restantes constituent un arbre couvrant dans le graphe dual de Mortimer, le nombre d’arêtes qu’il obtient correspond à un de plus que le nombre de sommets du graphe dual, qui sont des faces du graphe original.

En rassemblant tout ça, cela signifie que le nombre total d’arêtes est deux de plus que le nombre de sommets plus le nombre de faces, ce qui correspond exactement à la formule d’Euler.