Ivan Shishkin, Rye (1878)

Problems/Discrete mathematicsReviewed

Chemin eulérien dans un graphe fini

by Sequoia·
24
Difficulty scaleÉchelle de difficulté

This score reflects both the level of the required concepts and the difficulty of the solution.Ce score tient compte à la fois du niveau des notions nécessaires et de la difficulté de la résolution.

  1. 1–10First steps / middle schoolPremiers pas / collège
  2. 11–25Beginner / high schoolDébutant / lycée
  3. 26–50Intermediate / undergraduateIntermédiaire / licence
  4. 51–70Advanced / graduateAvancé / master
  5. 71–90Expert / specializedExpert / spécialisé
  6. 91–100Research levelNiveau recherche
These levels are approximate guides.Ces niveaux sont des repères approximatifs.
·
Français
FrançaisEnglish

Soit G=(V,E)G=(V,E) un graphe connexe finiEN. On dit qu’un chemin eulérien est une suite ordonnée d’arêtes qui passe par toutes les arêtes du graphe exactement une fois.

Picture6
En suivant les arêtes 1,2,3,4,5,6,7, on traverse toutes les arêtes du graphe (dont les sommets sont des losanges rouges) exactement une fois. C’est donc un chemin eulérien.

Quelle condition nécessaire et suffisante sur GG faut-il imposer pour qu’il contienne au moins un chemin eulérien ?

I solved itMark it doneAdd to my listKeep it in your list
I like this problem0 likes
Show related problems0

No related problems yet.

Solutions

0
Report

For an unclear, ambiguous, or possibly incorrect statement, please use the Discussion tab on the right. Report content that needs moderator intervention, such as dangerous, clearly non-mathematical, or plagiarized content.