Graphe d'intersection
Cet article est une ébauche concernant les mathématiques et l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
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 modifier
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 modifier
- 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[1].
- Un graphe de disques est le graphe d'intersection d'une collection de disques.
- Un graphe de permutation est le graphe d'intersection de segments dont les extrémités touchent deux droites parallèles.
Notes et références modifier
- (en) Fănică Gavril, « The intersection graphs of subtrees in trees are exactly the chordal graphs », Journal of Combinatorial Theory, Series B, vol. 16, , p. 47–56 (DOI 10.1016/0095-8956(74)90094-X)
