Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 01-05-2021 10:48:30
- maths48
- Membre
- Inscription : 15-04-2021
- Messages : 185
Arbres et coloration
Bonjour à 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 je trouve 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 ?
Merci d'avance de votre aide,
Bonne journée
Hors ligne
#3 02-05-2021 11:57:37
- maths48
- Membre
- Inscription : 15-04-2021
- Messages : 185
Re : Arbres et coloration
Bonjour, merci beaucoup de votre réponse!
Maintenant que j'ai la conjecture j'ai 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
Dernière modification par maths48 (02-05-2021 11:57:52)
Hors ligne
#6 02-05-2021 22:25:03
- maths48
- Membre
- Inscription : 15-04-2021
- Messages : 185
Re : Arbres et coloration
Pour la question 2 :
En construisant l'arbre à partir d'un sommet v arbitraire : pour le premier sommet on a 3 choix, pour le second, plus que 2, ce qui donne 6 choix puis chaque fois qu'on ajoute un sommet on a deux choix, on a donc 3 x 2^(n-1) s'il y a n sommets. Par le même principe on remarque que pour n-1 sommets, le nombre de colorations s'élève à 3 x 2^(n-2).
On a :
p(T) = 3 x 2^(n-1)
p(T') = 3 x 2^(n-2)
or 2p(T') = 3 x 2(n-1) = p(T')
donc il existe un arbre T' à n − 1 sommets pour lequel p(T) = 2p(T').
Qu'en pensez-vous ?
Merci d'avance
Dernière modification par maths48 (02-05-2021 22:25:43)
Hors ligne
#7 03-05-2021 07:04:34
- Fred
- Administrateur
- Inscription : 26-09-2005
- Messages : 7 352
Re : Arbres et coloration
Bonjour,
En réalité, tu essaies de démontrer la question 2 en utilisant le résultat de la question 3, alors que l'on te demande de faire l'inverse : utiliser le résultat de la question 2 pour faire la question 3. D'ailleurs, dans le raisonnement que tu présentes à la question 2, tu fais un raisonnement par récurrence sans le dire : pour le premier 3 choix, pour le second, 2 choix, puis chaque fois qu'on ajoute un sommet 2 choix....
Pour faire la question 2 comme demandé, tu dois considérer T' un arbre extrait de T où tu as supprimé un sommet terminal. Comment obtenir une coloration propre de T? En choisissant une coloration propre de T', puis en choisissant une des deux couleurs pour le dernier sommet de T, couleur qui ne peut pas être égale à la couleur du sommet de T' auquel ce sommet est relié.
F.
Hors ligne
#8 03-05-2021 10:36:08
- maths48
- Membre
- Inscription : 15-04-2021
- Messages : 185
Re : Arbres et coloration
Bonjour,
Voici la rédaction pour la question 2 :
Considéreons T un arbre à n sommets et p(T) son nombre de colorations propres avec les couleurs {1,2,3}.
Soit T' = T\v, v étant une feuille et p(T') son nombre de colorations propres avec les couleurs {1,2,3}. Pour obtenir une coloration propre de T, il suffit d'ajouter la coloration de v (2 choix) à p(T').
D'où p(T) = 2p(T').
On a montré qu'il existe bien un arbre T' à n − 1 sommets pour lequel p(T) = 2p(T').
Qu'en pensez-vous ?
Bonne journée et merci d'avance
Dernière modification par maths48 (03-05-2021 10:36:28)
Hors ligne
#10 03-05-2021 15:39:33
- bridgslam
- Membre Expert
- Lieu : Rospez
- Inscription : 22-11-2011
- Messages : 1 913
Re : Arbres et coloration
Bonjour,
En faisant encore plus simple pour se ramener à un arbre réduit à un seul sommet , dans le cas de c couleurs,
on a donc [tex]c( c-1)^{n-1}[/tex] colorations propres d'un arbre à n sommets.
En effet T(1) = c.
Cela évite de partir de deux sommets avec un dénombrement moins évident.
Alain
Hors ligne
#11 03-05-2021 15:58:58
- maths48
- Membre
- Inscription : 15-04-2021
- Messages : 185
Re : Arbres et coloration
Merci à tous les deux.
Donc si je reprends la question 3, la modification suivante complète-t-elle la récurrence que je n'avais pas réussi ?
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é?
On a montré à la question précédente qu'il existe un arbre T' à n − 1 sommets pour lequel p(T) = 2p(T').
Donc 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}.
Hors ligne
#12 03-05-2021 17:18:35
- bridgslam
- Membre Expert
- Lieu : Rospez
- Inscription : 22-11-2011
- Messages : 1 913
Re : Arbres et coloration
Je rédigerais comme ceci avec c couleurs.
La relation est vraie pour n = 1 ( n nombre de sommets ).
Hypothèse de récurrence P(n) : supposons qu'un arbre [tex]A_n[/tex] quelconque à n sommets ait [tex]c . (c-1)^{n-1}[/tex] colorations propres.
Soit [tex]A_{n+1}[/tex] un arbre quelconque à n+1 sommets. Soit F une feuille de cet arbre, N son noeud de rattachement
(on a au moins deux sommets, donc N existe).
Colorer proprement cet arbre est équivalent à choisir une coloration propre quelconque de [tex]A_{n+1} - \{F\}[/tex] et une coloration de F distincte de celle de N.
Il y en a donc c-1 fois plus, soit : [tex]c . (c-1)^{n}[/tex] en utilisant l'hypothèse de récurrence, ainsi P(n+1) est vraie.
En résumant, la propriété est vraie pour tout n.
( en particulier on a montré que le nombre de colorations propres est indépendant de la structure de l'arbre, il ne dépend que du nombre de sommets... ce qui est vrai pour mal de propriétés des arbres , par exemple le nombre de sommets est toujours le nombre d'arêtes +1 ... mais ce genre de propriétés est faux dans le cas général, à nombre de sommets égal, ça dépend de la forme du graphe bien-sûr)
Il y a aussi la notion de nombre chromatique: la quantité minimum de couleurs à utiliser dans une coloration propre...
Pour un arbre non singleton, c'est deux ( il suffit de suivre une sous-arborescence en alternant ).
Alain
Hors ligne
#14 18-05-2021 12:38:38
- bridgslam
- Membre Expert
- Lieu : Rospez
- Inscription : 22-11-2011
- Messages : 1 913
Re : Arbres et coloration
Bonjour,
De rien. De bonnes présentations en live, mais c'est en anglais:
https://www.google.com/search?q=sarada+ … osfgNazvQM
Couvre beaucoup de thèmes des graphes. Nombreux schémas.
Alain
Hors ligne
Pages : 1