cube en fil de fer

gimax
gimax
dans Combinatoire et Graphes
Bonjour

Je suis tombé sur l'exercice suivant en théorie des graphes, sur le thème des graphes eulériens :

On dispose d'un fil de fer de 120 cm
1)Est-il possible de construire un squelette de cube de 10 cm de côté sans couper le fil de fer ?
2)Sinon, combien de fois au minimum faut-il le couper ?

Voici ce que j'ai fait :

1) On peut fabriquer le cube en un seul tenant si et seulement si le cube est un graphe eulérien ou semi-eulérien, la première condition est équivalente à "tous les sommets sont de degrés pairs" et la seconde à "Deux sommets exactement sont de degrés impairs".
Dans le cas du cube, tous les sommets sont de degré 3, donc la réponse est non.

2) J'ai trouvé 3. J'ai trouvé un découpage en 3 parties qui fonctionne. Pour montrer qu'on ne peut pas couper en 2 parties, j'ai fait l'étude de cas suivante : il y a 8=2+6=3+5=4+4 sommets. Notons A et B les deux parties, alors

- si A de cardinal 2, on peut vérifier que dans dans B, les 6 sommets sont de degré 3 (et donc on doit couper B)

- si A de cardinal 3, on peut vérifier que dans dans B, les 5 sommets sont de degré 3

- si A de cardinal 4, les 4 autres sommets sont de degré 3

J'aimerais savoir s'il y a une manière de le voir plus conceptuelle qui ne nécessite pas cette étude au cas par cas.

Merci d'avance.

Réponses

  • gimax
    gimax
    Bon, je pense que je me suis trompé quand j'ai cru trouver un découpage en trois parties. En revanche, j'ai bien des découpages en 4 parties.

    J'imagine que si c'est bien 4 le minimum, on doit pouvoir éliminer 3 comme on a éliminé 2. Je réitère donc ma question : y a-t-il plus conceptuel ?
  • claude quitté
    claude quitté
    @gimax
    Demande d'une précision : est ce que, pour toi, un découpage en 3 parties d'un graphe (je reprends tes termes) est une partition des arêtes en 3 cycles ?
  • gimax
    gimax
    @Claude Quitté : Non, c'est juste une partition des arêtes, pas forcément en cycles, ça peut être des chaînes.
  • GaBuZoMeu
    GaBuZoMeu
    Quand on a une partition de l'ensemble des arêtes d'un graphe en chaînes eulériennes, un sommet avec un nombre impair d'arêtes adjacentes est forcément une extrémité d'une des chaînes eulérienne. Chaque chaîne eulérienne a deux extrémités, ou zéro si elle est fermée.

    Conclusion pour le cube ...
  • gimax
    gimax
    Je suis désolé GaBuZoMeu, j'avais déjà bien vu ce que vous dites sur les sommets de degrés impairs qui sont nécessairement des extrémités de chaînes eulériennes. Mais je ne vois pas comment conclure.

    Je suis désolé, vous semblez dire que c'est trivial une fois qu'on a dit ça, mais je ne le vois pas du tout. Je suis désolé d'être aussi bête...
  • GaBuZoMeu
    GaBuZoMeu
    1) Chaque sommet ayant un degré impair est extrémité d'au moins une chaîne eulérienne de la partition
    2) Chaque chaîne eulérienne de la partition a deux ou zéro extrémités.
    3) Le cube a 8 sommets de degrés impairs.
    4) Le nombre de chaînes eulériennes de la partition est donc au moins ...
  • gimax
    gimax
    Bon sang mais c'est bien sûr ! Un très grand merci pour votre patience !
  • GaBuZoMeu
    GaBuZoMeu
    Pour compléter.
  • gimax
    gimax
    :-D
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 3

Seirios +2 Invités