Théorie des graphes est un sujet très utile et amusant.
Commençons par un problème historique qui est appelé le problème des ponts de Königsberg. La ville de Königsberg en Prusse, l'ancien (maintenant appelé Kaliningrad, Russie) a deux îles au milieu des rivières. Les deux îles reliaient au continent par sept ponts. Leonhard Euler en 1736 a demandé à ce problème: est-il possible de marcher de son domicile dans la ville et traverser chacun des sept ponts une seule fois et retourner à la maison? Le principal problème réside sur le mot «traverser chaque pont une seule fois".
Euler a simplifié le problème de cette façon: chaque masse de terre est considérée comme un noeud (ou appelé vertex) et chacun des ponts en un lien (ou appelé bord). La collection de nœuds et de liens avec les propriétés et les opérations sur les nœuds et de liens sont appelés Théorie des graphes. Euler a également prouvé à l'aide de ce modèle simple que personne ne peut marcher pour traverser chacun des sept ponts une fois pour revenir à la maison. Ainsi, le problème des ponts de Königsberg n'a pas de solution!
Depuis ce temps, l'étude de cette théorie a prospéré. Maintenant, nous pouvons trouver de nombreuses applications de la théorie des graphes. Juste un peu d'entre eux peuvent être mentionnés ici:
Le réseau routier peut être modélisé comme la théorie des graphes d'intersection de noeud et comme 'lien'. En utilisant ce graphique, vous pouvez trouver le chemin le plus court à partir de votre maison à votre école ou au bureau.
Lorsque chaque région sur une carte est représentée comme un nœud, et la connexion de la région avec ses régions voisines dans la même carte est indiquée comme un lien, nous aurons un graphique. La théorie des graphes a conduit à certains résultats que vous seulement 4 couleurs pour la couleur de toutes les régions dans une telle carte qu'aucune région adjacente sera coloré de la même couleur.
Réseau électrique est un graphe avec chacun de la jonction et appareils électriques comme des noeuds reliés par le fil sous forme de liens.
Le réseau social où chaque personne est connecté socialement avec leurs amis où des parents peuvent être visualisées sous forme du graphique.
Une activité dans un projet peut être modélisée un nœud. Les activités précédentes et successives sont reliées aux activités actuelles. Ce graphique des activités conduit à une optimisation des horaires en gestion de projet.
Posted in: Articles français
