Concept

Hypercube (graphe)

Concepts associés (16)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Graphe médian

En théorie des graphes, un graphe médian est un type de graphe. Étant donné un triplet de nœuds dans un graphe, les médians de ces sommets sont les sommets se trouvant sur les plus courts chemins entre ces sommets. Un graphe médian est un graphe tel que pour tout triplet de nœuds il existe un unique médian. En théorie des graphes, les médians d'un triplet de sommets sont les sommets se trouvant sur les plus courts chemins entre ces sommets. Autrement dit, si est l'ensemble de sommets sur les plus courts chemins entre et , alors l'ensemble des sommets médians est .

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.

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.

Graphe distance-transitif

En théorie des graphes, un graphe non-orienté est distance-transitif si pour tous sommets u, v, x, y tels que u et v d'une part et x et y d'autre part sont à même distance, il existe un automorphisme de graphe envoyant u sur x et v sur y. Autrement dit, un graphe est distance-transitif si son groupe d'automorphisme agit transitivement sur chacun des ensembles de paires de sommets à même distance. Tout graphe distance-transitif est distance-régulier.

Code de Gray

Le code de Gray, également appelé code Gray ou code binaire réfléchi, est un type de codage binaire permettant de ne modifier qu'un seul bit à la fois quand un nombre est augmenté d'une unité. Cette propriété est importante pour plusieurs applications. Le nom du code vient de l'ingénieur américain Frank Gray qui publia un brevet sur ce code en 1953, mais le code lui-même est plus ancien. Le code de Gray est un codage binaire, c'est-à-dire une fonction qui associe à chaque nombre une représentation binaire.

Arête (géométrie)

En géométrie dans l'espace, une arête est une droite délimitant deux demi-plans qui constituent les faces d’un angle diédral, ou plus spécialement le côté d’une face d’un polyèdre. Plus généralement, une arête d'un solide géométrique est la ligne d'intersection de deux surfaces de ce solide. À ce titre, l'arête n'est pas nécessairement une droite euclidienne. Un angle formé par deux demi-droites perpendiculaires à l’arête, issues d'un point de l’arête et incluses dans chacune des faces d’un dièdre, ne dépend pas du choix du point.

Graph power

In graph theory, a branch of mathematics, the kth power G^k of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G^2 is called the square of G, G^3 is called the cube of G, etc. Graph powers should be distinguished from the products of a graph with itself, which (unlike powers) generally have many more vertices than the original graph.

Induced path

In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the sequence are not connected by any edge in G. An induced path is sometimes called a snake, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box problem.

Graphe de Hamming

Les graphes de Hamming forment une famille de graphes. Le graphe de Hamming de dimension d sur un alphabet de taille q est défini de la manière suivante : est le graphe dont les sommets sont , l'ensemble des mots de longueur sur un alphabet , où . Deux sommets sont adjacents dans s'ils sont à une distance de Hamming de 1, c'est-à-dire si leurs étiquettes ne diffèrent que d'un symbole. On peut construire le graphe de Hamming directement en appliquant sa définition : disposons sommets, chacun avec une étiquette .

Produit cartésien (graphe)

Le produit cartésien, ou somme cartésienne, est une opération sur deux graphes et résultant en un graphe . Parler de produit ou de somme pour cette opération n'est pas une contradiction, mais une explication basée sur deux aspects différents : la construction peut se voir comme un produit, tandis que de nombreuses propriétés sont basées sur la somme. Soient deux graphes et . Le produit cartésien est défini comme suit : Autrement dit, l'ensemble résultant des sommets est le produit cartésien .