Almanach des nombres - chemin d'Euler, graphe d'un coup de crayon

NOMBRES - Curiosités, théorie et usages

Accueil / Dictionnaire / Rubriques / Index / Références / Nouveautés

ORIENTATION GÉNÉRALE - M'écrire - Édition du: 27/03/2012

- Ý - GRAPHES

Chemin EULÉRIEN

Sommaire de cette page

>>> APPROCHE

>>> DEGRÉ DES SOMMETS

>>> CHEMIN EULÉRIEN

>>> LA CÉLÈBRE ENVELOPPE

>>> LE CÉLÈBRE PONT DE KÖNIGSBERG

Pages voisines

Topologie - Glossaire

Les neufs points

Chiffre DEUX

Chemin le plus court

Arbre de distribution

Carrés

Dualité

Le parcours du cavalier

CHEMIN EULÉRIEN

Un seul coup de crayon!

Célèbres problèmes du pont et de l'enveloppe

-Ý- APPROCHE

Croix de cauchemar (aurait une signification magique)

§ On peut tracer ces deux figures d'un seul coup de crayon

§ Est-ce vrai pour toutes les figures ?

§ Non ! On pouvait s'en douter

§ Voyez l'exemple suivant

-Ý- DEGRÉ DES SOMMETS

§ Un sommet est caractérisé par le nombre de segments qui y concourent

§ On appelle ce nombre le degré du sommet

§ Le sommet est soit de degré pair, soit de degré impair

-Ý- CHEMIN EULÉRIEN

Chemin Eulérien:

Dessiner un graphe d'un seul coup de crayon,

sans repasser sur un tracé.

Règle

§ Si tous les sommets sont pairs

Possible

Départ = Arrivée

§ S'il existe seulement deux sommets impairs

Possible

Départ = l'un des sommets impairs

Arrivée = l'autre sommet impair

§ Dans tous les autres cas

Impossible

On remarque rapidement, en effet, que pour un degré 3:
On peut y arriver et partir	On peut en partir et revenir
puis y revenir et... stopper	puis partir sans y revenir
c'est un point d'arrivée	c'est un point de départ

Illustration

Rappel: un sommet de degré 3 est une extrémités

Voyez cette figure et un parcours possible

§ Les deux sommets pairs sont des points de passage

§ Les deux sommets impairs sont des extrémités:

l'un le départ, l'autre l'arrivée

-Ý- LA CÉLÈBRE ENVELOPPE

Apparition dans les livres de mathématiques en 1844

Même veine!

Impossible

Quatre nœuds impairs: impossible de le dessiner sans lever le crayon

-Ý- LE CÉLÈBRE PONT DE KÖNIGSBERG (Kaliningrad)

§ Comment aller de A à C en passant une seule fois sur chaque pont ?

§ Euler , qui vivait dans cette ville, a montré que c'est impossible (1736).

§ On dessine le graphe correspondant

§ Avec 4 sommets impairs c'est impossible

§ Avec un pont de plus entre A et C, alors c'est réalisable:

-Ý- THÉORIE

§ Ce genre de graphe est dit réseaux de points	*sommets*
§ Reliés par des lignes	arcs ou arêtes
§ On peut les tracer sur une feuille de papier, dans un plan. Ce sont des:	*graphes planaires*
§ Si on peut les tracer en un seul coup de crayon sans repasser sur une arête § Il n'est pas nécessaire pour connecter tous les points d'enjamber un arc, de sortir du plan, de passer en 3 dimensions	*graphes planaires connexes*
§ Le tracé en un seul trait est appelé	*Chemin eulérien*
§ Graphe de mêmes caractéristiques: sommets de même degré § La longueur des arcs et leur courbure n'influent pas sur les caractéristiques du graphe	*Graphes isomorphes*

Graphes isomorphes

Il s'agit de graphes équivalents: les degrés des sommets sont conservés

Voir

Euler – Biographie