nombre chromatique d´un k-cube en scilab

[invitee75a2d43]

Bonjour,

J´ai deux questions dont l´une est technique: Je viens de voir que scilab propose quelques fonctions concernant la théorie des graphes, mais j´ai eu beau chercher, je n´ai rien trouvé ni concernant le nombre chromatique d´un graphe en générale, ni sur la possibilité de construire un graphe qui soit un cube.

En fait, ce qui m´intéresse, c´est le nombre chromatique d´un k-cube. Je crois avoir prouvé par récurrence qu´il est toujour égal à 2, mais je suis peu sûr de moi dans ma démonstration, et je me demande s´il n´y a pas un moyen plus directe.

Merci d´avance

Christophe
-----

[invite986312212]

salut,

on définit souvent le cube multidimensionnel de façon récursive, donc c'est naturel de raisonner par récurrence pour montrer qu'il est 2-colorable, autrement, avec la définition d'un k-cube qui se trouve ici:
http://www.personal.kent.edu/~rmuham...eory/defEx.htm
tu peux voir qu'on peut le colorier en deux couleurs selon la parité du nombre de 1.

[invitee75a2d43]

Merci, mais je viens de m´apercevoir que ma "démonstration" par récurrence ne tient pas.

[invitee75a2d43]

Et tu la ferais comment cette démonstration par récurrence?

[A voir en vidéo sur Futura]

[invite986312212]

le cube est biparti: c'est deux "faces" identiques, disons A et B, qui sont des (k-1)-cubes, reliées par des arêtes perpendiculaires aux faces (en langage quelque peu imagé). Deux sommets adjacents de A sont reliés à deux sommets adjacents de B (dans un cube "géométrique" A est un translaté de B), etc.

[invitee75a2d43]

merci je vais voir