Longueur de chemin dans un graphe d'ordre n
Réponses
-
Mon intuition est la suivante :
Si je regarde les (n-1) premiers arcs de ce chemin alors forcément j'ai un sommet qui a été répété deux fois.
Si c'est le sommet qui correspond à l'extrémité initiale de mon chemin alors j'ai fini puisque la répétition se fait forcément dans une extrémité terminale d'un autre arc que le premier.
Si c'est un autre sommet alors c'est comme si j'avais fais un "trajet inutile" puisque j'ai fais un cycle dont je pouvais a priori sortir (sinon ce serait infini) pour rejoindre l'extrémité initiale de mon chemin.
Mettons que je supprime tout les cycles de mon chemin (ça reste un chemin de i à j). Qu'est ce que je peux en déduire sur mes arcs ? Si je regarde par exemple, l'extremité terminale de mon premier arc alors comme j'ai interdis les cycles elle ne peut plus réapparaitre et ainsi de suite. Ainsi, après mon premier arc j'ai (n-2) options de sommets avant l'arc conclusif de mon chemin après le troisième j'en aurais (n-3) et donc après n arcs j'en aurais 0 et je ne pourrais pas avancer et comme je dois placer mon sommet conclusif c'est impossible donc j'ai forcément un chemin qui implique au plus n arcs.
Cela vous parait correct ?
-
ça paraît vraiment lourdingue comme explication.
Le résultat que tu cherches à démontrer est un résultat exact.
L'idée est évidement que les cycles peuvent être supprimés, et que tout chemin qui passe par plus de $n$ points contient forcément au moins un cycle.Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
L'hypocrisie est pire qu'une vérité qui fait mal. Franck Ntasamara.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.1K Toutes les catégories
- 59 Collège/Lycée
- 22.1K Algèbre
- 37.5K Analyse
- 6.3K Arithmétique
- 58 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 20 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.7K Géométrie
- 83 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 337 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 801 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres