Nombre d'intersection

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

La mise en forme de cet article est à améliorer (décembre 2025).

La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».

Comment faire ?

Les points d'amélioration suivants sont les cas les plus fréquents. Le détail des points à revoir est peut-être précisé sur la page de discussion.

Les titres sont pré-formatés par le logiciel. Ils ne sont ni en capitales, ni en gras.
Le texte ne doit pas être écrit en capitales (les noms de famille non plus), ni en gras, ni en italique, ni en « petit »…
Le gras n'est utilisé que pour surligner le titre de l'article dans l'introduction, une seule fois.
L'italique est rarement utilisé : mots en langue étrangère, titres d'œuvres, noms de bateaux, etc.
Les citations ne sont pas en italique mais en corps de texte normal. Elles sont entourées par des guillemets français : « et ».
Les listes à puces sont à éviter, des paragraphes rédigés étant largement préférés. Les tableaux sont à réserver à la présentation de données structurées (résultats, etc.).
Les appels de note de bas de page (petits chiffres en exposant, introduits par l'outil « Source ») sont à placer entre la fin de phrase et le point final^{[comme ça]}.
Les liens internes (vers d'autres articles de Wikipédia) sont à choisir avec parcimonie. Créez des liens vers des articles approfondissant le sujet. Les termes génériques sans rapport avec le sujet sont à éviter, ainsi que les répétitions de liens vers un même terme.
Les liens externes sont à placer uniquement dans une section « Liens externes », à la fin de l'article. Ces liens sont à choisir avec parcimonie suivant les règles définies. Si un lien sert de source à l'article, son insertion dans le texte est à faire par les notes de bas de page.
La présentation des références doit suivre les conventions bibliographiques. Il est recommandé d'utiliser les modèles {{Ouvrage}}, {{Chapitre}}, {{Article}}, {{Lien web}} et/ou {{Bibliographie}}. Le mode d'édition visuel peut mettre en forme automatiquement les références.
Insérer une infobox (cadre d'informations à droite) n'est pas obligatoire pour parachever la mise en page.

Pour une aide détaillée, merci de consulter Aide:Wikification.

Si vous pensez que ces points ont été résolus, vous pouvez retirer ce bandeau et améliorer la mise en forme d'un autre article.

En théorie des graphes, le nombre d'intersection d'un graphe $G=(V,E)$ est le nombre minimal d'éléments nécessaires pour représenter $G$ sous forme de graphe d'intersection d'ensembles finis. Dans cette représentation, chaque sommet correspond à un ensemble et deux sommets sont reliés par une arête dès que leurs ensembles ont un élément commun. Le nombre d'intersection est aussi égal au nombre minimal de cliques (sous-graphes dont les arêtes relient toutes les paires de sommets) nécessaires pour recouvrir toutes les arêtes du graphe $G$ ^[1]^,^[2]. Ce nombre, et le problème associé consistant à le calculer, ont été étudiés sous de nombreux noms alternatifs.

Les applications du nombre d'intersection comprennent l'ordonnancement des opérations sur des ordinateurs à très longs mots d'instruction (Very long instruction word), l'allocation de bande passante dans les réseaux à fibres optiques, la visualisation de données à l'aide d'écrans à lettres compacts, l'analyse des réseaux trophiques en biologie et l'inférence des complexes protéiques à partir des réseaux d'interaction protéine-protéine.

Un graphe avec sommets $n$ et $m$ arêtes a un nombre d'intersection majoré par $\min(m,n^{2}/4)$ . Calculer ou approximer le nombre d'intersection est un problème NP-difficile, mais traitable avec un paramètre fixe.

Les deux formulations équivalentes du nombre d'intersection, en termes de graphes d'intersection ou en termes de cliques qui recouvrent toutes les arêtes, ont été à l'origine de multiples noms pour ce concept et pour le problème informatique de la recherche d'un graphe d'intersection ou d'une couverture par cliques.

Un ensemble de cliques recouvrant toutes les arêtes d'un graphe est appelé Couverture d'arêtes par cliques ^[3] ou simplement Couverture par cliques, bien que ce dernier terme soit ambigu : une couverture de cliques peut également désigner un ensemble de cliques recouvrant tous les sommets du graphe ^[4]. Parfois, le terme « recouvrement » est utilisé à la place de « couverture » ^[5]. Le nombre d'intersection est aussi parfois appelé Nombre de couverture d'arêtes par cliques ^[6] ou Nombre de couverture de cliques ^[7].

Le problème du calcul du nombre d'intersection a été appelé le problème du nombre d'intersection^[8], le problème de la base du graphe d'intersection ^[9], la couverture par cliques^[9], le problème de la couverture d'arêtes par des cliques ^[8], et (en raison de l'une de ses premières applications) le problème du conflit de mots clés^[2].

Définitions

Graphes d'intersection

Soit ${\mathcal {F}}$ être une famille d'ensembles. Le graphe d'intersection de ${\mathcal {F}}$ est un graphe non orienté qui possède un sommet pour chaque ensemble de ${\mathcal {F}}$ et une arête entre chaque paire d'ensembles ayant une intersection non vide. Tout graphe peut être représenté comme un graphe d'intersection de cette manière^[10].

Le nombre d'intersection d'un graphe $G$ est le plus petit nombre telle qu'il existe une représentation de ce type pour laquelle l'union des ensembles dans ${\mathcal {F}}$ a $k$ éléments^[9].

Couverture d'arêtes par cliques

Le nombre d'intersection d'un graphe est aussi défini comme le plus petit nombre de cliques dans $G$ ( sous-graphes complets de $G$ ) qui recouvrent toutes les arêtes de $G$ ^[1]^,^[11]. Un ensemble de cliques possédant cette propriété est appelé « couverture d'arêtes par cliques » et pour cette raison, le nombre d'intersection est aussi parfois appelé « nombre de couverture d'arêtes par cliques »^[6].

Équivalence

L'égalité du nombre d'intersections et du nombre de couvertures d'arêtes par cliques admet une démonstration concise.

D'une part, supposons que $G$ soit le graphe d'intersection d'une famille ${\mathcal {F}}$ d'ensembles dont l'union $U$ a $k$ éléments. Pour chaque élément $x\in U$ , les ensembles dans ${\mathcal {F}}$ qui contiennent $x$ forment une clique $K_{x}$ dans $G$ , car ces ensembles possède (deux à deux) une intersection non vide contenant $x$ . De plus, les cliques ainsi formées recouvrent chaque arête dans $G$ : si deux ensembles dans ${\mathcal {F}}$ ont une intersection non vide alors il existe une arête entre ces deux ensembles et cette arête est contenue dans la clique $K_{x}$ pour chaque élément $x$ qui appartient à leur intersection. Par conséquent, les arêtes de $G$ peut être couvert par $k$ cliques, une par élément de $U$ ^[11].

Réciproquement, si les arêtes du graphe $G$ peuvent être couvertes par $k$ cliques, alors chaque sommet $v$ de $G$ peut être représenté par l'ensemble des cliques de cette couverture qui contiennent $v$ . Deux de ces ensembles de cliques, pour deux sommets $u$ et $v$ , ont une intersection non vide si et seulement s'il existe une clique dans la couverture qui contient à la fois $u$ et $v$ . Si cette clique contenant $u$ et $v$ existe, alors elle contient également l'arête $uv$ , qui est une arête de $G$ . Inversement, si $uv$ est une arête dans $G$ , alors elle est couverte par une clique ; cette clique contient à la fois $u$ et $v$ , elle appartient donc à l'intersection des ensembles de cliques qui représentent $u$ et $v$ . Par conséquent, une couverture par des cliques conduit à une représentation d'intersection avec $k$ éléments^[11].

Applications

La représentation abstraite d'un graphe comme un graphe d'intersection d'ensembles peut être utilisée pour construire des représentations géométriques d'intersection plus concrètes de ce même graphe. En particulier, si un graphe possède un nombre d'intersection $k$ , il peut être représenté comme un graphe d'intersection de $k$ hypersphères unitaires de dimension n. La dimension minimale des hypersphères dans une telle représentation est appelée sphéricité d'un graphe, de sorte que la sphéricité est inférieure ou égale au nombre d'intersection^[6].

Un recouvrement par cliques peut servir de schéma d'étiquetage d'adjacence pour un graphe. Chaque sommet est étiqueté par une valeur binaire, permettant de tester rapidement l'existence d'une arête entre deux sommets en comparant leurs valeurs. Ces étiquettes comportent un bit par clique : zéro si le sommet n'appartient pas à la clique, un s'il y appartient. Avec ce schéma, deux sommets sont adjacents si et seulement si la valeur binaire de leurs étiquettes est non nulle. La longueur des étiquettes correspond au nombre d'intersection du graphe. Lorsque cette longueur est faible, une représentation informatique du graphe utilisant uniquement ces étiquettes consomme moins de mémoire que les méthodes explicites telles que les listes d'adjacence et permet des tests d'adjacence plus rapides. Cette méthode a été utilisée par E. Kellerman d'IBM dans une des premières applications des nombres d'intersection, pour étiqueter un ensemble de mots-clés et détecter rapidement les conflits. C’est pourquoi le problème du calcul des nombres d’intersection est également appelé problème de conflit de mots-clés^[12]^,^[13]. De même, en géométrie algorithmique, les représentations basées sur le nombre d’intersection ont été considérées comme une représentation compacte pour les graphes de visibilité, bien qu’il existe des entrées géométriques pour lesquelles cette représentation nécessite un nombre de cliques quasi quadratique^[14].

Bornes supérieures

Tout graphe ayant $m$ arêtes a un nombre d'intersection majoré par $m$ . Cela découle de l'observation que chaque arête est elle-même une clique à deux sommets. Il y a $m$ de ces cliques, et ensemble elles recouvrent tous les bords, formant ainsi une couverture d'arêtes par cliques de taille $m$ ^[15].

En outre, tout graphe ayant $n$ sommets a un nombre d'intersection majoré par $\lfloor n^{2}/4\rfloor$ . Un résultat plus fort est que les arêtes d'un graphe à $n$ sommets peut être couvert par au plus $\lfloor n^{2}/4\rfloor$ cliques, chacune étant soit une arête simple, soit un triangle. Un algorithme glouton peut trouver cette couverture en supprimant deux sommets adjacents et en s'appelant récursivement sur le graphe restant. Après avoir rétabli les deux sommets supprimés, l'algorithme ajoute à la couverture chaque triangle auquel ils appartiennent, ce qui couvre toutes les arêtes les reliant à des voisins communs. Toutes les arêtes restantes reliant l'un des deux sommets supprimés à un de leurs voisins, sans former de triangle, sont couvertes par des cliques de deux sommets. S'il n'y a pas de triangle contenant les deux sommets supprimés, l'arête entre eux est également couverte par une clique de deux sommets. Par hypothèse de récurrence, la couverture du graphe après suppression des deux sommets comporte au plus $\lfloor (n-2)^{2}/4\rfloor$ cliques. Les deux sommets supprimés appartiennent à au plus $n-1$ autres cliques, il y a égalité lorsque tous les autres sommets sont des voisins non partagés et que l'arête entre les deux sommets doit être utilisée comme clique. L'addition de ces deux quantités donne $\lfloor n^{2}/4\rfloor$ cliques au total^[2]^,^[11]. Ceci généralise le théorème de Mantel selon lequel un graphe sans triangle possède au plus $\lfloor n^{2}/4\rfloor$ arêtes, car dans un graphe sans triangle, la seule couverture optimale d'arêtes par cliques a une clique par arête et donc le nombre d'intersections est égal au nombre d'arêtes^[2].

Une borne encore plus précise est possible lorsque le nombre d'arêtes est strictement supérieur à ${\tfrac {n^{2}}{4}}$ . On note $p$ le nombre de paires de sommets non reliés par une arête dans un graphe $G$ donné et $t$ l'unique entier pour lequel $(t-1)t\leq p<t(t+1)$ . Alors le nombre d'intersection de $G$ est au plus $p+t$ ^[2]^,^[16]. Les graphes qui sont complémentaires d'un graphe creux ont de petits nombres d'intersection : le nombre d'intersection de tout graphe $G$ à $n$ sommets est au plus $2e^{2}(d+1)^{2}\ln n$ , où $e$ est la base du logarithme naturel et $d$ est le degré maximal du graphe complémentaire de $G$ ^[5].

Il ressort des résultats sur la structure des graphes sans étoile que, lorsqu'un graphe sans étoile connexe à $n$ sommets possède au moins trois sommets indépendants, il a un nombre d'intersection inférieur ou égal à $n$ . Il reste à déterminer si cela est vrai pour tous les graphes sans étoile sans qu'ils possèdent nécessairement de grands ensembles indépendants^[7]. Les graphes adjoints (line graph), qui représentent les arêtes et les paires d'arêtes tangentes d'un autre graphe $G$ , constituent une sous-classe importante des graphes sans étoile. Une couverture optimale de cliques d'un graphe adjoint $L(G)$ peut être formé avec une clique pour chaque triangle dans $G$ qui possède deux ou trois sommets de degré 2, et une clique pour chaque sommet de degré au moins deux qui n'est pas un sommet de degré deux de l'un de ces triangles. Le nombre d'intersection est le nombre de cliques de ces deux types^[17].

Dans le modèle Erdős – Rényi – Gilbert de graphes aléatoires, dans lequel tous les graphes à $n$ sommets étiquetés sont équiprobables (ou, de manière équivalente, chaque arête est présente ou absente, indépendamment des autres arêtes, avec une probabilité ${\tfrac {1}{2}}$ ), le numéro d'intersection d'un graphe aléatoire à n sommets est, avec une forte probabilité à un facteur constant près, de ${\frac {n^{2}}{\log ^{2}n}},$ Cette valeur est plus petite d'un facteur de $\log ^{2}n$ que le nombre d'arêtes. Dans ces graphes, les cliques maximales possèdent (avec une forte probabilité) un nombre logarithmique de sommets, ce qui implique qu'il en faut autant pour couvrir toutes les arêtes. L'autre sens de la borne consiste à prouver qu'il est possible de trouver suffisamment de cliques de taille logarithmique pour couvrir la plupart des arêtes, les arêtes restantes pouvant être couvertes par des cliques à deux sommets^[18]^,^[19].

Les premières recherches sur les nombres d'intersection consistaient en grande partie à calculer ce nombre pour divers graphes spécifiques, tels que les graphes formés en supprimant un sous-graphe complet ou bine en supprimant un couplage parfait d'un graphe complet plus grand^[20].

Complexité

Tester si un graphe $G$ a un nombre d'intersection inférieur ou égale à $k$ est un problème NP-complet^[9]^,^[17]^,^[13]. Par conséquent, calculer le nombre d'intersection d'un graphe donné est également NP-difficile. La difficulté du calcul du nombre d'intersections a été utilisée pour prouver que reconnaître les carrés des graphes scindés est NP-complet^[21].

Le problème du calcul du nombre d'intersection est cependant traitable à paramètre fixé : c'est-à-dire qu'il peut être résolu en un temps borné par un polynôme en $n$ multiplié par une fonction en $k$ , le nombre d'intersection. Cela peut être démontré en observant qu'il y a au plus $2^{k}$ des voisinages fermés distincts (le voisinage fermé d'un sommet est l'ensemble des voisins de ce sommets avec le sommet étudié). Or deux sommets appartenant à la même clique ont le même voisinage. Le graphe obtenu en sélectionnant un sommet par voisinage fermé possède le même nombre d'intersection que le graphe original^[4]^,^[22]. Par conséquent, en temps polynomial, l'entrée peut être réduite à un noyau plus petit avec au plus ${\textstyle 2^{k}}$ sommets. Appliquer une recherche exhaustive sur au plus $2^{k}!$ possibilités d'ensembles distincts de cliques aux sommets restants donne un temps doublement exponentiel en $k$ ^[4]^,^[23]. La dépendance doublement exponentielle sur $k$ ne peut pas être réduite à une simple exponentielle par une réduction au noyau de taille polynomiale, sauf si la hiérarchie polynomiale s'effondre ^[24]. Si l' hypothèse du temps exponentiel est vérifiée, une double dépendance exponentielle est nécessaire, que la noyau soit réduit ou non ^[23]. Sur les graphes de largeur arborescente bornée, la programmation dynamique sur une décomposition arborescente du graphe permet de trouver le nombre d'intersection en temps linéaire ^[25]^,^[26].

Des algorithmes plus efficaces sont connus pour certaines classes particulières de graphes. Le nombre d'intersection d'un graphe d'intervalles est toujours égal à son nombre de cliques maximales, calculable en temps polynomial^[27]^,^[28]. Plus généralement, pour les graphes cordaux, le nombre d'intersection peut être calculé par un algorithme qui considère les sommets dans un ordre d'élimination du graphe (un ordre dans lequel chaque sommet et ses voisins ultérieurs forment une clique). Pour chaque sommet $v$ , on forme une clique pour $v$ et ses voisins ultérieurs chaque fois qu'au moins une des arêtes incidentes à $v$ n'est couverte par aucune clique antérieure^[28]. Il est également possible de trouver le nombre d'intersections en temps linéaire dans les graphes d'arcs circulaires^[29]. Cependant, bien que ces graphes ne possèdent qu'un nombre polynomial de cliques possibles pour la couverture, le fait d'avoir peu de cliques ne suffit pas à simplifier le problème : il existe des familles de graphes avec un nombre polynomial de cliques pour lesquelles le calcul du nombre d'intersection reste NP-difficile^[8]. Le nombre d'intersection peut cependant être trouvé en temps polynomial pour les graphes dont le degré maximal est cinq, mais est NP-difficile pour les graphes de degré maximal six^[30]^,^[31]. Sur les graphes planaires, le calcul exact du nombre d'intersections reste NP-difficile, mais il existe un schéma d'approximation en temps polynomial basé sur la technique de Baker^[26].