Arête transversale
# 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]]. 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 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é 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é.

**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 :

* $MT$ est initialisé à $\emptyset$ ;
* $N_{1}$ est initialisé à $\{\{1\},\{2\},\{3\},\{4\},\{5\}\}$ ;
* $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,5\}$ et $\{3,4\}$ sont ajoutées à $MT$,
   * $\{1,3\},\{1,4\},\{2,4\},\{2,5\},\{3,5\}$ et $\{4,5\}$ sont ajoutées à $N_{2}$,
   * Les autres hyperarêtes sont redondantes ;
* $N_{2}$ vaut $\{\{1,3\},\{1,4\},\{2,4\},\{2,5\},\{3,5\},\{4,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\}$ :
   * $\{2,4,5\}$ est ajoutée à $MT$,
   * Les autres hyperarêtes sont redondantes ;
* $N_{3}=\emptyset$ ;
* 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\}$.

