Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel14}} ==!! Matroidok megadása, orákulumok, ezek kapcsolata. k-polimatroid rangfüggvény fogalma. A 2-polimatroid-matching …”

2012-10-22T09:43:37Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel14}} ==!! Matroidok megadása, orákulumok, ezek kapcsolata. k-polimatroid rangfüggvény fogalma. A 2-polimatroid-matching …”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel14}}

==!! Matroidok megadása, orákulumok, ezek kapcsolata. k-polimatroid rangfüggvény fogalma. A 2-polimatroid-matching probléma, ennek bonyolultsága, Lovász tétele (biz. nélkül).==

__TOC__

===Matroid megadása===

A grafikus és lineáris matroidok polinom tárral megadhatók, de az általános matroid leírása exponenciális méretű lenne, ezért feltételezzük, hogy van egy algoritmusunk, ami egy X&sube;E részhalmazra polinom időben kiszámolja M valamilyen tulajdonságát:
* Függetlenségi orákulum: megadja, hogy X független halmaz-e.
* Kör orákulum: eldönti, hogy X kör-e.
* Bázis orákulum: eldönti, hogy X bázis-e.
* Rang orákulum: megadja X rangját.
* Girth orákulum: megadja X által tartalmazott legrövidebb kör hosszát, vagy ∞-t, ha X∈F.

===Orákulumok kapcsolata===

*Def.*: A orákulum erősebb B-nél, ha A polinom időben tudja szimulálni B-t.

*Tétel*: a rang és a függetlenségi orákulum egyforma erejű. 
*Biz.*:
* Ha tudunk rangot számolni, X pontosan akkor független, ha r(X)=|X.
* Ha adott egy függetlenségi orákulum, mohó algoritmussal számolható a rang.

*Tétel*: a függetlenségi orákulum erősebb, mint a bázis orákulum. 
*Biz.*:
* X akkor bázis, ha független, és E-ből bármelyik x elemet hozzávéve nem marad független.
* A bázis orákulummal nem szimulálható a függetlenségi orákulum. Legyen matroidunk egy G gráf körmatroidja, ahol G egy n ágú csillag, melynek középpontjában van még n db hurokél is. Mindig azt válaszolom, hogy nem bázis, így polinom sok kérdéssel nem tudja kizárni az összes, <math> 2n \choose n </math> lehetőséget. (Azaz nem találja meg az egyetlen bázist!)
(-- [[RendesGaborAntal|Gabo]] - 2008.01.04.)

*Tétel*: a függetlenségi orákulum erősebb, mint a kör orákulum. 
*Biz.*:
* X akkor kör, ha nem független, de bármelyik elemet elhagyva független lesz.
* A kör orákulummal nem szimulálható a függetlenségi orákulum. Legyen M1 az U2n,2n szabadmatroid, és M2 G körmatroidja, ahol G egy n ágú csillag a középpontjában egy n hosszú körrel kiegészítve. Minden kérdésre azt válaszoljuk, hogy nem kör. Ahhoz, hogy a kérdező kizárja az összes M2 típusú matroidot, legalább <math> 2n \choose n </math> kérdést kell feltennie, ami exponenciális.

*Tétel*: a girth orákulum erősebb, mint a függetlenségi orákulum. 
*Biz.*:
* X akkor független, ha a g(X)=∞
* M1=U2n,n, g(M1)=n+1. M2-t úgy kapjuk, hogy M1 F halmazából elhagyunk 1 elemet. g(M2)=n. Az X független-e típusú kérdésre akkor válaszolunk igennel, ha |X≤n. Ahhoz, hogy a kérdező kizárja az összes M2 típusú matroidot, legalább <math> 2n \choose n </math> kérdést kell feltennie, ami exponenciális.

<div id="k-polimatroid"></div>
===k-polimatroid rangfüggvény===

*Def.*: f:2E→N egy k-polimatroid rangfüggvénye, ha teljesülnek rá a következő axiómák:
# f(<big>∅</big>)=0
# X&sube;Y <big>⇒</big> f(X)≤f(Y)
# f({x})≤k
# f(X)+f(Y)≥f(X∪Y)+f(X∩Y)
*Speciális eset*: f({x})≤1, ekkor f egy matroid rangfüggvénye. 
*Megj.*: f({x})≤k-vel ekvivalens az f(X)≤k|X|| illetve az f(X∪Y)≤f(X)+k||Y axióma.

===k-polimatroid matching probléma===

*Def.*: X&sube;E k-polimatroid matching, ha f(X)=k|X. 
*Def.*: k-polimatroid matching probléma: adott f és t∈N. Kérdés: van-e legalább t elemű k-polimatroid matching? 
*Speciális esetek*:
* Input: tetszőleges G gráf, t∈N. Kérdés: ν(G)≥t? 2-polimatroid matchingként megfogalmazva: f(X)=|X által lefedett pontok halmaza||≤2||X
|}
* Input: két matroid, t. Kérdés: létezik-e X&sube;E, |X||≥t, X∈F1∩F2 (matroid metszet probléma). 2-polimatroid matchingként megfogalmazva: f(X)=r1(X)+r2(X)≤2||X
|}
* Az utolsó két probléma közös speciális esete: páros gráfban ν(G)≥t?
** 2. probléma leképzése a 3.-ra.: M1 grafikus matroidban e1 és e2 párhuzamos élek, ha e1-nek és e2-nek felül van egy közös pontja. M2-t hasonlóan értelmezzük a páros gráf alsó ponthalmazán.

===A 2-polimatroid matching probléma bonyolultsága===

*Lovász-tétel*: a 2-polimatroid matching probléma polimatroid rangfüggvény orákulummal általános esetben exponenciális. 
*Biz.*: |E=2n, X&sube;E. Tekintsük az alábbi polimatroid rangfüggvényt: 
<math> f(X) = \left\{ \begin{array}{l}
\mbox{|X|$, ha $|X|<n$} \\
\mbox{n+1$, ha $|X|>n$} \\
\mbox{n$ vagy n-1$, ha $|X|=n$}
\end{array} \right. </math> 
Ha egy n elemű részhalmazra kérdeznek rá, 2n-1-et mondok. Polinom sok kérdéssel nem ellenőrizhető, hogy fogok-e 2n-et mondani.

*Lovász-tétel*: Tegyük fel, hogy E (ai,bi) párokból áll és az f függvényt a következőképpen definiáljuk az {1,2,...,n} indexhalmazon: ∀J&sube;I-re f(J)=r(<big>∪</big>i∈J{ai,bi}) 
Ha ∀i r({ai,bi})=2 (nincs hurokél és ai,bi párhuzamos élek), f egy 2-polimatroid rangfüggvény. Ha emellett M koordinátázva is van R felett, a 2-polimatroid matching probléma polinom időben megoldható.

-- [[PallosPeter|Peti]] - 2007.01.02.

[[Category:Infoszak]]

Rendszeroptimalizálás, 14. tétel - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel14}} ==!! Matroidok megadása, orákulumok, ezek kapcsolata. k-polimatroid rangfüggvény fogalma. A 2-polimatroid-matching …”