Qu'est-ce que la théorie des graphes et comment définit-on un graphe en tant que tel ?

En 1736, sur la base des travaux du physicien-mathématicien suisse Leonhard Euler (1707-1783), on a observé qu'une succession de sommets définit un chemin, cependant, si ledit chemin se compose de différents sommets sans arêtes répétées, il est appelé un chemin ou un chemin eulérien; si en plus on arrive au point de départ, en traversant chaque arête une seule fois, alors on a un cycle eulérien (circuit).

Devis (APA)

alexandre barraza | Juil. 2022
Licence en physique

Pour sa part, nous définissons un graphe comme un couple ordonné (SE REND) où v désigne l'ensemble (non vide) de tous les sommets ou nœuds d'un graphe, tandis que UN désigne l'ensemble (il peut être vide) de toutes les arêtes ou lignes qui joignent les sommets d'un graphe. Les éléments de l'ensemble UN peut être désigné comme une paire non ordonnée {v, w} où v et w sont des éléments (nœuds ou sommets) de v, on dit alors que v et w sont des sommets adjacents (ils sont reliés par une arête).

La théorie des graphes est née de la réponse donnée par Euler à un problème d'ingéniosité populaire qui se demandait comment franchir les sept ponts qui rejoint deux îles de la communauté de Königsberg (partie de l'Allemagne à l'époque, et actuellement Kaliningrad, en Russie), entre elles et avec le continent sans utiliser deux fois le même pont et en arrivant au point de départ (situé sur la terre ferme) quel qu'il soit, déterminant que dans ce cas, en définitive, aucun pourrait.

Le problème des sept ponts de Königsberg

Euler a modélisé Königsberg comme un graphe où chaque point (sommet ou nœud) représente un pont et chaque ligne (arête) un chemin terrestre :

Quelle est la solution à ce problème ?

il n'y en a pas la solution qui satisfait aux conditions imposées, puisque, comme l'a montré Euler, les sommets ne sont pas de degré pair, c'est-à-dire qu'un nombre pair de lignes n'affecte pas chaque point _[3]. Il ne semble pas que nous puissions faire grand-chose avec une structure définie aussi simplement, cependant, comme c'est souvent le cas dans matematiques, Parfois, les choses ne sont pas ce qu'elles semblent être. Ainsi, l'un des domaines les plus prolifiques, transversaux et interdisciplinaires _[4] de la connaissance humaine, la théorie des graphes.

Graphes eulériens ou à trajectoire eulérienne ?

Les graphes suivants ont tous des chemins eulériens _[5]. Ont-ils tous des cycles eulériens ?

Prenons le troisième graphique :

Numérotons les sommets :

On voit alors que le chemin défini par la suite {3,4,6,2,1,3,7,6,5,4,2} est un chemin eulérien, puisque il parcourt tout le graphe sans répéter les arêtes, mais ce n'est pas un cycle eulérien, car il n'atteint pas le point de départ. Que se serait-il passé si nous avions numéroté les sommets différemment? Pas grand-chose, sauf que maintenant le chemin serait défini par une succession différente. Que se serait-il passé si nous avions suivi des chemins différents de celui proposé dans notre solution initiale? Cette question est un peu plus complexe à répondre, et elle implique des algorithmes dont les ingénieurs logiciels sont généralement ravis. programmation.

Pour une preuve plus rigoureuse de ce qui est exposé ici, nous devons nous référer au résultat suivant:

"Être g un graphique connexe _[6]. Alors oui g il a un circuit Euler, le degré de chaque sommet est pair, alors que si g a un chemin d'Euler, G a exactement deux sommets de degré impair _[7] (exactement les sommets où le chemin commence et se termine)".

On peut alors vérifier qu'en fait, dans le graphe que l'on prend, seuls les sommets 3 et 6 ont un degré impair (ce se produirait même si la numérotation des sommets avait été différente), donc ledit graphe a un chemin eulérien _[8]. Pour les graphes restants, nous pouvons procéder de manière analogue et vérifier s'ils ont effectivement des chemins et Cycles eulériens, ou autrement dit, pouvons-nous dessiner de tels graphiques sans prendre le crayon et répéter lignes? La réponse à cette question peut être déduite de ce qui a déjà été expliqué jusqu'ici, cependant, elle constitue un exercice intéressant en termes de motricité fine, d'ingéniosité et de patience, j'invite le lecteur à trouver et tracer des graphiques de 6 ou plus sommets avec trajectoire eulérien.

Existe-t-il d'autres types de graphiques? La théorie des graphes a-t-elle des applications dans le monde « réel »?

Ces graphes que nous avons passés en revue très brièvement ne sont qu'un des nombreux types de graphes que l'on trouve dans la théorie des graphes. On peut également trouver des graphes tels que des arbres, très représentatifs dans des ensembles où leurs éléments peuvent être classés dans des hiérarchies et dans des calculs de comptage et probabilité_[9], digraphes, graphes hamiltoniens _[10], etc.

Image des modèles graphiques et des réseaux en psycho., par Ruiz, Ana María.

Ces énigmes, si nous voulons les appeler ainsi, ont une énorme applicabilité dans le monde d'aujourd'hui, dans des situations aussi diverses que: la biologie moléculaire _[11], l'informatique_[12], télécommunications _[13] et analyse de réseau _[14]. Cela vaut donc la peine de se demander: n'est-il pas au moins curieux qu'un problème de presque banal finira par être l'un des résultats les plus intéressants et les plus remarquables des mathématiques? Peut-être, pour cela, la contribution d'un des esprits les plus illustres de l'humanité était-elle nécessaire.