Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Partial cube
Résumé
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. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.
was the first to study isometric embeddings of graphs into hypercubes. The graphs that admit such embeddings were characterized by and , and were later named partial cubes. A separate line of research on the same structures, in the terminology of families of sets rather than of hypercube labelings of graphs, was followed by and , among others.
Every tree is a partial cube. For, suppose that a tree T has m edges, and number these edges (arbitrarily) from 0 to m – 1. Choose a root vertex r for the tree, arbitrarily, and label each vertex v with a string of m bits that has a 1 in position i whenever edge i lies on the path from r to v in T. For instance, r itself will have a label that is all zero bits, its neighbors will have labels with a single 1-bit, etc. Then the Hamming distance between any two labels is the distance between the two vertices in the tree, so this labeling shows that T is a partial cube.
Every hypercube graph is itself a partial cube, which can be labeled with all the different bitstrings of length equal to the dimension of the hypercube.
More complex examples include the following:
Consider the graph whose vertex labels consist of all possible (2n + 1)-digit bitstrings that have either n or n + 1 nonzero bits, where two vertices are adjacent whenever their labels differ by a single bit.
Source officielle
À 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.