Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
- Accueil
- » Entraide (supérieur)
- » Arbres et coloration
- » Répondre
Répondre
Résumé de la discussion (messages les plus récents en premier)
- bridgslam
- 18-05-2021 12:38:38
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
- maths48
- 03-05-2021 20:33:54
Très intéressant cette petite parenthèse ! Ça ajoute beaucoup à un "simple exercice".
Merci à vous,
Bonne soirée
- bridgslam
- 03-05-2021 17:18:35
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
- maths48
- 03-05-2021 15:58:58
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}.
- bridgslam
- 03-05-2021 15:39:33
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
- Fred
- 03-05-2021 13:07:38
Oui, c'est cela.
- maths48
- 03-05-2021 10:36:08
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
- Fred
- 03-05-2021 07:04:34
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.
- maths48
- 02-05-2021 22:25:03
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
- maths48
- 02-05-2021 20:59:48
Je n'ai pas encore traité la question 2 justement, je ne voyais pas comment y répondre...
- Fred
- 02-05-2021 16:28:27
Je ne comprends pas trop ce qui te gêne.... Normalement, tu as vu à la question 2 comment enlever un sommet???
- maths48
- 02-05-2021 11:57:37
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
- Fred
- 01-05-2021 16:27:47
Bonjour,
Je pense qu'on te demande plutôt de conjecturer que si $T$ admet $n$ sommets, alors $p(T)=3\times 2^{n-1}$.
F.
- maths48
- 01-05-2021 10:48:30
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