Příčná hrana
V teorii hypergrafu je příčná část vrcholů, která splňuje všechny okraje hypergrafu . Sada příčných prvků je [[Mřížka (matematika) | mřížka ]] . To je obdoba vrcholového krytu ( angl. Vertex cover ) v grafech.
Definice
Je třeba připomenout, že hypergraf je pár, kde je sada vrcholů a rodina podmnožin zvaných hrany nebo hyperhrany.
H{\ displaystyle {\ mathcal {H}}}
(PROTI,E){\ displaystyle (V, \, E)}
PROTI{\ displaystyle V}
E{\ displaystyle E}
PROTI{\ displaystyle V}![PROTI](https://wikimedia.org/api/rest_v1/media/math/render/svg/af0f6064540e84211d0ffe4dac72098adfa52845)
Příčný k je číslo takové, že pro každou hranu patřící do , .
H{\ displaystyle {\ mathcal {H}}}
T⊂PROTI{\ displaystyle T \ podmnožina V}
E{\ displaystyle e}
E{\ displaystyle E}
T∩E≠∅{\ displaystyle T \ cap e \ neq \ emptyset}![{\ displaystyle T \ cap e \ neq \ emptyset}](https://wikimedia.org/api/rest_v1/media/math/render/svg/adb9a0c023dd084b99858d3b2b6ecffe6c08fcc7)
Počet transversality hypergrafu je velikost nejmenšího příčného z . Často se to zaznamenáváH{\ displaystyle {\ mathcal {H}}}
H{\ displaystyle {\ mathcal {H}}}
τ(H){\ displaystyle \ tau ({\ mathcal {H}})}
Příklad
Například pokud je hypergraf definován a , pak připouští několik příčných řezů o velikosti 2 (například nebo ) a žádném z velikosti 1 (protože žádný vrchol nepatří ke všem hranám). Jeho počet transverzality má tedy hodnotu 2.
H{\ displaystyle {\ mathcal {H}}}
PROTI={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 \}}![{\ displaystyle \ {2,4 \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/303ee7b3881b20e9b99f732866ee8b061e43aeff)
Redundantní vrcholy příčné
Vrchol příčné se říká, že není redundantní, pokud existuje hrana výchozího hypergrafu, jehož průsečík s touto příčnou je redukován na uvažovaný vrchol. Jinými slovy, vrchol příčné spojené s hypergrafem je neredundantní, pokud splňuje:i{\ displaystyle i}
X{\ displaystyle X}
H(PROTI,E){\ displaystyle {\ mathcal {H}} (V, E)}
∃E∈E,E∩X={i}{\ displaystyle \ existuje e \ v E, e \ cap X = \ {i \}}
Intuitivně je redundance vrcholu ekvivalentní transverzálnosti množiny vrcholů . Ve skutečnosti, pokud je nadbytečné, pak pro jakýkoli hyper-okraj : pokud pak , a pokud pak existuje prvek takový, že auto je nadbytečné. Máme tedy . Naopak, pokud je příčná, pak je nutně nadbytečná, protože pokud by existovala taková , pak bychom měli a nebyli bychom příčnou.
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 \}) = \ prázdná sada}
X∖{i}{\ displaystyle X \ setminus \ {i \}}![{\ displaystyle X \ setminus \ {i \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6b324a467e1a5062b61fe6ac12419c486a77a23)
O příčném se říká, že je minimální (nebo neredundantní), pokud žádná z jejích podmnožin není také příčná, což odpovídá tomu, že žádný z jejích vrcholů není nadbytečný. Ve skutečnosti: v předchozím odstavci jsme viděli, že pokud by jeden z jeho vrcholů byl nadbytečný, měli bychom příčnou podmnožinu, a kdybychom měli příčnou podmnožinu, mohli bychom ukázat, že jakýkoli vrchol je nadbytečný (ukázka je velmi podobná té v předchozí odstavec).
X{\ displaystyle X}
X′{\ displaystyle X '}
X∖X′{\ displaystyle X \ setminus X '}![{\ displaystyle X \ setminus X '}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8286cb07518d1233957ed1d2e389eaa03722e381)
Příčný hypergraf
Sada minimálních příčných členů spojených s hypergrafem tvoří hypergraf nazývaný příčný hypergraf .
Výpočet příčné hypergrafie je proveditelný, k dnešnímu dni v čase , kdy je kardinálem množiny vrcholů.
Ó(NEÓ(logNE)){\ displaystyle O (N ^ {o (\ log N)})}
NE{\ displaystyle N}![NE](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
Algoritmus
Pseudo kód
Algoritmus MTMiner (pro Minimal Transversals Miner ) umožňuje vypočítat minimální příčné převody daného hypergrafu.
Entrée Un hypergraphe
H=(V,E){\displaystyle {\mathcal {H}}=(V,E)}![{\displaystyle {\mathcal {H}}=(V,E)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04285e60db0adeb0c382ddf8e53bbb5ee2a61591)
Sortie L'ensemble des transversales minimales de
H{\displaystyle {\mathcal {H}}}![{\mathcal {H}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19ef4c7b923a5125ac91aa491838a95ee15b804f)
Fonction MTMiner(
H{\displaystyle {\mathcal {H}}}![{\mathcal {H}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19ef4c7b923a5125ac91aa491838a95ee15b804f)
)
MT←{{v}∣v∈V, {v} est une arête transversale}{\displaystyle MT\leftarrow \{\{v\}\mid v\in V,\ \{v\}{\text{ est une arête transversale}}\}}
N1←{{v}∣v∈V∖MT, 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}![{\displaystyle j\leftarrow 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a201d50e7afb971fd2b4bbcca67ec7e84238a446)
tant que
Nj≠∅{\displaystyle N_{j}\neq \emptyset }![{\displaystyle N_{j}\neq \emptyset }](https://wikimedia.org/api/rest_v1/media/math/render/svg/82e83c48784d7549f2254c3c9b60517e3b436758)
faire :
pour tous
P⊂V{\displaystyle P\subset V}![{\displaystyle P\subset V}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ac56b4033cb76a97ff76d0ff6062f5e25bb6afc)
et
v1≠v2∈V{\displaystyle v_{1}\neq v_{2}\in V}![{\displaystyle v_{1}\neq v_{2}\in V}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b2e6c9b9a378f61c93ecd863e9a9a286aa9b9c5d)
tels que
P∪{v1},P∪{v2}∈Nj{\displaystyle P\cup \{v_{1}\},P\cup \{v_{2}\}\in N_{j}}![{\displaystyle P\cup \{v_{1}\},P\cup \{v_{2}\}\in N_{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/759fd67e247713fd3a028f1f2c527edfeb2ae742)
:
W←P∪{v1}∪{v2}{\displaystyle W\leftarrow P\cup \{v_{1}\}\cup \{v_{2}\}}![{\displaystyle W\leftarrow P\cup \{v_{1}\}\cup \{v_{2}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/976769cfb367bf478e85359bb75b225251a2d438)
si
W{\displaystyle W}![W](https://wikimedia.org/api/rest_v1/media/math/render/svg/54a9c4c547f4d6111f81946cad242b18298d70b7)
est non-redondant :
si
W{\displaystyle W}![W](https://wikimedia.org/api/rest_v1/media/math/render/svg/54a9c4c547f4d6111f81946cad242b18298d70b7)
est transversal :
Ajouter
W{\displaystyle W}![W](https://wikimedia.org/api/rest_v1/media/math/render/svg/54a9c4c547f4d6111f81946cad242b18298d70b7)
à
MT{\displaystyle MT}![MT](https://wikimedia.org/api/rest_v1/media/math/render/svg/98a909994972c27e3d072742881c62dcfb3aeeae)
sinon :
Ajouter
W{\displaystyle W}![W](https://wikimedia.org/api/rest_v1/media/math/render/svg/54a9c4c547f4d6111f81946cad242b18298d70b7)
à
Nj+1{\displaystyle N_{j+1}}
j←j+1{\displaystyle j\leftarrow j+1}![{\displaystyle j\leftarrow j+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5a5e3291b445ad105c3e4d7c5c58057196074c7)
renvoyer
MT{\displaystyle MT}
Příklad provedení
Nechte hypergraf tvořený vrcholy s hranami . Provádění probíhá následovně:
H{\ displaystyle {\ mathcal {H}}}
PROTI={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 \} \}}![{\ displaystyle E = \ {\ {1,2,3 \}, \ {1,4 \}, \ {3,5 \}, \ {4,5 \} \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bafdc34276314796d1f955c86512ab37069ff567)
-
MT{\ displaystyle MT}
je inicializováno na ;∅{\ displaystyle \ emptyset}![\ prázdná sada](https://wikimedia.org/api/rest_v1/media/math/render/svg/6af50205f42bb2ec3c666b7b847d2c7f96e464c7)
-
NE1{\ displaystyle N_ {1}}
je inicializováno na ;{{1},{2},{3},{4},{5}}{\ displaystyle \ {\ {1 \}, \ {2 \}, \ {3 \}, \ {4 \}, \ {5 \} \}}![{\ displaystyle \ {\ {1 \}, \ {2 \}, \ {3 \}, \ {4 \}, \ {5 \} \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1f077fe88640011e9a4150aceea968286f72acf)
-
Ž{\ displaystyle W}
bude brát postupně jako hodnoty a :
{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 \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62e69048793e26a2f9ba42849abf3214d0c21594)
-
{1,5}{\ displaystyle \ {1.5 \}}
a jsou přidány do ,{3,4}{\ displaystyle \ {3,4 \}}
MT{\ displaystyle MT}![MT](https://wikimedia.org/api/rest_v1/media/math/render/svg/98a909994972c27e3d072742881c62dcfb3aeeae)
-
{1,3},{1,4},{2,4},{2,5},{3,5}{\ displaystyle \ {1.3 \}, \ {1.4 \}, \ {2.4 \}, \ {2.5 \}, \ {3.5 \}}
a jsou přidány do ,{4,5}{\ displaystyle \ {4,5 \}}
NE2{\ displaystyle N_ {2}}![N_ {2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/597ea9dac049261fdda77c5176b050e6588d6bb9)
- Ostatní hyperhrany jsou nadbytečné;
-
NE2{\ displaystyle N_ {2}}
stojí za to ;{{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 \} \}}![{\ displaystyle \ {\ {1.3 \}, \ {1.4 \}, \ {2.4 \}, \ {2.5 \}, \ {3.5 \}, \ {4.5 \} \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d63810a1871f03400b273c57340a05e3350c3755)
-
Ž{\ displaystyle W}
bude brát postupně jako hodnoty a :
{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 \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/085dd7bab450e45707ee9a6130ea503e84df87f1)
-
{2,4,5}{\ displaystyle \ {2,4,5 \}}
je přidán do ,MT{\ displaystyle MT}![MT](https://wikimedia.org/api/rest_v1/media/math/render/svg/98a909994972c27e3d072742881c62dcfb3aeeae)
- Ostatní hyperhrany jsou nadbytečné;
-
NE3=∅{\ displaystyle N_ {3} = \ emptyset}
;
- Algoritmus se vrátí .MT={{1,5},{3,4},{2,4,5}}{\ displaystyle MT = \ {\ {1,5 \}, \ {3,4 \}, \ {2,4,5 \} \}}
![{\ displaystyle MT = \ {\ {1,5 \}, \ {3,4 \}, \ {2,4,5 \} \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d956b4235292007a3b6ce6b9090494164a24932)
Minimální průřezy jsou dobře a .
H{\ displaystyle {\ mathcal {H}}}
{1,5},{3,4}{\ displaystyle \ {1,5 \}, \ {3,4 \}}
{2,4,5}{\ displaystyle \ {2,4,5 \}}![{\ displaystyle \ {2,4,5 \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4600842f19f3bded1497123b2294d2a039a53d2a)
Poznámky a odkazy
-
Lock. Lhote , Příklady analýzy algoritmů v aritmetice, teorii informací a dolování dat ,19. ledna 2017, 75 s. ( číst online )
-
(in) Michael L. Fredman a Leonid Khachiyan , „ On the Complexity of Monotone Dualization of disjunctive Normal Forms “ , Journal of Algorithms , vol. 21, n o 3,1 st 11. 1996, str. 618-628 ( ISSN 0196-6774 , DOI 10.1006 / jagm.1996.0062 , číst online , přístup k 25. srpnu 2020 )
-
(in) Céline Hébert Alain Bretto a Bruno Crémilleux , „ Formalizace dolování dat ke zlepšení minimálního výpočtu transverzálního hypergrafu “ , Fundamenta Informaticae ,prosince 2007, str. 415-433
-
(in) Julien David , Loïck Lhote , Arnaud Mary a Francois Rioult , „ Průměrná studie hypergrafů a minimálních jejich příčných “ , Teoretická informatika ,2015( DOI 10.1016 / j.tcs.2015.06.052 )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">