Arbres et coloration

[math47]

Bonsoir à tous,

Tout d'abord, voici l'énoncé de mon exercice :
On considère un arbre T à n sommets. On dénote p(T) le nombre de colorations propres de T avec les couleurs {1, 2, 3}.
1. Déterminez les valeurs p(T) pour tous les arbres à 2, 3, 4 et 5 sommets. Que pouvez-vous conjecturer sur la valeur de p(T) ?
2. Montrez qu’il existe un arbre T' à n − 1 sommets pour lequel p(T) = 2p(T').
3. Montrez par récurrence sur n la conjecture de la question 1.

Pour la question 1, par exemple pour un arbre à n = 2 sommets on peut colorer les deux sommets avec les couleurs (1,2), (1,3) et (2,3), doit-on également compter les couples (2,1), (3,1) et (3,2) ? Comme je doute sur la façon de compter cela me bloque sur le reste de mon exercice puisque je ne peux pas émettre de conjecture...

Merci d'avance de votre aide,
Bonne soirée
-----

[Médiat]

Bonjour,

doit-on également compter les couples (2,1), (3,1) et (3,2) ?

Oui, je ne vois pas pourquoi vous hésitez, de plus vous pouvez le vérifier facilement en comptant P(T) pour n = 1 et la question 2

[math47]

Bonjour, merci de votre réponse!

Une question : le terme "coloration propre" est utilisé seulement pour dire que l'on colorie de couleurs différentes deux sommets voisins, il n'y a pas notion de nombre minimal de couleurs ?

[math47]

Je trouve finalement pour n=2, on a p(T)=6
pour n=3, p(T)=12
pour n=4, p(T)=24
pour n=5, p(T)=48

La conjecture que je peux donc faire est celle donnée dans la question 2, c'est bien cela ?

[A voir en vidéo sur Futura]

[math47]

Je pense avoir la conjecture (si T admet n sommets, alors p(T)=3×2^(n−1)), j'ai donc essayé de résoudre la question 3 mais il manque quelque chose :
Initialisation : C'est vérifié pour n = 1
Hérédité : On considère que tous les arbres à n sommets ont 3×2^(n−1) colorations avec les couleurs {1,2,3} pour un n supérieur ou égal à 1 fixé. A-t-on un arbre à n+1 sommets vérifiant cette propriété?
(c'est ici que j'ai du mal, il faudrait enlever un sommet pour utiliser l'hypothèse de récurrence comme je fais ci-après, mais enlever un
sommet ne suffit pas, que manque-t-il ?)
D'après l'hypothèse de récurrence, cet arbre sur n sommets a 3×2^(n-1) colorations avec les couleurs {1,2,3}, c'est donc que l'arbre initial a 3×2^(n) colorations avec les couleurs {1,2,3}.
On a montré la propriété au rang n+1.
Conclusion : Tout arbre sur n supérieur ou égal à 1 sommets possède 3×2^(n-1) colorations avec les couleurs {1,2,3}.

Qu'en pensez-vous ?
Merci d'avance

[MissJenny]

bah moi j'aurais pas pris la peine de faire formellement une récurrence. Si tu construis l'arbre petit à petit à partir de n'importe quel sommet arbitraire : pour le premier sommet tu as 3 choix, pour le second, plus que 2, donc ça fait 6 choix et ensuite à chaque fois que tu ajoutes un sommet tu as deux choix, cela où que tu le connectes, donc c'est bien 6 x 2^(n-2) s'il y a n sommets.

[Médiat]

ensuite à chaque fois que tu ajoutes un sommet tu as deux choix, cela où que tu le connectes,

C'est ce qui s'appelle une récurrence !