Borda transversal

Na teoria do hipergrafo , um transversal é uma parte dos vértices que encontra todas as arestas de um hipergrafo . O conjunto de transversais é a [[Grade (matemática) | grade ]] . Isso é análogo à cobertura do vértice ( cobertura do vértice em inglês) nos gráficos.

Definições

Recorde-se que um hipergrafo é um par onde está um conjunto de vértices e uma família de subconjuntos chamados arestas, ou hiper arestas. ${\ mathcal {H}}$ ${\ displaystyle (V, \, E)}$ $V$ $E$ $V$

Uma transversal a é um número tal que, para cada aresta que pertence a , . ${\ mathcal {H}}$ ${\ displaystyle T \ subset V}$ $e$ $E$ ${\ displaystyle T \ cap e \ neq \ emptyset}$

O número de transversalidade de um hipergrafo é do tamanho de um menor transversal de . É freqüentemente notado ${\ mathcal {H}}$ ${\ mathcal {H}}$ ${\ displaystyle \ tau ({\ mathcal {H}})}$

Exemplo

Por exemplo, se o hipergrafo é definido por e , então admite vários transversais de tamanho 2 (por exemplo ou ) e nenhum de tamanho 1 (porque nenhum vértice pertence a todas as arestas). Seu número de transversalidade vale, portanto, 2. ${\ mathcal {H}}$ ${\ displaystyle V \, = \, \ {1,2,3,4,5,6 \}}$ ${\ displaystyle E \, = \, \ {\ {1,2,3 \}, \ {1,4,5 \}, \ {2,3,6 \}, \ {4,5,6 \} \}}$ ${\ mathcal {H}}$ ${\ displaystyle \ {1,6 \}}$ ${\ displaystyle \ {2,4 \}}$

Vértices redundantes de uma transversal

Um vértice de uma transversal é considerado não redundante se houver uma aresta do hipergrafo inicial cuja intersecção com esta transversal seja reduzida ao vértice considerado. Em outras palavras, um vértice de uma transversal associada a um hipergrafo não é redundante se satisfizer: $eu$ $X$ ${\ displaystyle {\ mathcal {H}} (V, E)}$ ${\ displaystyle \ existe e \ in E, e \ cap X = \ {i \}}$

Intuitivamente, a redundância de um vértice equivale à transversalidade do conjunto de vértices . Na verdade, se é redundante, então para qualquer hiper-borda : se então , e se então existe um elemento tal que o carro é redundante. Temos então . Por outro lado, se é uma transversal, então é necessariamente redundante porque se existisse tal que , então teríamos e não seria uma transversal. $eu$ ${\ displaystyle X \ setminus \ {i \}}$ $eu$ $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 i$ ${\ displaystyle j \ notin e \ cap X}$ $eu$ ${\ displaystyle j \ in e \ cap (X \ setminus \ {i \}) \ neq \ emptyset}$ ${\ displaystyle X \ setminus \ {i \}}$ $eu$ $e$ ${\ displaystyle e \ cap X = \ {i \}}$ ${\ displaystyle e \ cap (X \ setminus \ {i \}) = \ emptyset}$ ${\ displaystyle X \ setminus \ {i \}}$

Uma transversal é considerada mínima (ou não redundante) se nenhum de seus subconjuntos também for transversal, o que equivale a dizer que nenhum de seus vértices é redundante. De fato: vimos no parágrafo anterior que se um de seus vértices fosse redundante, teríamos um subconjunto transversal, e se tivéssemos um subconjunto transversal, poderíamos mostrar que qualquer vértice de é redundante (a demonstração é muito semelhante à do parágrafo anterior). $X$ $X '$ ${\ displaystyle X \ setminus X '}$

Hipergrafo transversal

O conjunto de transversais mínimos associados a um hipergrafo forma um hipergrafo denominado hipergrafo transversal .

O cálculo de um hipergrafo transversal é viável, até hoje, no tempo , sendo o cardinal do conjunto de vértices. ${\ displaystyle O (N ^ {o (\ log N)})}$ $NÃO$

Algoritmo

Pseudo-código

O algoritmo MTMiner (para Minimal Transversals Miner ) permite calcular os transversais mínimos de um dado hipergrafo.

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

Exemplo de execução

Seja o hipergrafo formado por vértices , com arestas . A execução prossegue da seguinte forma: ${\ mathcal {H}}$ ${\ displaystyle V = \ {1,2,3,4,5 \}}$ ${\ displaystyle E = \ {\ {1,2,3 \}, \ {1,4 \}, \ {3,5 \}, \ {4,5 \} \}}$

$MT$ é inicializado com ; $\ emptyset$
$N_ {1}$ é inicializado com ; ${\ displaystyle \ {\ {1 \}, \ {2 \}, \ {3 \}, \ {4 \}, \ {5 \} \}}$
C{\ displaystyle W} $C$ tomará sucessivamente como valores 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}{\ displaystyle \ {4,5 \}} ${\ displaystyle \ {4,5 \}}$
1. ${\ displaystyle \ {1.5 \}}$ e são adicionados a , ${\ displaystyle \ {3,4 \}}$ $MT$
2. ${\ displaystyle \ {1.3 \}, \ {1.4 \}, \ {2.4 \}, \ {2.5 \}, \ {3.5 \}}$ e são adicionados a , ${\ displaystyle \ {4,5 \}}$ $N_ {2}$
3. As outras hiper-arestas são redundantes;
$N_ {2}$ vale a pena ; ${\ displaystyle \ {\ {1,3 \}, \ {1,4 \}, \ {2,4 \}, \ {2,5 \}, \ {3,5 \}, \ {4,5 \} \}}$
C{\ displaystyle W} $C$ tomará sucessivamente como valores 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}{\ displaystyle \ {3,4,5 \}} ${\ displaystyle \ {3,4,5 \}}$
1. ${\ displaystyle \ {2,4,5 \}}$ é adicionado a , $MT$
2. As outras hiper-arestas são redundantes;
${\ displaystyle N_ {3} = \ emptyset}$ ;
O algoritmo retorna . ${\ displaystyle MT = \ {\ {1,5 \}, \ {3,4 \}, \ {2,4,5 \} \}}$

Os transversais mínimos de são bem e . ${\ mathcal {H}}$ ${\ displaystyle \ {1.5 \}, \ {3.4 \}}$ ${\ displaystyle \ {2,4,5 \}}$

Notas e referências

Loïck. Lhote , Exemplos de análise de algoritmos em Aritmética, Teoria da Informação e Mineração de Dados ,19 de janeiro de 2017, 75 p. ( leia online )
(em) Michael L. Fredman e Leonid Khachiyan , " On the Complexity of Monotone Dualization of disjunctive Normal Forms " , Journal of Algorithms , vol. 21, n o 3,1 r nov 1996, p. 618-628 ( ISSN 0196-6774 , DOI 10.1006 / jagm.1996.0062 , ler online , acessado em 25 de agosto de 2020 )
(in) Céline Hébert Alain Bretto e Bruno Crémilleux , " Uma formalização de mineração de dados para melhorar a computação mínima do hipergrafo transversal " , Fundamenta Informaticae ,dezembro de 2007, p. 415-433
(in) Julien David , Loïck Lhote , Arnaud Mary e Francois Rioult , " Um estudo médio de hipergrafos e mínimo seu transversal " , Ciência da computação teórica ,2015( DOI 10.1016 / j.tcs.2015.06.052 )