Concept

Graphe d'intersection

Résumé
En théorie des graphes, un graphe d'intersection est un graphe représentant les intersections d'une famille d'ensembles. Plus précisément, pour une famille d'ensembles finie donnée, on associe à chaque ensemble un sommet, et deux sommets sont reliés par une arête si les ensembles ont une intersection non nulle. Beaucoup de familles de graphe sont définies par l'intersection d'ensembles géométriques, par exemple des sphères dans le plan, ou des intervalles sur une droite. Ces représentations géométriques permettent parfois d'avoir des algorithmes plus efficaces. Propriétés Tout graphe est un graphe d'intersection : il suffit de considérer pour un nœud l'ensemble des arêtes adjacentes à ce nœud. Exemples
  • Un graphe d'intervalle est le graphe d'intersection d'un ensemble d'intervalles.
  • Les graphes cordaux sont les graphe d'intersection de sous-arbres d'un arbre.
  • Un graphe de disques est le graphe d'intersection d'une collection de disques.
  • Un graphe de per
À 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

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement