Hypercube (graphe)

Les hypercubes, ou n-cubes, forment une famille de graphes. Dans un hypercube , chaque sommet porte une étiquette de longueur sur un alphabet , et deux sommets sont adjacents si leurs étiquettes ne diffèrent que d'un symbole. C'est le graphe squelette de l'hypercube, un polytope n-dimensionnel, généralisant la notion de carré (n = 2) et de cube (n = 3). Dans les années 1980, des ordinateurs furent réalisés avec plusieurs processeurs connectés selon un hypercube : chaque processeur traite une partie des données et ainsi les données sont traitées par plusieurs processeurs à la fois, ce qui constitue un calcul parallèle. L'hypercube est couramment introduit pour illustrer des algorithmes parallèles, et de nombreuses variantes ont été proposées, soit pour des cas pratiques liés à la construction de machines parallèles, soit comme objets théoriques. L'hypercube consiste en deux sommets d'étiquettes et ; les étiquettes de ces sommets étant différentes par un seul symbole, ils sont donc reliés. Pour passer à la dimension supérieure, on fabrique une copie du graphe : à la partie d'origine, on rajoute le symbole , et sur la partie copiée le symbole ; chaque sommet de la partie d'origine est ensuite relié à son équivalent dans la copie. Ainsi, consiste en quatre sommets étiquetés , , et . L'illustration ci-dessous montre en rouge les arêtes connectant les sommets d'origine à leurs équivalents dans la copie, et l'exemple se poursuit jusqu'à et . Cette méthode de construction est récursive, puisque pour construire on se fonde sur . Fichier:Hypercube-dim1.PNG → Fichier:Hypercube-dim2.PNG → Fichier:Hypercube-dim3.PNG → Fichier:Hypercube-dim4.PNG On peut aussi définir comme le produit cartésien de graphes complets , soit : Enfin, on peut construire le graphe directement en appliquant sa définition. On dispose sommets, et chacun a une étiquette unique dans l'espace vectoriel , c'est-à-dire une étiquette de la forme . Deux sommets sont reliés par une arête s'ils diffèrent exactement sur un symbole de leurs étiquettes, soit formellement pour le graphe : Le graphe hypercube est le graphe hexaédrique et est le graphe tesseract.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (1)

Concepts associés (30)

Séances de cours associées (15)

Efficient Data Structures For Decision Diagrams

Stéphane Rabie

Dynamic Programming Optimization (DPOP) is an algorithm proposed to solve distributed constraint optimization problems. In order to represent the multi-values functions manipulated in this algorithm, a data structure called Hypercube was implemented. A more efficient data structure, the Utility Diagram, was then proposed as an alternative to the Hypercube. DPOP also required the implementation of several operations (such as join, project, slice, split and reorder) on these two data structures. This project is a follow-up of Nacereddine Ouaret’s master thesis, which consisted in implementing all of these data structures and theirs associated operations. As DPOP may have to work on very large decision diagrams, and perform a lot of successive operations on them, having implementations which are efficient in term of speed and memory is critical. The aim of this project was therefore to seek for new ways to improve the already implemented functions for hypercubes and utility diagrams, both in term of execution time and memory consumption. This report will thus first present a quick overview of hypercubes, utility diagrams, and their associated operations (a more complete description of these objects, as well as the details about their original implementation, can be found in Nacereddine Ouaret’s report on Efficient Data Structures for Decision Diagrams). The second part will then cover various improvements made to their implementation during the course of this project. Finally, a variant for the methods used by hypercube, more economical in term of memory as it reuses existing hypercubes rather than creating new ones, will be presented.

2009

Hypercube (graphe)

Partial cube

In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels.

Snake-in-the-box

The snake-in-the-box problem in graph theory and computer science deals with finding a certain kind of path along the edges of a hypercube. This path starts at one corner and travels along the edges to as many corners as it can reach. After it gets to a new corner, the previous corner and all of its neighbors must be marked as unusable. The path should never travel to a corner which has been marked unusable.

Relations Binaires et Produits Cartésiens MATH-110(a): Advanced linear algebra I

Explore les relations binaires, les produits cartésiens et les applications entre les ensembles, en soulignant leurs propriétés et leur importance.

Profondeur-première recherche: Traverser et trier les graphiques CS-250: Algorithms I

Explore la recherche en profondeur, la recherche en largeur, la représentation graphique et le tri topologique dans les graphiques.

Séance de cours 4 : Espaces Hilbert et solutions uniques

Couvre les espaces Hilbert et les solutions uniques dans les espaces fonctionnels, en mettant l'accent sur le théorème Lax-Milgram.