graphe - chemin de plus court

Édition du: 08/03/2024

INDEX Graphe Topologie Dénombrement Logique	GRAPHES
	Graphes – Introduction	Arbres – Introduction	Minimiser la voirie
	Chemin eulérien	Cinq pays	Chemin le plus court
	Graphe planaire	Trois maisons	Voyageur de commerce
	Graphe de Delaunay	Petit monde	Multiple et diviseurs
	Ivrogne	Colonies de fourmis	Nombres de Delannoy

Faites un double-clic pour un retour en haut de page

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.

Sommaire de cette page

>>> Plus court chemin

>>> Villes disposées en carré

>>> Calcul de la dérivée

Débutants

Dénombrement

Glossaire

Combinatoire

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 L_min?. 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 Arbres de Steiner / Énigme du raccordement des maisons	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 x^r		a r x^{r – 1}
Ici	e 2a² – 2ae + e²		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 y^1/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 …

Graphe – Index

Voir

Diagramme de Venn

Dominos et graphe

Échiquier et graphe

Énigmes et paradoxes

Intelligence artificielle

Jeux – Index

Logique formelle

Raisonnement

Topologie – Glossaire

Cette page

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