NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 09/07/2017

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Topologie

 

Débutants

Général

GRAPHES

 

Glossaire

Topologie

 

 

INDEX

 

Logique

 

Vocabulaire

des graphes

 

Ivrogne

Cinq pays

Chemin le plus court

Chemin eulérien

Trois maisons

Arbre de distribution

Graphe planaire

Petit monde

Voyageur de commerce

Graphe de Delaunay

Colonies de fourmis

 

Sommaire de cette page

>>> Approche

>>> Degré des sommets 

>>> Chemin eulérien

>>> La célèbre enveloppe

>>> Le célèbre pont de Königsberg

>>> Vocabulaire

 

 

 

 

CHEMIN EULÉRIEN

Figures unicursales

 

Un seul coup de crayon!

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

 

 

 Devinette

Dessinez complétement cette figure sans lever le crayon. Pas si simple!

 

Solution

 

Bonus: pouvez-vous dessinez d'un seul trait une guérite (petite maison) avec sa sentinelle (garde en arme) ?

 

 

 

 

APPROCHE

 

 

 

Pas de problème pour dessiner ces deux figures sans lever le crayon.

 

 

Croix de cauchemar (aurait une signification magique).

 



Est-ce vrai pour toutes les figures ? Non ! Voyez l'exemple ci-contre.

 

 

 

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.

 

 

Voir Pair et impair

 

 

 

 CHEMIN EULÉRIEN

Chemin eulérien: graphe qui peut être dessiné d'un seul coup de crayon, sans repasser sur un tracé.

 

Règle

 

On remarque rapidement, en effet, que pour un degré 3: dans un sens comme dans l'autre, impossible d'aller plus loin.

Ces points sont des points de départ ou d'arrivée.

 

 

 

 

  

LA CÉLÈBRE ENVELOPPE et variantes

Dessinez l'enveloppe en un trait. Cette énigme est apparue dans les livres de mathématiques en 1844.

 

Nous notons deux sommets impairs, et seulement deux, le tracé est donc possible.

 

Notez que la pointe de l'enveloppe (0) n'est pas un sommet.

 

Réalisable

 

Deux nœuds impairs aux extrémités gauche et droite.

 

Réalisable

 

Irréalisable: quatre nœuds impairs

 

 

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

 

 

Comment aller d'un bord à l'autre en passant une seule fois sur chaque pont ?

 

 

 

 

 

Ce parcours (rouge) va bien du bord sud au bord nord, mais en laissant de coté le pont central.

 

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

 

 

Transcription en graphe.

 

Avec 4 sommets impairs c'est impossible.

 

 

 

Avec un pont de plus entre A et C, alors ce serait réalisable. Dans ce cas, le graphe est dit planaire.

Voir Énigmes juniors

 

Dessin original

 

Euler interrogé sur les ponts

Pendant son séjour à l'Académie des sciences de Saint-Pétersbourg, Euler reçut une lettre curieuse. Elle provenait de la ville pittoresque de Königsberg en Prusse (Kaliningrad dans la Russie actuelle). Morcelée par les bras de la rivière Pregel, la ville consistait en quatre quartiers séparés reliés par sept ponts. Le maire de la ville voisine de Dantzig, Carl Leonhard Gottlieb Ehler, voulait organiser un circuit à pied de Königsberg de telle manière que les touristes franchissent tous les ponts. (…)

Le grand mathématicien fut d'abord réticent. (…) Il n'existait en fait dans toute la science mathématique aucun instrument  qui puise s'attaquer à une énigme de ce type. (…) Certes, le philosophe allemand Gottfried Wilhem Leibniz (1646-1716) et son élève Christian Wolf (1679-1745) avaient suggéré une nouvelle discipline mathématique, qu'ils baptisèrent analysis situs (…)

Euler montre qu'il est carrément impossible de parcourir Königsberg à pied de la manière souhaitée (…) et donne les conditions exactes dans lesquelles une ville dotée d'îles et de ponts peut être parcourue de la manière prescrite.

Extrait de La conjecture de Poincaré – George G. Szpiro – Lattès Points sciences – 2007 – pages 85 à 87

 

 

 

Vocabulaire

Sommets ou nœuds

 Ce genre de graphe est dit réseaux de points (sommets).

Distance entre deux sommets

Longueur de la plus courte chaine qui relie ces deux sommets.

Ordre du graphe

Quantité de sommets dans ce graphe.

Diamètre du graphe

La plus grande des distances entre les paires de sommets du graphe.

Degré d'un sommet

Quantité d'arêtes présentes à ce sommet. >>>

Arêtes ou arcs

Segment linéaire ou courbe joignant les sommets.

Arc est plutôt utilisé lorsque l'arête est orientée.

Adjacent (sommets)

Deux sommets sont adjacents s'ils sont reliés par une arête.

Face d'un graphe

Chacune des régions délimitées par les arêtes, y compris la région extérieure. Région délimitée par un chemin passant par trois sommets et ne contenant aucun autre sommet.

Graphe connexe

Graphe tels que toute paire de sommet peut être reliée par une chaine (une suite d'arêtes). Ce graphe possède au moins n – 1 arêtes.

Arbre

Graphe qui ne contient aucun cycle (boucle). Ils sont donc planaires

Graphe complet

Tous les sommets sont adjacents. Alors, chaque sommet est relié à tous les autres.

Graphe k-facteur

Chaque sommet ne reçoit que k arêtes.

K5

Graphe complet à 5 sommets. Il n'est pas planaire.

Graphe biparti

Les sommets sont divisés en deux groupes. Les sommets de l'un sont reliés aux sommets de l'autre.

K3,3

Graphe complet biparti de 3 + 3 sommets. Il n'est pas planaire

Graphe planaire

 Un graphe planaire est dessiné sur une feuille de papier, dans un plan, sans que les arêtes se croisent.

Nombre chromatique

Quantité maximale de couleurs pour colorier un graphe. >>>

Graphe planaire topologique

Le graphe est dessiné dans une version qui montre que les arêtes ne se croisent pas. Cette version du graphe est aussi appelée la carte du graphe planaire.

Graphe planaire connexe

Graphe qui n'a pas de sommets ou de sous-graphes isolés. Il existe toujours un chemin pour relier deux sommets.

Chemin eulérien

Chaine eulérienne

Le tracé en un seul trait est appelé chemin eulérien.

La chaine contient toutes les arêtes et chaque arête n'est décrite qu'une seule fois.

Cycle eulérien

Chaine eulérienne fermée: le sommet de départ et celui d'arrivée sont les mêmes.

Graphe eulérien

Graphe que l'on peut dessiner sans jamais lever le crayon et sans passer deux fois par la même arête.

Un graphe est eulérien si et seulement si il contient une chaine eulérienne ou un cycle eulérien.

Chemin hamiltonien

Un tracé qui passe par tous les sommets (sans forcément parcourir toutes les arêtes du graphe).

Un graphe hamiltonien est un graphe possédant au moins un cycle passant par tous les sommets une fois et une seule. Un tel cycle élémentaire est alors appelé cycle hamiltonien.

Exemples avec le problème de la table ronde de Dudeney

Graphes isomorphes

Graphes de mêmes caractéristiques: le degré des sommets est conservé. La longueur des arcs et leur courbure n'influent pas sur les caractéristiques du graphe.

 

Exemple

Leur résolution en temps polynomial est un problème ouvert.

 

 

 Devinette – Solution

 

Les deux demi-lunes enchevêtrées

Remarquez que tous les sommets sont pairs. Ce qui veut dire que la solution est possible.

 

Suivez le trait rouge puis le trait vert.

 

L'astuce, en haut, consiste, après un demi-cercle, à prendre un chemin qui croise les deux demi-lunes.

 

L'astuce, en bas, consiste à suivre l'extérieur puis l'intérieur.

 

Retour

 

Les trois demi-lunes (ci-dessous)

La solution systématique (extérieur, puis intérieur) s'applique sans difficulté.

Solution élégante

Solution systématique

La guérite et la sentinelle

Vous dessinez ce croquis en commençant par la partie rouge qui semble être une erreur de dessin.

Votre ami vous interroge: mais où est la sentinelle? – Elle est derrière la guèrite. Seul le bout de sa baïonette dépasse!

Voir Lunules / Lune / Les gardes du fortin

 

 

 

 

Suite

*        Voyageur de commerce

*        Chemin de la fourmi sur pavé, cylindre

*        Graphe et organisation de tournois

*         Autres sur ce thème

*           EulerBiographie

Voir

*         Dominos et graphe

*         Dualité

*         Échiquier et graphe

*         Énigmes et paradoxes

*         Intelligence artificielle

*         JeuxIndex

*         Le parcours du cavalier

*         Les neufs points

*         Logique formelle

*         Raisonnement

*         TopologieGlossaire

*         Tour de Brahmâ

DicoNombre

*         Nombre 2

Site

*         Graphes de Marc Beveraggi

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Logique/DeuxEuler.htm