Rendszeroptimalizálás, 12. tétel

Ez az oldal a korábbi SCH wikiről lett áthozva.

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 összege. k-matroid-metszet probléma, ennek bonyolultsága k>3 esetén.

Matroidok összege

• Def.*: M₁=(E,F₁) és M₂=(E,F₂) összege M₁∨M₂=(E,F₁∨F₂), ahol X∈F₁∨F₂ ⇔ ∃X₁,X₂: X=X₁∪X₂, X₁∈F₁ és X₂∈F₂. Magyarul X előáll egy F₁-beli és egy F₂-beli elem uniójaként. Megjegyzés: nem változtat a definíción, ha feltesszük, hogy X₁ és X₂ diszjunkt.

• Tétel*: M₁∨M₂ is matroid.
  
• Biz.*:
  

Ezen a helyen volt linkelve a matroidosszeg.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

Az 1. és 2. függetlenségi axióma triviálisan teljesül. A 3. axióma bizonyításához vegyük azt a felbontást, ahol |(X₂∩Y₁)∪(Y₂∩X₁) (a (><) alakú terület elemszáma) minimális és X₁∩X₂=Y₁∩Y₂=∅.

X>Y miatt X₁>Y₁ és X₂>Y₂ közül legalább az egyik teljesül, legyen mondjuk az első. M₁ 3. axiómája miatt ∃x∈X₁-Y₁: Y₁∪{x}∈F₁. Ha x∉Y₂ (∗), akkor x kielégíti a M₁∨M₂-re vonatkozó 3. axiómát is. Ha x∈Y₂, (∗∗), akkor Y₁∪{x}, Y₂-{x} is egy jó felbontás és kisebb az (X₂∩Y₁)∪(Y₂∩X₁) elemszáma, ami ellentmondás.

Matroid csonkolása

• Def.*: M=(E,F). M csonkoltja M'=(E,F'), ahol F' az F elemeit tartalmazza a bázisok kivételével. A függetlenségi axiómák triviálisan teljesülnek. A csonkolástól a matroid rangja 1-gyel csökken.
  
• Pl.*: U_n,k csonkoltja U_n,k-1.

2-matroid-metszet probléma

• MMP_k*: adott k matroid (M_i=(E,F_i), i=1...k) és egy p egész szám. Kérdés: létezik-e F_i-knek legalább p méretű közös elemük?

• Tétel*: MMP₂∈P.
  
• Biz*: M₁=(E,F₁), M₂=(E,F₂), p egész. Ha p>min(r₁,r₂), nem a válasz. Csonkoljuk a matroidokat addig, amíg a rangjuk min(r₁,r₂,p)-re nem csökken. Ezzel a problémát redukáltuk közös bázis keresésére. r₁=r₂=p-re a válasz akkor és csak akkor igenlő, ha M₁∨M₂*=(E,2^E).
• ⇒: ha M₁-nek és M₂-nek van közös B bázisa, akkor M₂*-ban E-B bázis, E=B∪(E-B) egy felbontása az összegnek, azaz az összegben E független, tehát M₁∨M₂* szabadmatroid.
• ⇐: legyen E=C∪D egy olyan felbontása a szabadmatroidnak, ahol C∈F₁ és D∈F₂*.
  |E|| ≤ ||C||+||D|| = r₁(C)+r₂*(D) ≤ r₁(E)+r₂*(E) = r₁(E)+||E||-r₂(E) = ||E.
  C és D diszjunkt bázisok ⇒ C közös bázisa M₁-nek és M₂-nek.

k-matroid-metszet probléma bonyolultsága

Tétel: MMP₃ NP-teljes.

• Biz.*:

• NP-beli, mert tanú egy p elemű közös bázis.
• G irányított gráfban az u és v közötti Hamilton-út keresése visszavezethető MMP₃-ra.
  • M₁=(E,F₁)-ben X⊆E-re X∈F₁ ⇔ az X részgráfban minden pont be-foka legfeljebb 1 és u be-foka 0.
  • M₂=(E,F₂)-ben X⊆E-re X∈F₂ ⇔ az X részgráfban minden pont ki-foka legfeljebb 1 és v ki-foka 0.
  • M₃ a gráf körmatroidja.
  M₁, M₂ és M₃ közös |V-1 elemű bázisai G irányított Hamilton-útjai.

• Tétel*: MMP_k k>3-ra NP-teljes.
  
• Biz.*: az előző bizonyításban definiálit M₁, M₂ és M₃ matroidokhoz vegyünk hozzá k-3 db szabadmatroidot.

-- Peti - 2007.01.02.