NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 10/01/2016

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

 

Ivrogne

Cinq pays

Chemin le plus court

Chemin eulérien

Trois maisons

Arbre de distribution

Graphe planaire

Petit monde

Voyageur de commerce

Colonies de fourmis

 

Sommaire de cette page

>>> Plus court chemin

>>> Villes disposées en carré

>>> Calcul de la dérivée

 

 

 

 

CHEMIN LE PLUS COURT

 

Comment concevoir des réseaux de distribution les plus courts entre villes. Évidemment le trajet doit être minimisé entre chacune des villes prises deux à deux. Occasion de calculer une dérivée impliquant une racine carrée.

 

 

PLUS COURT CHEMIN

 

Trois points

 

*    La longueur de route la plus courte entre les trois villes est obtenue avec la figure ci-contre, formant des angles de 120°.

*    Vrai que si chacun des angles du triangle ABC est inférieur à 120°.

 

Voir Cas du triangle équilatéral

 

 

 

Quatre points

 

*    On prend un point E au centre du quadrilatère ABCD.
 

*    Avec E et deux des points (AB puis CD), on cherche les triangles dont les angles sont inférieurs à 120°, et on se ramène au cas de trois points.
 

*    Il faut ajuster les deux figures à trois points par tâtonnement.

 

 

 

Cas des villes sur les sommets d'un carré

 

*    La première idée qui vient à l'esprit consiste à dessiner les diagonales du carré. Il est clair que les villes sont à égale distance les unes des autres. Mais est-ce que le réseau routier est de longueur minimale?
L = 2,828a, est-ce Lmin?.

*    Notez que le trajet ABCD = 3a, d'abord plus long que le trajet diagonales, ne répond pas à la question car AB = a, AC= 2a et AD = 3a.

 

Voir Théorème de Pythagore

 

 

*    Étudions le réseau indiqué sur la figure où les angles sont à 120°, comme proposé ci-dessus.

*    Comme vous le devinez nous allons voir que la longueur du réseau est plus courte que celle du réseau en diagonales.

*    Pour cela nous devons recourir au calcul de l'optimum de L en fonction de l'écart e. Soit, faire intervenir sa dérivée.

 

 

 

 

Fonction à étudier:

L(e) =

e + 2 (2a² – 2ae + e²)1/2

Sa dérivée:

L'(e) =

Maximum pour une dérivée nulle.

Mis au carré:

2(a – e) =

 

4(a – e)² =

 

Nouvelle équation:

0 =

3e² – 6 ae + 2a²

Dont les solutions sont:

Solution la plus petite retenue.

e =

Soit pour L:

L =

e + 2 (2a² – 2ae +e²)1/2

Intermédiaire de calcul:

2a² – 2ae +e² 

= 4/3 a²

Reprise de L:

 

L = 2, 73 a

alors qu'avec la solution diagonale

L = 2,83 a

L 

=2,732… a

 

  

 

Calcul de la dérivée

*    Quelle est la dérivée de:

 L(e) =

e + 2 (2a² – 2ae + e²)1/2

*    Ici, il s'agit de dériver les termes en e. Dérivée implique une notion de vitesse.

En pratique et en gros, tous les termes descendent d'un degré et les exposants se retrouvent en facteurs.

Exemple

a xr

a r xr – 1

Ici

e

2a² – 2ae +

1

0 – 2a + 2e.

*    Pour une racine carrée, la dérivée est un peu curieuse! On dérive l'expression sous radical et on divise par deux fois la racine elle-même.

Exemple

a y1/2

Ici, dérivation par rapport à e:

(2a² – 2ae + e²)1/2

Et pour L(e)

L'(e)

=

Voir Autre exemple de dérivée avec racine

 

 

 

Bilan

Nous venons de voir le cas de trois ou quatre points. Le problème se complique énormément avec plus de quatre points. Voir le cas du voyageur de commerce.

 

 

 

 

Suite

*         Chemin eulérien

*         Chemin de la fourmi sur pavé, cylindre

Voir

*         Diagramme de Venn

*         Dominos et graphe

*         Échiquier et graphe

*         Énigmes et paradoxes

*         Intelligence artificielle

*         JeuxIndex

*         Logique formelle

*         Raisonnement

*         TopologieGlossaire

Cette page

http://villemin.gerard.free.fr/LogForm/GrChemin.htm