Rendszeroptimalizálás, 13. 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

!! A k-matroid partíciós probléma, ennek algoritmikus megoldása. A 2-matroid-metszet feladat visszavezetése matroid partíciós problémára.

k-matroid partíciós probléma

• MPP_k*: adott k matroid (M_i=(E,F_i), i=1...k). Kérdés: a matroidok összege a szabadmatroidot adja-e, vagyis E előáll-e E₁∪...∪E_k alakban úgy, hogy E_i∈F_i ∀i-re. Feltehető, hogy az E_i halmazok diszjunktak, ezért hívják a feladatot matroid partíciós problémának.

• Lemma*: MPP_k NP-beli, mert tanú rá egy particionálás, és a tanú lineáris időben ellenőrizhető.
  
• Lemma*: MPP_k coNP-beli, mert tanú rá egy X⊆E halmaz, ami biztosan összefüggő az összegben, azaz ∑r_i(X)<|X.

Algoritmus

Induljunk ki az ∀i E_i=∅ állapotból. Ekkor E_i∈F_i. Az E_i halmazokat addig bővítjük, amíg az uniójuk E nem lesz, vagy ha nem bővíthető, mutatunk egy X tanút.

A bővítéshez bevezetünk egy n+k pontú irányított segédgráfot, amelynek

• Csúcsai E elemei ∪ {p₁, ..., p_k}. p_i az E_i partíció segédpontja.
• (x→p_i) ∈ E(G), ha x∉E_i és E_i∪{x}∈F_i.
  Az ilyen típusú élek azt jelképezi, hogy az E_i partícióba felvehető x a függetlenség megsértése nélkül.
• (x→y) ∈ E(G), ha ∃i x∉E_i, y∈E_i, E_i∪{x}∉F_i, de E_i∪{x}-{y}∈F_i.
  Az ilyen típusú élek azt jelentik, hogy az E_i partícióban az y elem kicserélhető x-re a függetlenség megsértése nélkül.

1. Megkeressük a legrövidebb irányított utat E-∪E_i-ből {p₁, ..., p_k}-ba.
2. Ha van ilyen út, javítunk az út mentén, azaz végrehajtjuk a cseréket. ∪E_i mérete 1-gyel nő. Azért kell a legrövidebb úton végigmenni, mert különben nem garantált, hogy a cserék során nem sérül a partíciók függetlensége.
3. Különben STOP, nemleges a válasz, és a tanú a E-∪E_i-ből irányított úton elérhető pontok halmaza.

2-matroid-metszet feladat

Ld. 12. tétel, MMP₂ szakasz

-- Peti - 2007.01.02.

Javítás: ∑r_i(X)<|E|| helyett ∑r_i(X)<||X !

-- Gabo - 2008.01.04.