Graphe distance-unité

En mathématiques, plus particulièrement en théorie des graphes, un graphe distance-unité est un graphe s'obtenant à partir d'un ensemble de points du plan euclidien en reliant par une arête toutes les paires de points étant à une distance de 1. Les arêtes peuvent se croiser si bien qu'un graphe distance-unité n'est pas nécessairement un graphe planaire. S'il n'y a pas de croisement entre les arêtes, alors le graphe est qualifié de graphe allumette. Tous les cycles et toutes les grilles ; N'importe quel hypercube, donc le graphe hexaédrique et le graphe tesseract ; Le graphe de Petersen ainsi que celui de Moser, de Harborth et de Golomb ; Le graphe roue W7 (c'est le seul graphe roue à être distance-unité) ; Le graphe papillon, le graphe longhorn, le graphe diamant, le graphe taureau, le graphe griffe, le graphe criquet, le graphe poisson, le graphe fléchette, le graphe fourche, le graphe cerf-volant, le graphe croix et le graphe mite. Paul Erdős posa le problème suivant en 1946 : étant donnés n points, comment estimer le nombre maximal de paires de points pouvant être à une distance de 1 sur le plan euclidien ? En d'autres termes quelle est la densité maximale d'un graphe distance-unité d'ordre n ? Ce problème est très lié au théorème de Szemerédi-Trotter. L'hypercube fournit une borne inférieure sur le nombre de paires de points proportionnelle à n log n. Le problème de Hadwiger-Nelson, introduit en 1944 par Hugo Hadwiger et Edward Nelson, concerne le nombre minimal de couleurs qu'il faut pour colorier le plan de façon que deux points à une distance de 1 ne soient jamais de la même couleur. Il peut être formalisé en théorie des graphes de la façon suivante : quel est le nombre chromatique maximal d'un graphe distance-unité ? Le problème est toujours ouvert mais le graphe de Golomb, avec son nombre chromatique égal à 4, fournit une borne inférieure. Un autre exemple connu, plus petit mais avec le même nombre chromatique, est le graphe de Moser. Cependant, cette borne a été améliorée en 2018 grâce à la découverte d'un graphe distance-unité de nombre chromatique 5.

À 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.

Concepts associés (7)

Séances de cours associées (4)

Graphe grille

In graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space \mathbb{R}^n, forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a lattice in the group-theoretical sense. Typically, no clear distinction is made between such a graph in the more abstract sense of graph theory, and its drawing in space (often the plane or 3D space). This type of graph may more shortly be called just a lattice, mesh, or grid.

Graphe de disques

En théorie des graphes, un graphe de disques (ou disk graph en anglais) est le graphe d'intersection d'une collection de disques. C'est une extension du concept de graphe d'intervalle à la dimension 2. Formellement, G est un graphe de disques s'il existe une collection de disques dans le plan dont les centres sont en bijection avec les sommets de G et telle que deux disques s'intersectent si et seulement si les sommets correspondants sont reliés par une arête dans G.

Graphe distance-unité

Alignement des graphiques : basé sur Wasserstein

Discute des défis à relever pour comparer les données non euclides, proposant une solution laplacienne pour l'alignement des graphiques et l'exploration d'un transport optimal pour le calcul de la distance des graphiques.

Szemerédi Régularité Lemme MATH-467: Probabilistic methods in combinatorics

Explore le lemme de régularité Szemerédi, la régularité électronique dans les graphes bipartites, la structure des supergraphes et les techniques d'induction.

Partitionnement aléatoire de faible diamètre MATH-513: Metric embeddings

Discute de la décomposition randomisée à faible diamètre et du partitionnement graphique pour les coupes de bord et la coloration.