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)|grilleModèle:Référence nécessaire]]Modèle: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 $\mathscr{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 transversaleModèle:Référence nécessaire de $\mathscr{H}$ est un ensemble $T\subset V$ tel que pour toute arête $e$ appartenant à $E$, $T\cap e\ne \mathrm{\varnothing }$.

Le nombre de transversalitéModèle:Référence nécessaire d'un hypergraphe $\mathscr{H}$ est la taille d'une plus petite transversale de $\mathscr{H}$. Il est souvent noté $\tau (\mathscr{H})$

Exemple

Par exemple, si $\mathscr{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 $\mathscr{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 $\mathscr{H}(V,E)$ est non-redondant s'il vérifie : $\mathrm{\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\ne \mathrm{\varnothing }$, et si $i\in e\cap X$ alors il existe un élément $j\ne i$ tel que $j\notin e\cap X$ car $i$ est redondant. On a alors $j\in e\cap (X\setminus \{i\})\ne \mathrm{\varnothing }$. 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\})=\mathrm{\varnothing }$ 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^{\prime }$ transversal on pourrait montrer que tout sommet de $X\setminus X^{\prime }$ 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 MTMinerModèle:, (pour Minimal Transversals Miner) permet de calculer les transversales minimales d'un hypergraphe donné.

   Entrée Un hypergraphe $\mathscr{H}=(V,E)$
   Sortie L'ensemble des transversales minimales de $\mathscr{H}$
   Fonction MTMiner($\mathscr{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\ne \mathrm{\varnothing }$ faire :
         pour tous $P\subset V$ et $v_1\ne 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 $\mathscr{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é à $\mathrm{\varnothing }$ ;
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=\mathrm{\varnothing }$ ;
7. L'algorithme renvoie $MT=\{\{1,5\},\{3,4\},\{2,4,5\}\}$.

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