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.*: M1=(E,F1) és M2=(E,F2) összege M1∨M2=(E,F1∨F2), ahol X∈F1∨F2 ⇔ ∃X1,X2: X=X1∪X2, X1∈F1 és X2∈F2. Magyarul X előáll egy F1-beli és egy F2-beli elem uniójaként. Megjegyzés: nem változtat a definíción, ha feltesszük, hogy X1 és X2 diszjunkt.
- Tétel*: M1∨M2 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 |(X2∩Y1)∪(Y2∩X1) (a (><) alakú terület elemszáma) minimális és X1∩X2=Y1∩Y2=∅.
| X |
> |
Y |
miatt |
X1 |
> |
Y1 |
és |
X2 |
> |
Y2 közül legalább az egyik teljesül, legyen mondjuk az első. M1 3. axiómája miatt ∃x∈X1-Y1: Y1∪{x}∈F1. Ha x∉Y2 (∗), akkor x kielégíti a M1∨M2-re vonatkozó 3. axiómát is. Ha x∈Y2, (∗∗), akkor Y1∪{x}, Y2-{x} is egy jó felbontás és kisebb az (X2∩Y1)∪(Y2∩X1) 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.*: Un,k csonkoltja Un,k-1.
2-matroid-metszet probléma
- MMPk*: adott k matroid (Mi=(E,Fi), i=1...k) és egy p egész szám. Kérdés: létezik-e Fi-knek legalább p méretű közös elemük?
- Tétel*: MMP2∈P.
- Biz*: M1=(E,F1), M2=(E,F2), p egész. Ha p>min(r1,r2), nem a válasz. Csonkoljuk a matroidokat addig, amíg a rangjuk min(r1,r2,p)-re nem csökken. Ezzel a problémát redukáltuk közös bázis keresésére. r1=r2=p-re a válasz akkor és csak akkor igenlő, ha M1∨M2*=(E,2E).
- ⇒: ha M1-nek és M2-nek van közös B bázisa, akkor M2*-ban E-B bázis, E=B∪(E-B) egy felbontása az összegnek, azaz az összegben E független, tehát M1∨M2* szabadmatroid.
- ⇐: legyen E=C∪D egy olyan felbontása a szabadmatroidnak, ahol C∈F1 és D∈F2*.
|E|| ≤ ||C||+||D|| = r1(C)+r2*(D) ≤ r1(E)+r2*(E) = r1(E)+||E||-r2(E) = ||E.
C és D diszjunkt bázisok ⇒ C közös bázisa M1-nek és M2-nek.
k-matroid-metszet probléma bonyolultsága
Tétel: MMP3 NP-teljes.
- 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ő MMP3-ra.
- M1=(E,F1)-ben X⊆E-re X∈F1 ⇔ az X részgráfban minden pont be-foka legfeljebb 1 és u be-foka 0.
- M2=(E,F2)-ben X⊆E-re X∈F2 ⇔ az X részgráfban minden pont ki-foka legfeljebb 1 és v ki-foka 0.
- M3 a gráf körmatroidja.
M1, M2 és M3 közös |V-1 elemű bázisai G irányított Hamilton-útjai.
- Tétel*: MMPk k>3-ra NP-teljes.
- Biz.*: az előző bizonyításban definiálit M1, M2 és M3 matroidokhoz vegyünk hozzá k-3 db szabadmatroidot.
-- Peti - 2007.01.02.
|
