Arête transversale

En théorie des hypergraphes, une transversale est une partie des sommets qui rencontre toutes les arêtes d'un hypergraphe. C'est l'analogue du problème de couverture par sommets (vertex cover en anglais) chez les graphes.

On rappelle qu'un hypergraphe ${\displaystyle {\mathcal {H}}}$ est un couple ${\displaystyle (V,\,E)}$ où ${\displaystyle V}$ est un ensemble de sommets, et ${\displaystyle E}$ une famille de sous-ensembles de ${\displaystyle V}$ qu'on nomme arêtes, ou hyperarêtes.

Une transversale^{[réf. nécessaire]} de ${\displaystyle {\mathcal {H}}}$ est un ensemble ${\displaystyle T\subset V}$ tel que pour toute arête ${\displaystyle e}$ appartenant à ${\displaystyle E}$, ${\displaystyle T\cap e\neq \emptyset }$.

Le nombre de transversalité^{[réf. nécessaire]} d'un hypergraphe ${\displaystyle {\mathcal {H}}}$ est la taille d'une plus petite transversale de ${\displaystyle {\mathcal {H}}}$. Il est souvent noté ${\displaystyle \tau ({\mathcal {H}})}$

Par exemple, si ${\displaystyle {\mathcal {H}}}$ est l'hypergraphe défini par ${\displaystyle V\,=\,\{1,2,3,4,5,6\}}$ et ${\displaystyle E\,=\,\{\{1,2,3\},\{1,4,5\},\{2,3,6\},\{4,5,6\}\}}$, alors ${\displaystyle {\mathcal {H}}}$ admet plusieurs transversales de taille 2 (par exemple ${\displaystyle \{1,6\}}$ ou ${\displaystyle \{2,4\}}$) et aucune de taille 1 (car aucun sommet n'appartient à toutes les arêtes). Son nombre de transversalité vaut donc 2.

Un sommet d'une transversale est dit non-redondant s'il existe une arête de l'hypergraphe de départ dont l'intersection avec cette transversale est réduite au sommet considéré. Autrement dit, un sommet ${\displaystyle i}$ d'une transversale ${\displaystyle X}$ associée à un hypergraphe ${\displaystyle {\mathcal {H}}(V,E)}$ est non-redondant s'il vérifie : ${\displaystyle \exists e\in E,e\cap X=\{i\}}$

Intuitivement, la redondance d'un sommet ${\displaystyle i}$ équivaut à la transversalité de l'ensemble de sommets ${\displaystyle X\setminus \{i\}}$. En effet, si ${\displaystyle i}$ est redondant, alors pour toute hyperarête ${\displaystyle e}$ : si ${\displaystyle i\notin e\cap X}$ alors ${\displaystyle e\cap (X\setminus \{i\})=e\cap X\neq \emptyset }$, et si ${\displaystyle i\in e\cap X}$ alors il existe un élément ${\displaystyle j\neq i}$ tel que ${\displaystyle j\notin e\cap X}$ car ${\displaystyle i}$ est redondant. On a alors ${\displaystyle j\in e\cap (X\setminus \{i\})\neq \emptyset }$. Réciproquement, si ${\displaystyle X\setminus \{i\}}$ est une transversale, alors ${\displaystyle i}$ est forcément redondant car s'il existait ${\displaystyle e}$ tel que ${\displaystyle e\cap X=\{i\}}$, alors on aurait ${\displaystyle e\cap (X\setminus \{i\})=\emptyset }$ et ${\displaystyle X\setminus \{i\}}$ ne serait pas une transversale.

Une transversale ${\displaystyle X}$ est dite minimale (ou non-redondante^[1]) si aucun de ses sous-ensembles n'est également une transversale, ce qui est équivalent à dire qu'aucun de ses sommets n'est redondant. En effet : on a vu au paragraphe précédent que si l'un de ses sommets était redondant on disposerait d'un sous-ensemble transversal, et si l'on disposait d'un sous-ensemble ${\displaystyle X'}$ transversal on pourrait montrer que tout sommet de ${\displaystyle X\setminus X'}$ est redondant (la démonstration est très similaire à celle du paragraphe précédent).

L'ensemble des transversales minimales associées à un hypergraphe forme un hypergraphe appelé hypergraphe transverse.

Le calcul d'un hypergraphe transverse est faisable, à ce jour, en temps ${\displaystyle O(N^{o(\log N)})}$^[2], ${\displaystyle N}$ étant le cardinal de l'ensemble de sommets.

L'algorithme MTMiner^[3],[4] (pour Minimal Transversals Miner) permet de calculer les transversales minimales d'un hypergraphe donné.

   Entrée Un hypergraphe ${\displaystyle {\mathcal {H}}=(V,E)}$
   Sortie L'ensemble des transversales minimales de ${\displaystyle {\mathcal {H}}}$
   Fonction MTMiner(${\displaystyle {\mathcal {H}}}$)
      ${\displaystyle MT\leftarrow \{\{v\}\mid v\in V,\ \{v\}{\text{ est une arête transversale}}\}}$
      ${\displaystyle N_{1}\leftarrow \{\{v\}\mid v\in V\setminus MT,\ v{\text{ est dans une arête de }}E\}}$
      ${\displaystyle j\leftarrow 1}$
      tant que ${\displaystyle N_{j}\neq \emptyset }$ faire :
         pour tous ${\displaystyle P\subset V}$ et ${\displaystyle v_{1}\neq v_{2}\in V}$ tels que ${\displaystyle P\cup \{v_{1}\},P\cup \{v_{2}\}\in N_{j}}$ :
            ${\displaystyle W\leftarrow P\cup \{v_{1}\}\cup \{v_{2}\}}$
            si ${\displaystyle W}$ est non-redondant :
               si ${\displaystyle W}$ est transversal :
                  Ajouter ${\displaystyle W}$ à ${\displaystyle MT}$
               sinon :
                  Ajouter ${\displaystyle W}$ à ${\displaystyle N_{j+1}}$
         ${\displaystyle j\leftarrow j+1}$
      renvoyer ${\displaystyle MT}$

Soit ${\displaystyle {\mathcal {H}}}$ l'hypergraphe formé des sommets ${\displaystyle V=\{1,2,3,4,5\}}$, avec pour arêtes ${\displaystyle E=\{\{1,2,3\},\{1,4\},\{3,5\},\{4,5\}\}}$. L'exécution se déroule comme suit :

1. ${\displaystyle MT}$ est initialisé à ${\displaystyle \emptyset }$ ;
2. ${\displaystyle N_{1}}$ est initialisé à ${\displaystyle \{\{1\},\{2\},\{3\},\{4\},\{5\}\}}$ ;
3. ${\displaystyle W}$ prendra successivement pour valeurs ${\displaystyle \{1,2\},\{1,3\},\{1,4\},\{1,5\},\{2,3\},\{2,4\},\{2,5\},\{3,4\},\{3,5\}}$ et ${\displaystyle \{4,5\}}$ :
   1. ${\displaystyle \{1,5\}}$ et ${\displaystyle \{3,4\}}$ sont ajoutées à ${\displaystyle MT}$,
   2. ${\displaystyle \{1,3\},\{1,4\},\{2,4\},\{2,5\},\{3,5\}}$ et ${\displaystyle \{4,5\}}$ sont ajoutées à ${\displaystyle N_{2}}$,
   3. Les autres hyperarêtes sont redondantes ;
4. ${\displaystyle N_{2}}$ vaut ${\displaystyle \{\{1,3\},\{1,4\},\{2,4\},\{2,5\},\{3,5\},\{4,5\}\}}$ ;
5. ${\displaystyle W}$ prendra successivement pour valeurs ${\displaystyle \{1,3,4\},\{2,4,5\},\{1,3,5\},\{1,2,4\},\{1,4,5\}}$ et ${\displaystyle \{3,4,5\}}$ :
   1. ${\displaystyle \{2,4,5\}}$ est ajoutée à ${\displaystyle MT}$,
   2. Les autres hyperarêtes sont redondantes ;
6. ${\displaystyle N_{3}=\emptyset }$ ;
7. L'algorithme renvoie ${\displaystyle MT=\{\{1,5\},\{3,4\},\{2,4,5\}\}}$.

Les transversales minimales de ${\displaystyle {\mathcal {H}}}$ sont bien ${\displaystyle \{1,5\},\{3,4\}}$ et ${\displaystyle \{2,4,5\}}$.

• Portail des mathématiques