cube en fil de fer
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
- 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.
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
- 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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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 ?
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 ?
Conclusion pour le cube ...
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...
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 ...