Poikittainen reuna
Vuonna hypergraph Teoriassa , eli poikittainen on osa pisteiden joka täyttää kaikki reunat hypergraph . Poikittaisjoukko on [[Ruudukko (matematiikka) | ruudukko ]] . Tämä on analoginen kaavioiden kärkikannen ( englanninkielisen kärkikannen ) kanssa.
Määritelmät
Muistutetaan, että hypergraafi on pari, jossa on joukko pisteitä, ja alaryhmäperhe, jota kutsutaan reunoiksi tai hyperreunoiksi.
H{\ displaystyle {\ mathcal {H}}}
(V,E){\ displaystyle (V, \, E)}
V{\ displaystyle V}
E{\ displaystyle E}
V{\ displaystyle V}![V](https://wikimedia.org/api/rest_v1/media/math/render/svg/af0f6064540e84211d0ffe4dac72098adfa52845)
Poikittainen ja on useita sellainen, että jokainen reuna kuuluvien , .
H{\ displaystyle {\ mathcal {H}}}
T⊂V{\ displaystyle T \ osajoukko V}
e{\ displaystyle e}
E{\ displaystyle E}
T∩e≠∅{\ displaystyle T \ cap e \ neq \ emptyyset}![{\ displaystyle T \ cap e \ neq \ emptyyset}](https://wikimedia.org/api/rest_v1/media/math/render/svg/adb9a0c023dd084b99858d3b2b6ecffe6c08fcc7)
Määrä transversaalisuuden hypergraafi on pienimmän poikittaisen koko . Usein todetaanH{\ displaystyle {\ mathcal {H}}}
H{\ displaystyle {\ mathcal {H}}}
τ(H){\ displaystyle \ tau ({\ mathcal {H}})}
Esimerkki
Esimerkiksi, jos hypergraafin on määritellyt ja , hyväksyy sitten useita poikittaiskokoja, joiden koko on 2 (esimerkiksi tai ) ja mikään koosta 1 (koska yksikään kärki ei kuulu kaikkiin reunoihin). Sen poikittaismäärä on siis 2.
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 \}}![{\ displaystyle \ {2,4 \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/303ee7b3881b20e9b99f732866ee8b061e43aeff)
Poikittaisen redundantit kärjet
Poikittaispisteen sanotaan olevan tarpeeton, jos aloitushypergraafissa on reuna, jonka leikkauspiste tämän poikittaisen kanssa on pienennetty tarkasteltavaan kärkeen. Toisin sanoen hypergraafiin liittyvän poikittaisen kärki ei ole tarpeeton, jos se tyydyttää:i{\ displaystyle i}
X{\ displaystyle X}
H(V,E){\ displaystyle {\ mathcal {H}} (V, E)}
∃e∈E,e∩X={i}{\ displaystyle \ on olemassa e \ E: ssä, e \ cap X = \ {i \}}
Kärkipisteen redundanssi vastaa intuitiivisesti pisteiden joukon poikittaisuutta . Itse asiassa, jos on tarpeeton, sitten kaikki hyper-reuna : jos sitten , ja jos niin on olemassa elementti siten, että auto on tarpeeton. Meillä on sitten . Toisaalta, jos se on poikittainen, niin se on välttämättä tarpeeton, koska jos se olisi olemassa sellainen , niin meillä olisi ja ei olisi poikittainen.
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 \ emptyyset}
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 \ emptyyset}
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 \}) = \ tyhjennä}
X∖{i}{\ displaystyle X \ setminus \ {i \}}![{\ displaystyle X \ setminus \ {i \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6b324a467e1a5062b61fe6ac12419c486a77a23)
Poikittaisen sanotaan olevan minimaalinen (tai ei-redundantti), jos mikään sen osajoukoista ei ole myös poikittainen, mikä vastaa sanomista, ettei mikään sen kärjistä ole tarpeeton. Todellakin: Näimme edellisessä kappaleessa, että jos yksi sen kärjistä olisi tarpeeton, meillä olisi poikittainen osajoukko, ja jos meillä olisi poikittainen osajoukko, voimme osoittaa, että mikä tahansa sen kärki on tarpeeton (esittely on hyvin samanlainen kuin edellinen kappale).
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)
Poikittainen hypergraafi
Hypergraafiin liittyvien minimaalisten poikittaisjoukot muodostavat hypergraafin, jota kutsutaan poikittaiseksi hypergraafiksi .
Laskenta poikittaisen hypergraph on mahdollista, tähän mennessä, ajan , ollessa kardinaali solmujen.
O(EIo(HirsiEI)){\ displaystyle O (N ^ {o (\ log N)})}
EI{\ displaystyle N}![EI](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
Algoritmi
Pseudokoodi
MTMiner-algoritmi ( Minimal Transversals Miner ) antaa mahdollisuuden laskea tietyn hypergraafin vähimmäispoikkisuunnat.
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}
Suoritusesimerkki
Anna pisteiden muodostaman hypergraafin , jossa on reunat . Suoritus etenee seuraavasti:
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 \} \}}![{\ 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}
on alustettu ;∅{\ displaystyle \ emptyyset}![\ tyhjennä](https://wikimedia.org/api/rest_v1/media/math/render/svg/6af50205f42bb2ec3c666b7b847d2c7f96e464c7)
-
EI1{\ displaystyle N_ {1}}
on alustettu ;{{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)
-
W{\ displaystyle W}
otetaan peräkkäin arvoina ja :
{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 \}}
ja lisätään ,{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 \}}
ja lisätään ,{4,5}{\ displaystyle \ {4,5 \}}
EI2{\ displaystyle N_ {2}}![N_ {2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/597ea9dac049261fdda77c5176b050e6588d6bb9)
- Muut hyperreunat ovat tarpeettomia;
-
EI2{\ displaystyle N_ {2}}
on arvoinen ;{{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)
-
W{\ displaystyle W}
otetaan peräkkäin arvoina ja :
{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 \}}
lisätään ,MT{\ displaystyle MT}![MT](https://wikimedia.org/api/rest_v1/media/math/render/svg/98a909994972c27e3d072742881c62dcfb3aeeae)
- Muut hyperreunat ovat tarpeettomia;
-
EI3=∅{\ displaystyle N_ {3} = \ tyhjennä}
;
- Algoritmi palaa .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)
Pienimmät poikittaispisteet ovat hyvin ja .
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)
Huomautuksia ja viitteitä
-
Loick. Lhote , esimerkkejä algoritmianalyysistä aritmeettisessa, informaatioteoriassa ja tiedonlouhinnassa ,19. tammikuuta 2017, 75 Sivumäärä ( lue verkossa )
-
(in) Michael L. Fredman ja Leonid Khachiyan , " monimutkaisuuden monotonista Dualization on vaihtoehtoista Normaali Forms " , Journal of Algorithms , vol. 21, n ° 3,1 kpl marraskuu 1996, s. 618-628 ( ISSN 0196-6774 , DOI 10.1006 / jagm.1996.0062 , luettu verkossa , käytetty 25. elokuuta 2020 )
-
(in) Céline Hébert Alain Bretto ja Bruno Crémilleux , " datan louhinta vakiinnuttaminen parantaa poikittaisen hypergraph minimaalinen laskenta " , Fundamenta Informaticae ,joulukuu 2007, s. 415 - 433
-
(vuonna) Julien David , Loïck Lhote , Arnaud Mary ja Francois Rioult , " Keskimääräinen tutkimus hypergraafeista ja vähäisimmistä niiden poikittaisista " , teoreettinen tietojenkäsittelytiede ,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;">