Bordo trasversale

Nella teoria dell'ipergrafo , una trasversa è una parte dei vertici che incontrano tutti i bordi di un ipergrafo . L'insieme delle trasversali è la [[Griglia (matematica) | griglia ]] . Questo è analogo al vertex cover ( vertex cover in inglese) nei grafici.

Definizioni

Si ricorda che un ipergrafo è una coppia dove è un insieme di vertici, e una famiglia di sottoinsiemi chiamati archi, o iper-archi. ${\ matematica {H}}$ ${\ stile di visualizzazione (V, \, E)}$ $V$ $E$ $V$

Un trasversale to è un numero tale che per ogni arco appartenente a , . ${\ matematica {H}}$ ${\ displaystyle T \ sottoinsieme V}$ $e$ $E$ ${\ displaystyle T \ cap e \ neq \ emptyset}$

Il numero della trasversalità di un ipergrafo è la dimensione della più piccola trasversa di . È spesso notato ${\ matematica {H}}$ ${\ matematica {H}}$ ${\ displaystyle \ tau ({\ mathcal {H}})}$

Esempio

Ad esempio, se l'ipergrafo è definito da e , allora ammette più trasversali di dimensione 2 (ad esempio o ) e nessuna di dimensione 1 (perché nessun vertice appartiene a tutti gli spigoli). Il suo numero di trasversalità vale quindi 2. ${\ matematica {H}}$ ${\ stile di visualizzazione V \, = \, \ {1,2,3,4,5,6 \}}$ ${\ displaystyle E \, = \, \ {\ {1,2,3 \}, \ {1,4,5 \}, \ {2,3,6 \}, \ {4,5,6 \} \}}$ ${\ matematica {H}}$ ${\ stile di visualizzazione \ {1,6 \}}$ ${\ stile di visualizzazione \ {2,4 \}}$

Vertici ridondanti di una trasversa

Un vertice di una trasversa si dice non ridondante se esiste un bordo dell'ipergrafo di partenza la cui intersezione con questa trasversa è ridotta al vertice considerato. In altre parole, un vertice di un traverso associato a un ipergrafo è non ridondante se soddisfa: $io$ $X$ ${\ displaystyle {\ mathcal {H}} (V, E)}$ ${\ displaystyle \ esiste e \ in E, e \ cap X = \ {i \}}$

Intuitivamente, la ridondanza di un vertice equivale alla trasversalità dell'insieme dei vertici . Infatti, se è ridondante, allora per qualsiasi iper-edge : se allora , e se poi esiste un elemento tale che auto è ridondante. Abbiamo allora . Viceversa, se è una trasversa, allora è necessariamente ridondante perché se esistesse in modo tale che , allora avremmo e non saremmo una trasversa. $io$ ${\ displaystyle X \ setminus \ {i \}}$ $io$ $e$ ${\ displaystyle i \ notin e \ cap X}$ ${\ displaystyle e \ cap (X \ setminus \ {i \}) = e \ cap X \ neq \ emptyset}$ ${\ displaystyle i \ in e \ cap X}$ $j \ neq io$ ${\ displaystyle j \ notin e \ cap X}$ $io$ ${\ displaystyle j \ in e \ cap (X \ setminus \ {i \}) \ neq \ emptyset}$ ${\ displaystyle X \ setminus \ {i \}}$ $io$ $e$ ${\ displaystyle e \ cap X = \ {i \}}$ ${\ displaystyle e \ cap (X \ setminus \ {i \}) = \ emptyset}$ ${\ displaystyle X \ setminus \ {i \}}$

Una trasversa si dice minima (o non ridondante) se nessuno dei suoi sottoinsiemi è anche trasversa, il che equivale a dire che nessuno dei suoi vertici è ridondante. Infatti: abbiamo visto nel paragrafo precedente che se uno dei suoi vertici fosse ridondante avremmo un sottoinsieme trasversale, e se avessimo un sottoinsieme trasversale potremmo dimostrare che qualsiasi vertice di è ridondante (la dimostrazione è molto simile a quella del paragrafo precedente). $X$ $X '$ ${\ displaystyle X \ setmeno X '}$

Ipergrafo trasversale

L'insieme delle trasversali minime associate a un ipergrafo forma un ipergrafo chiamato ipergrafo trasversale .

Il calcolo di un ipergrafo trasversale è fattibile, ad oggi, nel tempo , essendo il cardinale dell'insieme dei vertici. ${\ displaystyle O (N ^ {o (\ log N)})}$ $NON$

Algoritmo

Pseudo-codice

L'algoritmo MTMiner (per Minimal Transversals Miner ) permette di calcolare le minime trasversali di un dato ipergrafo.

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

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}\}

W

est non-redondant : si

W

est transversal : Ajouter

W

MT

sinon : Ajouter

W

N_{j+1}

j\leftarrow j+1

renvoyer

MT

Esempio di esecuzione

Lascia che l'ipergrafo sia formato da vertici , con spigoli . L'esecuzione procede come segue: ${\ matematica {H}}$ ${\ stile di visualizzazione V = \ {1,2,3,4,5 \}}$ ${\ displaystyle E = \ {\ {1,2,3 \}, \ {1,4 \}, \ {3,5 \}, \ {4,5 \} \}}$

$MT$ è inizializzato a ; $\ set vuoto$
$N_ {1}$ è inizializzato a ; ${\ displaystyle \ {\ {1 \}, \ {2 \}, \ {3 \}, \ {4 \}, \ {5 \} \}}$
W{\ stile di visualizzazione W} $W$ assumerà successivamente come valori e : {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 \}} ${\ displaystyle \ {1,2 \}, \ {1,3 \}, \ {1,4 \}, \ {1,5 \}, \ {2,3 \}, \ {2,4 \} , \ {2,5 \}, \ {3,4 \}, \ {3,5 \}}$ {4,5}{\ stile di visualizzazione \ {4,5 \}} ${\ stile di visualizzazione \ {4,5 \}}$
1. ${\ stile di visualizzazione \ {1.5 \}}$ e si aggiungono a , ${\ stile di visualizzazione \ {3,4 \}}$ $MT$
2. ${\ displaystyle \ {1.3 \}, \ {1.4 \}, \ {2.4 \}, \ {2.5 \}, \ {3.5 \}}$ e si aggiungono a , ${\ stile di visualizzazione \ {4,5 \}}$ $N_ {2}$
3. Gli altri hyper-edge sono ridondanti;
$N_ {2}$ vale ; ${\ displaystyle \ {\ {1.3 \}, \ {1.4 \}, \ {2.4 \}, \ {2.5 \}, \ {3.5 \}, \ {4.5 \} \}}$
W{\ stile di visualizzazione W} $W$ assumerà successivamente come valori e : {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 \}} ${\ displaystyle \ {1,3,4 \}, \ {2,4,5 \}, \ {1,3,5 \}, \ {1,2,4 \}, \ {1,4,5 \}}$ {3,4,5}{\ stile di visualizzazione \ {3,4,5 \}} ${\ stile di visualizzazione \ {3,4,5 \}}$
1. ${\ stile di visualizzazione \ {2,4,5 \}}$ si aggiunge a , $MT$
2. Gli altri hyper-edge sono ridondanti;
${\ displaystyle N_ {3} = \ set vuoto}$ ;
L'algoritmo restituisce . ${\ displaystyle MT = \ {\ {1,5 \}, \ {3,4 \}, \ {2,4,5 \} \}}$

Le minime trasversali di sono bene e . ${\ matematica {H}}$ ${\ stile di visualizzazione \ {1.5 \}, \ {3.4 \}}$ ${\ stile di visualizzazione \ {2,4,5 \}}$

Note e riferimenti

Loïck. Lhote , Esempi di analisi algoritmica in aritmetica, teoria dell'informazione e data mining ,19 gennaio 2017, 75 pag. ( leggi in linea )
(in) Michael L. Fredman e Leonid Khachiyan , " Sulla complessità della dualizzazione monotona delle forme normali disgiuntive " , Journal of Algorithms , vol. 21, n . 3,1 ° novembre 1996, pag. 618-628 ( ISSN 0196-6774 , DOI 10.1006 / jagm.1996.0062 , lettura online , accesso 25 agosto 2020 )
(in) Céline Hébert Alain Bretto e Bruno Crémilleux , " Una formalizzazione del data mining per migliorare il calcolo minimo dell'ipergrafo trasversale " , Fundamenta Informaticae ,dicembre 2007, pag. 415-433
(in) Julien David , Loïck Lhote , Arnaud Mary e Francois Rioult , " Uno studio medio di ipergrafi e minimali loro trasversali " , Informatica teorica ,2015( DOI 10.1016 / j.tcs.2015.06.052 )