Séminaire Mathématique de Béjaia
Volume 9, Numéro 1, Pages 21-24
2010-12-31
Plongement Et Placement De Certaines Classes D’arbres Dans L’hypercube
Auteurs : Kabyl Kamal . Berrachedi Abdelhafid .
Résumé
Un plongement de G(V, E) dans l’hypercube est défini par la donnée d’une application injective ϕ de l’ensemble des sommets de G dans l’ensemble des sommets de Q_n, et d’une application P_ϕ de l’ensemble des arêtes de G dans l’ensemble des arêtes de Q_n, qui associe à chaque arête uv de G une arête ϕ(u) ϕ(v) dans Q_n. Un graphe G = (V, E) est dit cubique s’il est plongeable dans Qn pour un certain n. On définit dans ce papier des nouvelles classes d’arbres pour lesquelles la dimension cubique est déterminée. On a donné, aussi, le nombre maximum de copies de certaines topologies qu’on peut placer dans un hypercube de dimension donnée.
Mots clés
Plongement, Hypercube, Placement, Arbres.
Les articles similaires
Kabyl Kamal
.
Berrachedi Abdelhafid
.
pages 19-22.
Kabyl Kamel
.
Berrachedi Abdelhafid
.
pages 25-28.
