Rendszeroptimalizálás, 14. tétel

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

!! 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).

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⊆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!)

(-- 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 M₁ az U_2n,2n szabadmatroid, és M₂ 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 M₂ 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)=∞
• M₁=U_2n,n, g(M₁)=n+1. M₂-t úgy kapjuk, hogy M₁ F halmazából elhagyunk 1 elemet. g(M₂)=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 M₂ típusú matroidot, legalább [math] 2n \choose n [/math] kérdést kell feltennie, ami exponenciális.

k-polimatroid rangfüggvény

• Def.*: f:2^E→N egy k-polimatroid rangfüggvénye, ha teljesülnek rá a következő axiómák:

1. f(∅)=0
2. X⊆Y ⇒ f(X)≤f(Y)
3. f({x})≤k
4. 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⊆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⊆E, |X||≥t, X∈F₁∩F₂ (matroid metszet probléma).
  2-polimatroid matchingként megfogalmazva: f(X)=r₁(X)+r₂(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.: M₁ grafikus matroidban e₁ és e₂ párhuzamos élek, ha e₁-nek és e₂-nek felül van egy közös pontja. M₂-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⊆E. Tekintsük az alábbi polimatroid rangfüggvényt:
  

[math] f(X) = \left\{ \begin{array}{l} \mbox{|X|$, ha $|X|\lt n$} \\ \mbox{n+1$, ha $|X|\gt 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 (a_i,b_i) párokból áll és az f függvényt a következőképpen definiáljuk az {1,2,...,n} indexhalmazon: ∀J⊆I-re f(J)=r(∪_i∈J{a_i,b_i})
  

Ha ∀i r({a_i,b_i})=2 (nincs hurokél és a_i,b_i 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ó.

-- Peti - 2007.01.02.