Graphique d'intersection

Formellement, un graphe d'intersection

en créant un sommet pour chaque ensemble , et en reliant deux sommets et par une arête chaque fois que les deux ensembles correspondants ont une intersection non vide , c'est-à-dire,

Tout graphe non orienté de constitué des arêtes incidentes à ; alors deux tels ensembles ont une intersection non vide si et seulement si les sommets correspondants partagent une arête. Par conséquent, .

et Pósa (1966) proposent une construction plus efficace, car elle requiert un nombre total d'éléments plus faible pour l'ensemble des S </sub>. Ce nombre est au plus égal n ^2/4 , où un graphe est le nombre total minimal d'éléments dans toute représentation d'intersection de ce graphe.

De nombreuses familles de graphes importantes peuvent être décrites comme des graphes d'intersection de types plus restreints de familles d'ensembles, par exemple des ensembles dérivés d'une certaine configuration géométrique :

• Un graphe d'intervalles est défini comme le graphe d'intersection des intervalles sur la droite réelle, ou des sous-graphes connectés d'un graphe de chemin .
• Un graphe d'indifférence peut être défini comme le graphe d'intersection des intervalles unitaires sur la droite réelle.
• Un graphe d'arcs circulaires est défini comme le graphe d'intersection des arcs sur un cercle .
• Un graphe polygone-cercle est défini comme l'intersection de polygones dont les sommets se trouvent sur un cercle.
• Une caractérisation possible d'un graphe cordal est celle du graphe d'intersection des sous-graphes connexes d'un arbre .
• Un graphe trapézoïdal est défini comme le graphe d'intersection des trapèzes formés par deux droites parallèles. Il s'agit d'une généralisation de la notion de graphe de permutation , qui est elle-même un cas particulier de la famille des graphes complémentaires des graphes de comparabilité , appelés graphes de cocomparabilité.
• Un graphe de disques unitaires est défini comme le graphe d'intersection des disques unitaires du plan.
• Un graphe circulaire est le graphe d'intersection d'un ensemble de cordes d'un cercle.
• Le théorème d'empilement de cercles stipule que les graphes planaires sont exactement les graphes d'intersection de familles de disques fermés dans le plan délimitées par des cercles non sécants.
• La conjecture de Scheinerman (désormais un théorème) affirme que tout graphe planaire peut aussi être représenté comme un graphe d'intersection de segments de droite dans le plan. Cependant, les graphes d'intersection de segments de droite peuvent également être non planaires, et la reconnaissance de tels graphes est complète pour la théorie existentielle des réels .
• Le graphe linéaire d'un graphe G est défini comme le graphe d'intersection des arêtes de G , où nous représentons chaque arête comme l'ensemble de ses deux extrémités.
• Un graphe de chaînes est le graphe d'intersection des courbes sur un plan .
• Un graphe a une boxicité k s'il est le graphe d'intersection de boîtes multidimensionnelles de dimension k , mais pas de dimension inférieure.
• Un graphe de cliques est le graphe d'intersection des cliques maximales d'un autre graphe.
• Un graphe bloc , ou arbre de cliques, est le graphe d'intersection des composantes biconnexes d'un autre graphe.

classes d'intersection de graphes , des familles de graphes finis qui peuvent être décrites comme les graphes d'intersection d'ensembles tirés d'une famille d'ensembles donnée. Il est nécessaire et suffisant que la famille possède les propriétés suivantes :

• Tout sous-graphe induit d'un graphe de la famille doit également appartenir à la famille.
• Tout graphe formé à partir d'un graphe de la famille en remplaçant un sommet par une clique doit également appartenir à la famille.
• Il existe une suite infinie de graphes dans la famille, chacun étant un sous-graphe induit du graphe suivant dans la suite, avec la propriété que chaque graphe de la famille est un sous-graphe induit d'un graphe de la suite.

Si les représentations graphiques d'intersection imposent en plus que différents sommets soient représentés par différents ensembles, alors la propriété d'expansion des cliques peut être omise.

Les ordres d'inclusion constituent un analogue en théorie de l' ordre des graphes d'intersection . De la même manière qu'une représentation d'intersection d'un graphe étiquette chaque sommet avec un ensemble de sorte que les sommets sont adjacents si et seulement si leurs ensembles ont une intersection non vide, une représentation d'inclusion f d'un poset étiquette chaque élément avec un ensemble de sorte que pour tout x et y dans le poset, x ≤ y si et seulement si f ( x ) ⊆ f ( y ).