Arête transversale

En théorie des hypergraphes, une transversale est une partie des sommets qui rencontre toutes les arêtes d'un hypergraphe. L'ensemble des transversales est la [[Grille (mathématiques)|grille^{[réf. nécessaire]}]]^[Quoi ?]. C'est l'analogue du problème de couverture par sommets (vertex cover en anglais) chez les graphes.

Définitions

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

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

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

Exemple

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

Sommets redondants d'une transversale

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 $i$ d'une transversale $X$ associée à un hypergraphe ${\mathcal {H}}(V,E)$ est non-redondant s'il vérifie : $\exists e\in E,e\cap X=\{i\}$

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

Une transversale $X$ est dite minimale (ou non-redondante) 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 $X'$ transversal on pourrait montrer que tout sommet de $X\setminus X'$ est redondant (la démonstration est très similaire à celle du paragraphe précédent).

Hypergraphe transverse

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 $O(N^{o(\log N)})$, $N$ étant le cardinal de l'ensemble de sommets.

Algorithme

Pseudo-code

L'algorithme MTMiner (pour Minimal Transversals Miner) permet de calculer les transversales minimales d'un hypergraphe donné.

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

Exemple d'exécution

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

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

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