L'hypercube a suscité de nombreuses études engendrant une littérature très dense aussi bien en mathématiques discrètes qu'en informatique. Cet intérêt sans cesse croissant est largement motivé par l'utilisation de sa structure dans de nombreux domaines (architectures parallèles, transfert de l'information, décision multicritère,...). Chacun peut s'étonner des raisons qui font que le cube soit le cube?. Sa simple définition peut déjà apporter une réponse quoique partielle à une telle question. Plusieurs propriétés spécifiques à l'hypercube ont, soit, défini de nouvelles classes de graphes, soit, fait ressortir le rôle remarquable joué par celui-ci dans plusieurs classes déjà existantes. Les (0, 2)-graphes sont une généralisation naturelle de l'hypercube. Il est maximal dans cette classe. Le thème de cette thèse consiste en la définition et la caractérisation de quelques classes de (0, 2)-graphes obtenues à partir de l'hypercube par rajout d'arêtes ou identification de sommets. Nous caractérisons au chapitre II, le graphe de l'hyperoctaèdre comme un {2(n-2), 2(n-1)}-graphe d'ordre 2n, et nous prouvons l'unicité de son cycle hamiltonien et cela à une équivalence naturelle près. Nous donnons, au chapitre III, une caractérisation de l'hypercube en tant que graphe distance-régulier de vecteur d'intersection {d, d-1, ..., 1; 1, 2, ..., d}. Une classe de (0, 2)-graphes minimaux -les graphes de Shrikhande généralisés- y est étudiée et une caractérisation des graphes de Laborde-Mulder comme (0, 2)-graphes de diamètre minimum [d/2] parmi ceux d'ordre 2d-1 et de degré d impair est donnée. Au chapitre IV, nous caractérisons parmi les hypercubes généralisés ceux qui sont des (0, 2)-graphes. Nous présentons une construction de (0, 2)-graphes non sommet-transitifs. On montre enfin que les graphes de Laborde-Mulder et du demi-cube sont plongeables dans le carré de l'hypercube. Dans un dernier chapitre, nous nous intéressons au problème d'existence de (0, 2)-graphe d'un ordre donné. Nous donnons une condition nécessaire d'existence de tels graphes pour un ordre impair. Nous montrons ensuite qu'à l'ordre 18 et 20, il n'existe pas de (0, 2)-graphes, en utilisant à cette fin un algorithme de construction de (0, 2)-graphes. Nous présentons enfin quelques résultats sur la structure locale des (0, 2)-graphes
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00344544 |
| Date | 07 March 1994 |
| Creators | Madani, Rafaï Mourad |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0107 seconds