ArĂȘte transversale
DĂ©finitions On rappelle qu'un hypergraphe
H
{\displaystyle {\mathcal {H}}}
(
V
,
E
)
{\displaystyle (V,\,E)}
V
{\displaystyle V}
E
{\displaystyle E}
V
{\displaystyle V}
Une transversale de
H
{\displaystyle {\mathcal {H}}}
T
â
V
{\displaystyle T\subset V}
e
{\displaystyle e}
E
{\displaystyle E}
T
â©
e
â
â
{\displaystyle T\cap e\neq \emptyset }
Le nombre de transversalité d'un hypergraphe
H
{\displaystyle {\mathcal {H}}}
H
{\displaystyle {\mathcal {H}}}
Ï
(
H
)
{\displaystyle \tau ({\mathcal {H}})}
Exemple Par exemple, si
H
{\displaystyle {\mathcal {H}}}
V
=
{
1
,
2
,
3
,
4
,
5
,
6
}
{\displaystyle V\,=\,\{1,2,3,4,5,6\}}
E
=
{
{
1
,
2
,
3
}
,
{
1
,
4
,
5
}
,
{
2
,
3
,
6
}
,
{
4
,
5
,
6
}
}
{\displaystyle E\,=\,\{\{1,2,3\},\{1,4,5\},\{2,3,6\},\{4,5,6\}\}}
H
{\displaystyle {\mathcal {H}}}
{
1
,
6
}
{\displaystyle \{1,6\}}
{
2
,
4
}
{\displaystyle \{2,4\}}
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
{\displaystyle i}
X
{\displaystyle X}
H
(
V
,
E
)
{\displaystyle {\mathcal {H}}(V,E)}
â
e
â
E
,
e
â©
X
=
{
i
}
{\displaystyle \exists e\in E,e\cap X=\{i\}}
Intuitivement, la redondance d'un sommet
i
{\displaystyle i}
X
â
{
i
}
{\displaystyle X\setminus \{i\}}
i
{\displaystyle i}
e
{\displaystyle e}
i
â
e
â©
X
{\displaystyle i\notin e\cap X}
e
â©
(
X
â
{
i
}
)
=
e
â©
X
â
â
{\displaystyle e\cap (X\setminus \{i\})=e\cap X\neq \emptyset }
i
â
e
â©
X
{\displaystyle i\in e\cap X}
j
â
i
{\displaystyle j\neq i}
j
â
e
â©
X
{\displaystyle j\notin e\cap X}
i
{\displaystyle i}
j
â
e
â©
(
X
â
{
i
}
)
â
â
{\displaystyle j\in e\cap (X\setminus \{i\})\neq \emptyset }
X
â
{
i
}
{\displaystyle X\setminus \{i\}}
i
{\displaystyle i}
e
{\displaystyle e}
e
â©
X
=
{
i
}
{\displaystyle e\cap X=\{i\}}
e
â©
(
X
â
{
i
}
)
=
â
{\displaystyle e\cap (X\setminus \{i\})=\emptyset }
X
â
{
i
}
{\displaystyle X\setminus \{i\}}
Une transversale
X
{\displaystyle X}
minimale (ou non-redondante[1] 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
âČ
{\displaystyle X'}
X
â
X
âČ
{\displaystyle X\setminus X'}
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
)
)
{\displaystyle O(N^{o(\log N)})}
[2]
N
{\displaystyle N}
Pseudo-code L'algorithme MTMiner[3] [4] Minimal Transversals Miner ) permet de calculer les transversales minimales d'un hypergraphe donné.
Entrée Un hypergraphe
H
=
(
V
,
E
)
{\displaystyle {\mathcal {H}}=(V,E)}
Sortie L'ensemble des transversales minimales de
H
{\displaystyle {\mathcal {H}}}
Fonction MTMiner(
H
{\displaystyle {\mathcal {H}}}
M
T
â
{
{
v
}
âŁ
v
â
V
,
{
v
}
est une arĂȘte transversale
}
{\displaystyle MT\leftarrow \{\{v\}\mid v\in V,\ \{v\}{\text{ est une arĂȘte transversale}}\}}
N
1
â
{
{
v
}
âŁ
v
â
V
â
M
T
,
v
est dans une arĂȘte de
E
}
{\displaystyle N_{1}\leftarrow \{\{v\}\mid v\in V\setminus MT,\ v{\text{ est dans une arĂȘte de }}E\}}
j
â
1
{\displaystyle j\leftarrow 1}
tant que
N
j
â
â
{\displaystyle N_{j}\neq \emptyset }
faire :
pour tous
P
â
V
{\displaystyle P\subset V}
v
1
â
v
2
â
V
{\displaystyle v_{1}\neq v_{2}\in V}
P
âȘ
{
v
1
}
,
P
âȘ
{
v
2
}
â
N
j
{\displaystyle P\cup \{v_{1}\},P\cup \{v_{2}\}\in N_{j}}
W
â
P
âȘ
{
v
1
}
âȘ
{
v
2
}
{\displaystyle W\leftarrow P\cup \{v_{1}\}\cup \{v_{2}\}}
si
W
{\displaystyle W}
si
W
{\displaystyle W}
W
{\displaystyle W}
M
T
{\displaystyle MT}
sinon :
Ajouter
W
{\displaystyle W}
N
j
+
1
{\displaystyle N_{j+1}}
j
â
j
+
1
{\displaystyle j\leftarrow j+1}
renvoyer
M
T
{\displaystyle MT}
Exemple d'exécution Soit
H
{\displaystyle {\mathcal {H}}}
V
=
{
1
,
2
,
3
,
4
,
5
}
{\displaystyle V=\{1,2,3,4,5\}}
E
=
{
{
1
,
2
,
3
}
,
{
1
,
4
}
,
{
3
,
5
}
,
{
4
,
5
}
}
{\displaystyle E=\{\{1,2,3\},\{1,4\},\{3,5\},\{4,5\}\}}
M
T
{\displaystyle MT}
â
{\displaystyle \emptyset }
N
1
{\displaystyle N_{1}}
{
{
1
}
,
{
2
}
,
{
3
}
,
{
4
}
,
{
5
}
}
{\displaystyle \{\{1\},\{2\},\{3\},\{4\},\{5\}\}}
W
{\displaystyle W}
{
1
,
2
}
,
{
1
,
3
}
,
{
1
,
4
}
,
{
1
,
5
}
,
{
2
,
3
}
,
{
2
,
4
}
,
{
2
,
5
}
,
{
3
,
4
}
,
{
3
,
5
}
{\displaystyle \{1,2\},\{1,3\},\{1,4\},\{1,5\},\{2,3\},\{2,4\},\{2,5\},\{3,4\},\{3,5\}}
{
4
,
5
}
{\displaystyle \{4,5\}}
{
1
,
5
}
{\displaystyle \{1,5\}}
{
3
,
4
}
{\displaystyle \{3,4\}}
M
T
{\displaystyle MT}
{
1
,
3
}
,
{
1
,
4
}
,
{
2
,
4
}
,
{
2
,
5
}
,
{
3
,
5
}
{\displaystyle \{1,3\},\{1,4\},\{2,4\},\{2,5\},\{3,5\}}
{
4
,
5
}
{\displaystyle \{4,5\}}
N
2
{\displaystyle N_{2}}
Les autres hyperarĂȘtes sont redondantes ;
N
2
{\displaystyle N_{2}}
{
{
1
,
3
}
,
{
1
,
4
}
,
{
2
,
4
}
,
{
2
,
5
}
,
{
3
,
5
}
,
{
4
,
5
}
}
{\displaystyle \{\{1,3\},\{1,4\},\{2,4\},\{2,5\},\{3,5\},\{4,5\}\}}
W
{\displaystyle W}
{
1
,
3
,
4
}
,
{
2
,
4
,
5
}
,
{
1
,
3
,
5
}
,
{
1
,
2
,
4
}
,
{
1
,
4
,
5
}
{\displaystyle \{1,3,4\},\{2,4,5\},\{1,3,5\},\{1,2,4\},\{1,4,5\}}
{
3
,
4
,
5
}
{\displaystyle \{3,4,5\}}
{
2
,
4
,
5
}
{\displaystyle \{2,4,5\}}
M
T
{\displaystyle MT}
Les autres hyperarĂȘtes sont redondantes ;
N
3
=
â
{\displaystyle N_{3}=\emptyset }
L'algorithme renvoie
M
T
=
{
{
1
,
5
}
,
{
3
,
4
}
,
{
2
,
4
,
5
}
}
{\displaystyle MT=\{\{1,5\},\{3,4\},\{2,4,5\}\}}
Les transversales minimales de
H
{\displaystyle {\mathcal {H}}}
{
1
,
5
}
,
{
3
,
4
}
{\displaystyle \{1,5\},\{3,4\}}
{
2
,
4
,
5
}
{\displaystyle \{2,4,5\}}
Notes et rĂ©fĂ©rences LoĂŻck. Lhote , Exemples dâanalyses dâalgorithmes en ArithmĂ©tique, ThĂ©orie de lâInformation et Fouille de DonnĂ©es , 19 janvier 2017 , 75 p. (lire en ligne ) (en) Michael L. Fredman et Leonid Khachiyan , « On the Complexity of Dualization of Monotone Disjunctive Normal Forms » , Journal of Algorithms vol. 21, no 3,â 1er novembre 1996p. 618â628 (ISSN 0196-6774 DOI 10.1006/jagm.1996.0062 lire en ligne , consultĂ© le 25 aoĂ»t 2020 ) (en) CĂ©line HĂ©bert , Alain Bretto et Bruno CrĂ©milleux , « A data mining formalization to improve hypergraph minimal transversal computation » , Fundamenta Informaticae â dĂ©cembre 2007 , p. 415-433 (en) Julien David , LoĂŻck Lhote , Arnaud Mary et François Rioult , « An average study of hypergraphs and their minimal transversals » , Theoretical Computer Science â 2015 (DOI 10.1016/j.tcs.2015.06.052
Cet article est issu de
wikipedia . Text licence:
CC BY-SA 4.0 , Des conditions supplĂ©mentaires peuvent sâappliquer aux fichiers multimĂ©dias.
