Forum de mathématiques - Bibm@th.net

nrg

Invité

Arbre et graphe biparti

Bonjour,

Comment montrer que chaque arbre de diamètre d est un graphe biparti ?
Je pensais à quelque chose comme "un arbre est un graphe non orienté sans cycle donc ..."

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 049

Re : Arbre et graphe biparti

Salut,

  Avec un marteau : un graphe est biparti si et seulement s'il ne contient pas de cycle impair.
Et dans un arbre, il n'y a pas de cycle.

F.

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 049

Re : Arbre et graphe biparti

Re-

  Plus facilement, tu raisonnes par récurrence sur le nombre de sommet de l'arbre. Pour l'hérédité dans la récurrence, tu considères un arbre à n+1 sommets. Tu isoles une feuille. Le graphe auquel tu as enlevé cette feuille reste un arbre. Par hypothèse de récurrence, il est biparti.
Tu peux le colorier avec deux couleurs. Tu donnes ensuite à la feuille que tu as enlevé la couleur que n'a pas le sommet auquelle elle est liée.

F.

nrg

Invité

Re : Arbre et graphe biparti

Ah j'avais pas pensé à démontrer ça par récurrence, merci !