Matematika | Felsőoktatás » Matroidok összege és metszete

Matroidok összege és metszete 1. Matroidok A matroidok fogalmát Hassler Whitney amerikai matematikus vezetette be 1935-ben els®sorban a lineáris függetlenség jellemz® tulajdonságainak absztrakt módon történ® megfogására. 1.1 Deníció (Matroid) Az Legyen adott egy S véges halmaz, illetve S részhalmazainak egy F rendszere. M = (F, S) pár matroidot alkot, ha az alábbi három feltételt teljesíti: A) ∅∈F B) X ⊆ Y ∈ F esetén X ∈ F (leszálló tulajdonság) C) tetsz®leges X ⊆ S részhalmaz esetén az F -nek X -ben fekv® és X -ben legb®vebb tagjai azonos elem- számúak Az F tagjait a matroid függetlenjeinek, míg a többi részhalmazt függ®nek hívjuk. Az utolsó feltételben meg- fogalmazott maximális elemszámot az rangját értjük, melyet X halmaz rangjának nevezzük. A matroid rangján az S alaphalmaz r(M ) jelöl. A maximális elemszámú független halmazokat bázisoknak, a minimális elemszámú függ® halmazokat pedig a

matroid köreinek nevezzük. Érdemes megjegyezni, hogy a fenti denícióval ekvivalens megfogalmazást kapunk, ha az els® feltételt az F 6= ∅ alakban adjuk meg. Most néhány egyszer¶ példa következik matroidokra A) Mátrix-matroid: tekintsünk egy test feletti A mátrixot, amelynek oszlopai legyenek S elemei. Egy X ⊆ S halmaz pontosan akkor független, ha a mátrix megfelel® oszlopai lineárisan függetlenek. B) Grakus matroid: tekintsünk egy G = (V, E) gráfot. Ezúttal S elemeit a gráf élei szolgáltatják Egy X ⊆ S halmaz pontosan akkor független, ha nem tartalmaz kört. C) Uniform matroid: tekintsünk egy S halmazt és egy 1 ≤ k ≤ |S| egész számot. Egy X ⊆ S halmaz pontosan akkor független, ha |X| ≤ k teljesül. D) Transzverzális matroid: egy G = (S, T ; E) páros gráfban az S pontosztály párosítható részhalmazai matroidot alkotnak. E) Partíciós matroid: az S = {S1 , . , Sk } alaphalmazon értelmezett M1 , , Mk uniform matroidok direkt

összege. F) Párosítás matroid: a G = (V, E) gráf ponthalmazán értelmezett matroid, amelyben U ⊆ V pontosan akkor független, ha lefedhet® egy párosítás által. 1 2. Matroidok metszete Nemcsak Kruskal mohó algoritmusa terjeszthet® ki matroidokra, hanem a párosításokra vonatkozó K®nig-Hall-tétel is. Legyen G = (S, T ; E) egyszer¶ páros gráf, valamint M = (S, r) tetsz®leges matroid A gráf egy párosítását akkor nevezzük M -függetlennek, ha az általa fedett S -beli pontok halmaza független M -ben. Egy X ⊆ T halmazra jelölje Γ(X) az X szomszédainak halmazát A Hall-tétel matroidos általánosítása Radotól származik. 2.1 Tétel (Rado) Legyen adva a G = (S, T ; E) páros gráf S ponthalmazán egy M = (S, r) matroid. Az olyan párosítás maximális elemszáma, amely a S -ben a matroid egy független ponthalmazát fedi egyenl® minX⊆T {r(Γ(X) + |T − X|} értékkel. Speciálisan, akkor és csak akkor létezik T -t fed® M -független

párosítás, ha minden X ⊆ T esetén teljesül a Rado-féle feltétel: r(Γ(X)) ≥ |X| Speciális esetként visszakapjuk a Hall-tételt, amennyiben r(Γ(X)) ≡ Γ(X), azaz M éppen a szabad matroid. Megjegyzés. A kombinatorikus optimalizálás egyik központi eredménye Edmonds metszet-tétele, amely tartalmilag ekvivalens ugyan a Rado-tétellel, de általánosabb megfogalmazása miatt alkalmazásokban jobban használható. 2.2 Tétel (Edmonds metszet-tétele) Az S alaphalmazon legyen adott két matroid: M1 = (S, r1 ) és M2 = (S, r2 ). A közös független halmazok maximális elemszáma egyenl® a min {r1 (X) + r2 (S − X)} X⊆S értékkel. 2.3 Következmény leges A tétel alapján pontosan akkor létezik k elem¶ közös független halmaz, ha tetsz®- S = X1 ∪ X2 partíció esetén r1 (X1 ) + r2 (X2 ) ≥ k teljesül. Edmonds bizonyítása algoritmikus és az alternáló utas módszer kiterjesztésének tekinthet®. Térjünk át a súlyozott esetre. Egy

páros gráf maximális súlyú teljes párosítási valamint egy digráf legolcsóbb feszít® feny® feladatának közös általánosításaként Edmonds megoldotta két matroid maximális súlyú közös bázisának problémáját is. Egyrészt egy lineáris programozáson alapuló min-max formulát adott a maximális súlyú közös bázis súlyára, másrészt egy polinomiális algoritmust is leírt ennek kiszámítására. Legyen adott az S alaphalmazon két matroid, továbbá egy c : S Z egészérték¶ súlyfüggvény. Tegyük fel, hogy az M1 és M2 matroidoknak van közös bázisa, melynek elemszámát jelölje k. Valamely x : S Z súlyfüggvényre jelölje r̂i (x) az Mi matroidban a maximális x-súlyú bázis súlyát. 2.4 Tétel (Súlyozott metszet-tétel) Az M1 és M2 matroidok közös bázisainak maximális c-súlya egyenl® a min{r̂1 (c1 ) + r̂2 (c2 ) : c1 + c2 = c, ci egészérték¶} értékkel. Egy B közös bázis akkor és csak akkor maximális c-súlyú,

ha létezik c-nek egy egészérték¶ c1 + c2 felbontása úgy, hogy B egyrészt az M1 -nek maximális c1 -súlyú bázisa, másrészt az M2 -nek maximális c2 -súlyú bázisa. A tételben megfogalmazott optimalitási kritérium teremt lehet®séget egy viszonylag egyszer¶ er®sen polinomiális súlyozott matroidmetszet algoritmus konstruálására. 2 2.5 Tétel (Maximális súlyú közös függetlenek) Az S alaphalmazon adott két matroid és egy c nemnegatív egészérték¶ súlyfüggvény. A maximális súlyú közös független halmaz súlya egyenl® a min{r̂1 (c1 ) + r̂2 (c2 ) : c1 + c2 = c, c1 ≥ 0, c2 ≥ 0, ci egészérték¶} értékkel. 3. Matroidok összege A matroid metszet-tételhez hasonlóan fontos a matroid partíciós tétel. Legyen adott az S alaphalmazon k matroid. Nevezzünk egy X ⊆ S halmazt partícionálhatónak, ha el®áll az egyes matroidokból vett (összesen k darab) független halmaz uniójaként. 3.1 Tétel (Partíciós tétel) A

partícionálható halmazok egy matroid független halmazait alkotják. Az S legnagyobb partícionálható részhalmazának rΣ elemszáma egyenl® a min {|S − X| + X⊆S k X ri (X)} i=1 értékkel. Egyszer¶ konstrukciók segítségével kimutatható, hogy a metszet-tétel és a partíciós tétel egymással ekvivalens. A partícionálható halmazok matroidját a k matroid összegének nevezik A tételb®l kiolvasható, hogy az alaphalmaz mikor fedhet® le k bázissal és hogy mikor létezik k páronként diszjunkt bázis. 4. Alkalmazások A) Amiképp a metszettétel általánosítja K®nig tételét, a súlyozott metszettételb®l könnyen levezethet® Egerváry alaperedménye G = (A, B; E) páros gráfok maximális súlyú teljes párosításának súlyáról. Legyen ugyanis az E halmazon M1 és M2 az a partíciós matroid, amelyben egy F ⊆ E halmaz akkor független, ha dF (v) ≤ 1 minden A-beli csúcsra, illetve minden B -beli csúcsra fennáll. Ekkor a közös

bázisok éppen a teljes párosítások. B) Legyen adva a D = (V, A) irányított gráf élhalmazán egy c : A R+ súlyozás. A maximális súlyú fenyves problémája súlyozott matroid metszet problémaként fogalmazható meg, ahol az egyik matroid az irányítatlan alapgráf körmatroidja, míg a másik az a partíciós matroid, amelyben egy élhalmaz akkor független, ha minden csúcsba legfeljebb egy éllel lép be. Itt szintén alkalmazhatjuk a súlyozott matroid metszet algoritmust. 3