Ce qui fait un circuit Euler possible?

June 18

Ce qui fait un circuit Euler possible?

Définition

Un chemin eulérien sur un graphique touche chaque bord, une fois et une seule. Un circuit eulérien est un chemin eulérien qui commence et se termine au même point. Ce type de circuit a été théorisée par le mathématicien Leonhard Euler. Il les décrit d'abord tout en travaillant sur les sept ponts de Königsberg problème: Étant donné une série spécifique de ponts reliant plusieurs points, si elle était possible de construire un chemin qui traverserait tous les ponts qu'une seule fois. Euler déterminé que ce problème n'a pas de solution, fixer les bases de la théorie des graphes.

Conditions pour un circuit eulérien

Pour un circuit eulérien soit possible, chaque point du graphique doit avoir un nombre pair de chemins qui s'y connectent. Cela signifie qu'un circuit eulérien est possible pour tout graphe à laquelle chaque sommet a 2, 4 ou un nombre similaire de lignes reliant à elle. Par conséquent, la forme et la configuration du graphique n'a pas d'importance; tout ce qui compte réellement est le nombre de trajets pour chaque ligne.

La construction d'un chemin eulérien pour un graphique

Ce qui fait un circuit Euler possible?


Un graphique peut avoir un chemin eulérien si elle suit deux conditions: il doit avoir tous ses chemins dans le même plan (pensez à un plan comme une surface plane, comme une table ou un morceau de papier) et il y a certaines restrictions sur la «coins» du graphe. Il ne peut y avoir plus de deux angles qui ont un nombre impair de lignes à venir d'eux. Si ces conditions sont remplies, un chemin eulérien peut être faite en utilisant un processus appelé l'algorithme de Fleury. Tout d'abord, vous commencez à un sommet avec un nombre impair de chemins menant de lui. Ensuite, vous déplacez le long de tout bord qui, si vous deviez effacé, le graphique serait toujours connecté - à moins qu'il n'y a pas d'autre choix. Dans ce cas, le bord est supprimée. A la fin de l'algorithme, un chemin Eulérienne (ou dans certains cas, un circuit Eulérienne) est formé.