Graphe à distance héréditaire

vignette| Exemple d'un graphe à distance héréditaire. En théorie des graphes, un graphe à distance héréditaire (aussi appelé graphe complètement séparable) est un graphe dans lequel les distances entre sommets dans tout sous-graphe induit connexe sont les mêmes que celles du graphe tout entier ; autrement dit, tout sous-graphe induit hérite les distances du graphe entier. Les graphes à distance héréditaire ont été nommés et étudiés pour la première fois par Howorka en 1977, alors qu'une classe équivalente de graphes a déjà été considérée en 1970 par Olaru et Sachs qui ont montré que ce sont des graphes parfaits. Les graphes à distance héréditaire constituent une classe de graphes d'intersection ; un modèle d'intersection a été donné par Gioan et Paul en 2012. La définition originale d'un graphe à distance héréditaire est la suivante : c'est un graphe G tel que, pour deux sommets u et v appartenant à un sous-graphe induit connexe H de G, un plus court chemin reliant u et v dans G est contenu dans H, de sorte que la distance entre u et v dans H est la même que la distance dans G. Les graphes à distance héréditaire peuvent être caractérisés de plusieurs autres manières équivalentes : Ce sont les graphes dans lesquels tout chemin induit est un chemin le plus court, ou de manière équivalente les graphes dans lesquels tout chemin qui n'est pas de longueur minimale a au moins une arête reliant deux sommets non consécutifs du chemin. Ce sont les graphes dans lesquels chaque cycle de longueur ≥ 5 a au moins deux diagonales qui se croisent. Ce sont les graphes dans lesquels, pour quatre sommets quelconques, deux au moins des trois sommes de distances , et sont égales. Ce sont les graphes qui n'ont pas de sous-graphe isométrique qui est un cycle de longueur ≥ 5, ou l'un des trois graphes suivants : un cycle à 5 sommets avec une corde, un cycle à 5 sommets avec deux cordes qui ne se croisent pas, et un cycle à 6 sommets avec une corde reliant des sommets opposés. vignette|upright=1.5| Les trois opérations qui permettent de construire tout graphe distance-héréditaire.

À 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 (24)

Personnes associées (2)

Unités associées (6)

Concepts associés (16)

Cours associés (1)

Séances de cours associées (6)

Largeur de clique

vignette|upright=1.6|Construction d'un graphe (ici un graphe à distance héréditaire) de largeur de clique 3 par une succession d'unions disjointes, de renommages et de fusions d'étiquettes. Les étiquettes des sommets sont affichées sous forme de couleurs. En théorie des graphes, la largeur de clique d'un graphe est l'un des paramètres qui décrit la complexité structurelle du graphe ; il est étroitement lié à largeur arborescente, mais contrairement à celle-ci, elle peut être bornée même pour des graphes denses .

Partition en cliques

En théorie des graphes, une couverture par cliques ou une partition en cliques d'un graphe non orienté est une partition des sommets du graphe en cliques, c'est-à-dire en des ensembles de sommets à l'intérieur desquels deux sommets sont adjacents. Un couverture par cliques minimale est une couverture de taille minimale, c'est-à-dire par un nombre minimal de cliques. Le problème de la couverture par cliques est le problème algorithmique qui consiste à trouver une couverture par cliques minimale.

Coloration gloutonne

droite|vignette|upright=1.4| Deux colorations gloutonnes du même graphe couronne pour des ordres différents sur les sommets. La numérotation de droite se généralise aux graphes bicolores à n sommets, et l'algorithme glouton utilise couleurs. Dans l'étude des problèmes de coloration de graphes en mathématiques et en informatique, une coloration gloutonne ou coloration séquentielle est une coloration des sommets d'un graphe obtenue par un algorithme glouton qui examine les sommets du graphe en séquence et attribue à chaque sommet la première couleur disponible.

PHYS-512: Statistical physics of computation

This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and

ON THE INDEPENDENCE NUMBER OF INTERSECTION GRAPHS OF AXIS-PARALLEL SEGMENTS

Jana Tabea Cslovjecsek

We prove that for any triangle-free intersection graph of n axis-parallel line segments in the plane, the independence number alpha of this graph is at least alpha n/4+ohm(root n). We complement this with a construction of a graph in this class satisfying ...

Ottawa2023

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n.Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed p ...

EPFL2023

Cographs constitute a small point in the atlas of graph classes. However, by zooming in on this point, we discover a complex world, where many parameters jump from finiteness to infinity. In the present paper, we identify several milestones in the world of ...

ELSEVIER2022

Modèles graphiques : Représentation des distributions probabilistes PHYS-512: Statistical physics of computation

Couvre les modèles graphiques pour les distributions probabilistes à l'aide de graphiques, de nœuds et de bords.

Méthode probabiliste et ses applications

Introduit la méthode probabiliste pour prouver l'existence des résultats dans la théorie des graphiques.

TrackMate: Analyse d'images et suivi des données

Présente TrackMate pour l'analyse d'image et le suivi des données, en mettant l'accent sur les caractéristiques, les défis et les conseils pratiques.